Esercizi di Linguaggi di Programmazione

Esercizi Base su Scala


Exercise 1: Functional Scala.

Define the following functions in Scala:

  1. is_palindrome: string → bool that checks if the string given as input is palindrome, a string is palindrome when the represented sentence can be read the same way in either directions in spite of spaces, punctual and letter cases, e.g., detartrated, "Do geese see God?", "Rise to vote, sir.", ...;
  2. is_an_anagram : string → string list → boolean that given a dictionary of strings, checks if the input string is an anagram of one or more of the strings in the dictionary;
  3. factors: int → int list that given a number calculates all its prime factors;
  4. is_proper: int → boolean that given a number calculates if it is a perfect number or not, where a perfect number is a positive integer equal to the sum of its proper positive divisors (excluding itself), e.g., 6 is a perfect number since 1, 2 and 3 are the proper divisors of 6 and 6 is equal to 1+2+3;
Exercise 2: List Comprehensions.

Write the following functions by using list comprehensions:

Exercise 3: Distributed Reverse String.

To reverse the order of the characters in a string is quite trivial but when the length of the string grows trivial could means extremely slow. To decompose the input string in shorter strings and to join back the inverted strings in order to keep the algorithm working always on a short input is a good idea to fast the process.

Write a master-slave distributed system where:

When done with the exercise try to relax the constraint on the number of substrings from ten to a generic M passed as an input to the long_reversed_string service.

Note, Scala supports the actor model in a way really similar to Erlang look at the documentation to see the difference and learn how to implement the exercise.

Exercise 4: Playing around with Algebra.

A monoid is an algebraic structure consisting of a set together with a single associative binary operation and an identity element. E.g., the set of booleans with the or operator is a monoid whose identity is false.

A group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity and invertibility. E.g., the set Z (the integers with sign) with the + operator is a group but with the * is not since inverting the operation break the closure property.

A ring is an algebraic structure consisting of a set together with two binary operations (usually called addition and multiplication), where each operation combines two elements to form a third element. To qualify as a ring, the set together with its two operations must satisfy certain conditions, namely, the set must be an abelian (i.e., commutative) group under addition and a monoid under multiplication such that multiplication distributes over addition.

Write the Monoid, Group and Ring classess implementing the monoids, groups and rings algebraic structures respectively. Each class must be parametric on the algebraic sort, in the sense that the operations and the sets are not a priori defined and they should implement operations to check the properties characterizing the algebraic structure.

Test your implementation with the following examples (S is the set, add=additive operation, mul=multiplicative operation, i=identity):

Monoids

Groups

Rings

Note property checks on infinite sets should be on a finite subset.

Exercise 5: Playing with Files and Strings.

A KeWord In Context (KWIC) index is a simple index for a list of lines or titles. This assignment involves creating a KWIC index for an input list of titles stored in a file. Here's a small example. For the input file:

[02:34]cazzola@hymir:~/lp/scala>cat kwic.txt
My Big Fat Greek Wedding
One Flew Over the Cuckoo's Nest
Star Wars: Revenge of the Sith
Everything You Always Wanted To Know About Sex But Were Too Afraid To Ask
Borat: Cultural Learnings of America for Make Benefit Glorious Nation of Kazakhstan

your program should produce the output:

