10.5. Exercises

10.5.1. Mandatory exercises

  • Exercise 1 Implementing a solution for Knapsack problem via permutations.
  • Exercise 2 Implementing a solution for Knapsack problem via backtracking.
  • Exercise 3 SAT-solver
  • Exercise 4 Better DNA encoding

10.5.3. Exercise 1

Implement a version of a solver for the Knapsack Problem (finding a list of items to include) by using the function perm for enumerating all permutations of an array, implemented as a part of your midterm project. Implement randomised testing for the Knapsack solvers and use it to test your implementation with respect to the one implemented in the lecture.

10.5.4. Exercise 2

Implement a version of a solver for the Knapsack Problem using the back-tracking technique (similarly to how n-queens problem has been solved), by progressively selecting subsets of items, optimising for the weight and recording the maximal price the price (and the set of elements that delivered it). Test your solution as in Exercise 1.

10.5.5. Exercise 3

In this exercise you will be asked to implement a solver for Boolean satisfiability problem using both the brute-force and the backtracking technique. Take the following data type defining syntax for boolean formulae:

type formula =
  | Var of string
  | And of formula * formula
  | Or  of formula * formula
  | Not of formula

For instance, OCaml’s value not x && (y || not z) can be encoded as follows:

And (Not (Var "x"),
     Or (Var "y",
         Not (Var "z")))

Implement thew following functions:

  • eval : formula -> (string * bool) list -> bool for evaluating the boolean value of a formula (true or false) given the list of bindings, mapping the variables occurring in the formula to their boolean values.
  • generate_random_formula : string list -> int -> formula for creating a random formula featuring variables from a given list of names, as well as other connectives. Use the int parameter to control the size of the forumla.
  • solve_brute_force : formula -> (string * bool) list option – a function for finding a list of substitutions from variable names that make the given formula evaluate to true or None if no such list exists. Do it by enumerating all possible assignments to variables.
  • solve_backtracking : formula -> (string * bool) list option – the same solver as before, but implemented by means of back-tracking, assigning individual values to the involved variables and partially simplifying the forumla as it goes (as discussed in the class).
  • Test both solvers using generate_random_formula and compare their performance on large formulae.

10.5.6. Exercise 4

Improve the encoding format of DNA strings so instead of storing the overall length (and wasting 30 bits) in the beginning, it would store a 2-bit number \(P\), indicating how many of 2-bit sequences (0-3) will be appended for padding at the end. Notice that \(P\) will depend on the length of the DNA sequence, and storing \(P\) will impact the value of \(P\), as it consumes 2 additional bits.

Read \(P\) when deserializing and then use the same trick as when reading ASCII strings for reading a DNA from the rest of the file. As added \(P\) 2-bit 0-sequences (for padding) at the end would contribute “junk” 'A' characters at the end of the decoded DNA, use the stored information to strip them in a deserialized DNA string.