ex-lists

LiP assignment #4

1. Fibonacci sequence

Write a fuction that, given as input a natural n, outputs the list of the first n Fibonacci numbers. You must use a linear-time complexity algorithm to compute Fibonacci numbers. For instance, for n=10 you must obtain the following output:

# fib 10;;
- : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34]

2. Prime numbers

Write a function that outputs the list of the prime numbers lower or equal to n. For instance, for n=20 you must obtain the following output:

# primes 20;;
- : int list = [2; 3; 5; 7; 11; 13; 17; 19]

3. Palindromes

Write a function that output the list of the first n palindrome numbers greater or equal to m. For instance, if n=10 and m=150, you must obtain the following output:

# palseq 150 10;;
- : int list = [151; 161; 171; 181; 191; 202; 212; 222; 232; 242]

Hint. You can use the function string_of_int to transform an integer into a string, and the following code snippet to transform such a string into a list of integers:

# let rec list_of_string s =
if s="" then []
else let s' = (String.sub s 1 ((String.length s)-1))
in  (String.get s 0)::(list_of_string s');;

4. Merge sort

Write a function that sorts the elements of a list according to a given comparison function, using the merge sort algorithm. The comparison function must return 0 if its arguments compare as equal, a positive integer if the first is greater, and a negative integer if the first is smaller. For instance, you must have:

# sort [3;4;5;1;2;7;6] compare;;
- : int list = [1; 2; 3; 4; 5; 6; 7]

5. Permutations

Write a function that, taken as input a list l, produces a list contaning all the permutations of the elements of the l. For instance, you must obtain:

# perm [1;2;3];;
- : int list list = [[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]]

6. Letter frequency

Write a function freq that takes as input a name f of a text file, and outputs a list of pairs (x,d), where x is a letter occurring in the text file, and d is the associated frequency (d = number of occurrences of x / total number of letters). The list must be ordered by frequency (in decreasing order).

Hint. Use the following functions for opening/closing files, and for reading text lines:

open_in : string -> in_channel
close_in : in_channel -> unit
input_line : in_channel -> string
• open_in f opens the file named f for reading, and returns a new input channel on that file, positioned at the beginning of the file. Raises Sys_error if the file could not be opened.
• close_in ch closes the channel ch. Input functions raise a Sys_error exception when they are applied to a closed input channel, except close_in, which does nothing when applied to an already closed channel. Note that close_in may raise Sys_error if the operating system signals an error.
• input line ch reads characters from the input channel ch, until a newline character is encountered. Returns the string of all characters read, without the newline character at the end. Raises End_of_file if the end of the file is reached at the beginning of line.

7. Random permutation

Write a function genperm that, taken as input an integer n, produces as output a random permutation of 1..n, i.e. a list of integers [x1,…,xn] such that:

1. xi∈1..n for all i∈1..n
2. xi≠xj for all i≠j.

For instance, a possible output of genperm 10 could be:

- : int list = [10; 3; 7; 4; 9; 5; 2; 6; 1; 8]

Hint. You should *not* use the function perm of Exercise 5. Use the expression Random.int n to generate a random integer between 0 and n-1.

8. Shift cipher

1. Write a function charpos: char → int that gives the position of a character. For instance, charpos 'a' evaluates to 0, charpos 'b' evaluates to 1, etc. (We assume the english alphabet, and that positions start from 0).
2. Write a function shift_encrypt: int → char → char such that shift_encrypt k x is the encryption of a character x under the key k. The encryption of character x (with position i) is defined as the character with position Ek(i) = (i + k) mod 26. For instance, shift_encrypt 3 'a' evaluates to d, because E3(0) = (0 + 3) mod 26 = 3 and shift_encrypt 3 'z' evaluates to c, because E3(25) = (25 + 3) mod 26 = 2.
3. Write a function shift_decrypt: int → char → char such that shift_decrypt k y is the decryption of a character y under the key k. The decryption of a character y (with position j) under a key k is defined as the character with position Dk(j) = (j - k) mod 26.
4. Write a function shift_encrypt_file: int → string → string that, taken as input an integer key k and the names of two files (in, out), writes in the file out the encryption of the file in. You can assume that the input file only contains lowercase letters a-z.
5. Write a function shift_decrypt_file: int → string → string that, taken as input an integer key k and the names of two files (in, out), writes in the file out the decryption of the file in.

Hint. Use the following function to get a list of characters from a string:

let rec list_of_string s =
if s="" then []
else let s' = (String.sub s 1 ((String.length s)-1)) in
let l= list_of_string s' in
let c = String.get s 0 in
c::l;;

9. LFSR keystream

Let k = k1 … km and c = c0 … cm-1 be two lists of length m. Let the sequence z1 z2 … be defined as follows, for all i>0:

Write a function keystream : int → int list → int list → int list such that keystream n c k evaluates to the list z1 z2 … zn

For instance, if k = [1;0;0;0] and c = [1;1;0;0], we will have:

keystream 15 c k;;
- : int list = [1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 0; 1; 1; 1]

Then, write a function lfsr_encrypt: int list → int list → int list → int list such that lfsr_encrypt c k x evaluates to the encryption of the list x with the LFSR stream cipher, which is defined as follows.

Let x = x1 … xn is a list of 0/1 (of arbitrary length), let c,k be lists of 0/1 (of equal length), and assume that keystream n c k evaluates to the list z = z1 … zn.

Then, the encryption of x (under key k,c) is the list y = y1 … yn such that yi = (xi + zi) mod 2.

10. Dutch national flag problem

1) Consider a list of elements of type 'a * string and two functions isred : 'a * string → bool and isblue : 'a * string → bool Assume that for each element x of the list, either isred x or isblue x (but not both) is true. Write a recursive function order : ('a * string) list → ('a * string) list that orders the list, by putting all the red elements before all the blue ones. The ordering among the elements of the same colour is not relevant. For instance:

let l = [1,"b"; 2,"r"; 3,"r"; 4,"b"];;
# val l : (int * string) list = [(1, "b"); (2, "r"); (3, "r"); (4, "b")]

order l;;
# - : (int * string) list = [(2, "r"); (3, "r"); (4, "b"); (1, "b")]

2) Solve the previous problem using the List.fold_right function and no recursion.

