User Tools

Site Tools


ex-lists

Differences

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

Link to this comparison view

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:
 +<code ocaml>
 +# fib 10;;
 +- : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34]
 +</​code>​
 +
 +\\
 +
 +===== 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:
 +<code ocaml>
 +# primes 20;;
 +- : int list = [2; 3; 5; 7; 11; 13; 17; 19]
 +</​code>​
 +
 +\\
 +
 +===== 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:
 +<code ocaml>
 +# palseq 150 10;;
 +- : int list = [151; 161; 171; 181; 191; 202; 212; 222; 232; 242]
 +</​code>​
 +
 +//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:
 +<code ocaml>
 +# 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');;
 +</​code>​
 +
 +\\
 +
 +===== 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:
 +<code ocaml>
 +# sort [3;​4;​5;​1;​2;​7;​6] compare;;
 +- : int list = [1; 2; 3; 4; 5; 6; 7]
 +</​code>​
 +
 +\\
 +
 +===== 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:
 +<code ocaml>
 +# 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]]
 +</​code>​
 +
 +\\
 +
 +===== 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:
 +<code ocaml>
 +open_in : string -> in_channel
 +close_in : in_channel -> unit
 +input_line : in_channel -> string
 +</​code>​
 +
 +  * ''​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</​sub>,​...,​x<​sub>​n</​sub>​] such that:
 +  - x<​sub>​i</​sub>​∈1..n for all i∈1..n ​
 +  - x<​sub>​i</​sub>​≠x<​sub>​j</​sub>​ for all i≠j.
 +
 +For instance, a possible output of ''​genperm 10''​ could be:
 +<code ocaml>
 +- : int list = [10; 3; 7; 4; 9; 5; 2; 6; 1; 8]
 +</​code>​
 +
 +//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</​sub>​(i) = (i + k) mod 26.  For instance, ''​shift_encrypt 3 '​a'​ ''​ evaluates to ''​d'',​ because E<​sub>​3</​sub>​(0) = (0 + 3) mod 26 = 3 and ''​shift_encrypt 3 '​z'​ ''​ evaluates to ''​c'',​ because ​ E<​sub>​3</​sub>​(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</​sub>​(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:
 +<code ocaml>
 +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;;
 +</​code>​
 +
 +\\
 +
 +===== 9. LFSR keystream =====
 +
 +Let k = k<​sub>​1</​sub>​ ... k<​sub>​m</​sub> ​
 +and c = c<​sub>​0</​sub>​ ... c<​sub>​m-1</​sub> ​
 +be two lists of length m.
 +Let the sequence z<​sub>​1</​sub>​ z<​sub>​2</​sub>​ ... 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</​sub>​ z<​sub>​2</​sub>​ ... z<​sub>​n</​sub>​
 +
 +For instance, if ''​k = [1;​0;​0;​0]''​ and ''​c = [1;​1;​0;​0]'',​ we will have:
 +<code ocaml>
 +keystream 15 c k;;
 +- : int list = [1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 0; 1; 1; 1]
 +</​code>​
 +
 +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</​sub>​ ...  x<​sub>​n</​sub>​ 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</​sub>​ ... z<​sub>​n</​sub>​.
 +
 +Then, the encryption of x (under key k,c) is the list y = y<​sub>​1</​sub>​ ... y<​sub>​n</​sub> ​
 +such that y<​sub>​i</​sub>​ = (x<​sub>​i</​sub>​ + z<​sub>​i</​sub>​) 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: ​
 +<code ocaml>
 +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"​)]
 +</​code>​
 +
 +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: ​
 +<code ocaml>
 +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"​)]
 +</​code>​
 +
 +
 +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:​
 +<code ocaml>
 +# 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 
 +</​code>​
 +
 +such that:
 +
 +1. ''​fsearch x l''​ evaluates to true iff ''​x''​ belongs to the list ''​l''​.
 +
 +2. ''​fadd x [(x<​sub>​1</​sub>,​n<​sub>​1</​sub>​);​...;​(x<​sub>​k</​sub>,​n<​sub>​k</​sub>​)]'',​ assuming that there exists an index i such that
 +x=x<​sub>​i</​sub>,​ produces the list ''​[(x<​sub>​1</​sub>,​n<​sub>​1</​sub>​);​...;​(x<​sub>​i</​sub>,​n<​sub>​i+1</​sub>​);​...;​(x<​sub>​k</​sub>,​n<​sub>​k</​sub>​)]''​
 +
 +3. ''​fcount [x<​sub>​1</​sub>;​...;​x<​sub>​k</​sub>​]''​ evaluates to the list ''​[(x<​sub>​1</​sub>,​n<​sub>​1</​sub>​);​...;​(x<​sub>​k</​sub>,​n<​sub>​k</​sub>​)]'',​
 +where ''​n<​sub>​i</​sub>''​ is the number of occurrences of ''​x<​sub>​i</​sub>''​ in ''​l'',​ for all i. 
 +
 +\\
ex-lists.txt · Last modified: 2015/10/08 15:20 (external edit)