Homework 4

1. Write an OCaml function which takes a list of elements and an element as arguments, and returns the index of the last occurrence of the element.
2. Define a binary search tree using variant types and product types. Define a search function that takes a binary search tree and a key as arguments, and returns true if the key is found, and false otherwise.

3. Move-to-front encoding: You are given a list table initially set equal to ['a';'b';'c';'d';'e';'f';'g';'h';'i';'j';'k';'l';'m';'n';'o'; 'p';'q';'r';'s';'t';'u';'v';'w';'x';'y';'z'] and a string s.

   Move-to-front encoding works as follows.

   1. Initially set the output list to empty.
   2. For i from 0 to (len s)-1 do
      1. let c be the i^th character of the string s
      2. Find the index of c in the current table, and add it to the output list.
      3. Transform table by bringing c to the front of the list, pushing back the elements in table from the first position to the index of c back by one position. Elements after c in table remain unchanged.
   3. Return the output list.

   In OCaml, you can get the character at the first position of a string s, for example, by the expression (String.get s 0).

4. You are given a Tic-Tac-Toe game board in the form of a list of 3 rows, where each row is a list of 3 characters. Each character may be a ' ', a 'o' or a 'x'. Given such a board, output true if the game is a winning position for the player playing 'x'.