3) Solve the previous problem using the List.fold_left function and no recursion.

4) Consider having also the function iswhite : 'a * string → bool and assume that for each element x of the list, only one between isred x or isblue x or iswhite x is true. Write a recursive function order : ('a * string) list → ('a * string) list that orders the list, by putting all the elements in the red - white - blue ordering. The ordering among the elements of the same colour is not relevant. For instance:

let l = [1,"b"; 2,"r"; 3,"r"; 4,"b"; 5,"w"];;
# val l : (int * string) list = [(1, "b"); (2, "r"); (3, "r"); (4, "b"); (5, "w")]

order l;;
# - : (int * string) list = [(2, "r"); (3, "r"); (5, "w"); (1, "b"); (4, "b")]

5) Solve the previous problem using the List.fold_right function and no recursion.

6) Solve the previous problem using the List.fold_left function and no recursion.

11. Number of occurrences in a list

Complete the following definitions:

# let fsearch = List.fold_right ...
val fsearch : 'a -> ('a * 'b) list -> bool

# let fadd    = List.fold_right ...
val fadd :  'a -> ('a * int) list -> ('a * int) list

# let fcount  = List.fold_right ...
val fcount : 'a list -> ('a * int) list

such that:

1. fsearch x l evaluates to true iff x belongs to the list l.

2. fadd x [(x1,n1);…;(xk,nk)], assuming that there exists an index i such that x=xi, produces the list [(x1,n1);…;(xi,ni+1);…;(xk,nk)]

3. fcount [x1;…;xk] evaluates to the list [(x1,n1);…;(xk,nk)], where ni is the number of occurrences of xi in l, for all i.

ex-lists.txt · Last modified: 2015/10/08 15:20 (external edit)

Page Tools 