ex-lists

# Differences

This shows you the differences between two versions of the page.

 — ex-lists [2015/10/08 15:20] (current) Line 1: Line 1: + ====== 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 [[wp>​merge_sort|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 [x<​sub>​1,​...,​x<​sub>​n​] such that: + - x<​sub>​i​∈1..n for all i∈1..n ​ + - x<​sub>​i​≠x<​sub>​j​ 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 ===== + + - 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). + - 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 ​  ​E<​sub>​k​(i) = (i + k) mod 26.  For instance, ''​shift_encrypt 3 '​a'​ ''​ evaluates to ''​d'',​ because E<​sub>​3​(0) = (0 + 3) mod 26 = 3 and ''​shift_encrypt 3 '​z'​ ''​ evaluates to ''​c'',​ because ​ E<​sub>​3​(25) = (25 + 3) mod 26 = 2. + - 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 D<​sub>​k​(j) = (j - k) mod 26. + - 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. + - 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 = k<​sub>​1​ ... k<​sub>​m ​ + and c = c<​sub>​0​ ... c<​sub>​m-1 ​ + be two lists of length m. + Let the sequence z<​sub>​1​ z<​sub>​2​ ... be defined as follows, for all i>0: + + {{:​lfsr.png?​400|}} + + Write a function ''​keystream : int -> int list -> int list -> int list''​ such that + ''​keystream n c k''​ evaluates to the list z<​sub>​1​ z<​sub>​2​ ... z<​sub>​n​ + + 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 = x<​sub>​1​ ...  x<​sub>​n​ 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 = z<​sub>​1​ ... z<​sub>​n​. + + Then, the encryption of x (under key k,c) is the list y = y<​sub>​1​ ... y<​sub>​n ​ + such that y<​sub>​i​ = (x<​sub>​i​ + z<​sub>​i​) 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 [(x<​sub>​1,​n<​sub>​1​);​...;​(x<​sub>​k,​n<​sub>​k​)]'',​ assuming that there exists an index i such that + x=x<​sub>​i,​ produces the list ''​[(x<​sub>​1,​n<​sub>​1​);​...;​(x<​sub>​i,​n<​sub>​i+1​);​...;​(x<​sub>​k,​n<​sub>​k​)]''​ + + 3. ''​fcount [x<​sub>​1;​...;​x<​sub>​k​]''​ evaluates to the list ''​[(x<​sub>​1,​n<​sub>​1​);​...;​(x<​sub>​k,​n<​sub>​k​)]'',​ + where ''​n<​sub>​i''​ is the number of occurrences of ''​x<​sub>​i''​ in ''​l'',​ for all i. + + \\