[02:36]cazzola@hymir:~/lp/scala>scala KWIC kwic.txt
   4 ed To Know About Sex But Were Too Afraid To Ask                           
   4                    Everything You Always Wanted To Know About Sex But Were
   5      Borat: Cultural Learnings of America for Make Benefit Glorious Nation
   4  About Sex But Were Too Afraid To Ask                                     
   5 ral Learnings of America for Make Benefit Glorious Nation of Kazakhstan   
   1                                My Big Fat Greek Wedding                   
   5                                   Borat: Cultural Learnings of America for
   2                 One Flew Over the Cuckoo's Nest                           
   5                            Borat: Cultural Learnings of America for Make B
   4                                   Everything You Always Wanted To Know Abo
   1                            My Big Fat Greek Wedding                       
   2                               One Flew Over the Cuckoo's Nest             
   5 nings of America for Make Benefit Glorious Nation of Kazakhstan           
   1                        My Big Fat Greek Wedding                           
   5 r Make Benefit Glorious Nation of Kazakhstan                              
   4   Everything You Always Wanted To Know About Sex But Were Too Afraid To As
   5                   Borat: Cultural Learnings of America for Make Benefit Gl
   5 Cultural Learnings of America for Make Benefit Glorious Nation of Kazakhst
   1                                   My Big Fat Greek Wedding                
   5 America for Make Benefit Glorious Nation of Kazakhstan                    
   2        One Flew Over the Cuckoo's Nest                                    
   2                                   One Flew Over the Cuckoo's Nest         
   3                        Star Wars: Revenge of the Sith                     
   4 g You Always Wanted To Know About Sex But Were Too Afraid To Ask          
   3         Star Wars: Revenge of the Sith                                    
   3                                   Star Wars: Revenge of the Sith          
   4 Wanted To Know About Sex But Were Too Afraid To Ask                       
   4             Everything You Always Wanted To Know About Sex But Were Too Af
   3                              Star Wars: Revenge of the Sith               
   1                  My Big Fat Greek Wedding                                 
   4 ways Wanted To Know About Sex But Were Too Afraid To Ask                  
   4                        Everything You Always Wanted To Know About Sex But

As you can see, each title is listed for each word (omitting some minor words). The titles are arranged so that the word being indexed is shown in a column on the page. The position the lines have in the input file is shown on the left in the result.

Your solution should follow the following rules:

Exercise 6: A Few More Math.

Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Every even integer greater than 2 is a Goldbach number, i.e., a number that can be expressed as the sum of two primes.

Expressing a given even number as a sum of two primes is called a Goldbach partition of the number. For example,

04 = 2 +  2           6 = 3 +  3           8 = 3 +  5

10 = 7 +  3          12 = 5 +  7          14 = 3 + 11

16 = 5 + 11          18 = 7 + 11          20 = 7 + 13

Write the following functions:

Exercise 7: A Matrix Class.

You have to write a class Matrix to represent and manipulate integer matrices. The class should be parametric on its dimensions and will provide the operations of matrix equivalence, matrix copy, matrix addition, scalar-matrix multiplication, matrix-matrix multiplication, matrix transposition, and matrix norm -- the "size" of a matrix. Override the appropriate operators and raise the appropriate exceptions.

The following gives the semantics of such operations.

Let aij denote the i,j-th element of matrix A, located at row i, column j. Using this notation, the matrix operations listed above may be defined precisely as follows:

Note that in each case we state the proper matrix dimensions for the operation to be valid. For example, when multiplying two matrices A and B, the number of columns of A must match the number of rows of B.

Exercise 8: Playing with Traits.

As you probably know, vi is a modal text editor: it operates in either insert mode (where typed text becomes part of the document) or normal mode (where keystrokes are interpreted as commands that control the edit session). Ex is a line editor that serves as the foundation for the screen editor vi. Ex commands work on the current line or on a range of lines in a file.

Syntax of Ex commands

:[address] command [options]

In our exercise we are going to implement a simplified version of the line editor Ex used by VI.

In particular you have to implement a class editor representing a line of text with the following operations defined on it:

Clearly all the above operations are methods invokable on instances of the editor class. Each instance should have clear where the cursor is after each computation.

As you can imagine to debug the editor class is not easy. In particular it is difficult to find out which operation has changed the text and where the cursor is in any moment. To this respect write a trait debug (to be applied to the editor class) that, when you print the line of text prints also who has performed the operation and where the cursor is.

Moreover, any (usable) editor should have a mechanism to undo and redo the actions carried out on the text and our line editor cannot do an exception to this rule.

On the other side undo/redo operations are normally orthogonal to the text editing actions and they are separately implemented. We are going to adopt the same approach to their implementation by defining a UndoRedo trait.

The UndoRedo trait will add to the editor class two operations:

Note that every pair of calls uctrlr will leave the text unchanged. A call to ctrlr method after any other editing command (i.e., any method different from u) has no effect.

The undo/redo model to implement is linear, i.e., if you edit the text after an undo operation you lose the possibility to redo all the changes to it and a successive undo do not restore this possibility.

Walter Cazzola

Didactics

Publications

Funded Projects

Research Projects

Related Events