The objective of this assignment is to give you some experience in programming with arrays in the imperative style, and to develop programs by first writing down the loop invariants and only then writing the code.  Some of the programs involve conceptual mappings between 1-dimensional and 2-dimensional arrays.  The code you need to write should only use 1-dimensional arrays, though the problem may conceptually use 2-dimensional arrays.  This requires a mapping between indices (i,j) and k and vice versa.  An algorithmic technique that you may encounter is dynamic programming, in which finding the solution to a problem involves solving overlapping subproblems, and incrementally combining their solutions.  You may write the code in OCaml or Java.  In each of the following problems, you MUST write down the loop invariant whenever you write a for or while loop.


  1. The All Nearest Smaller Value problem (ANSV) is to identify for each number ai, the least j such that j > i  (0 <= i,j < n) and aj < ai. It is undefined if no such j exists. For example, in the sequence 8,9,7,5,6, (indexed as 0,1,2,3,4), the ANSV's are 2,2,3,u,u, where u denotes ``undefined'' (the ANSV for the last element is always undefined). Note that you cannot change the order of the input sequence, since ANSV's depend on this ordering. Write an efficient (don't search for each element separately) OCaml (or Java) program that computes the ANSV's by considering the elements from left to right and by keeping track of those elements for which the ANSV's are yet to be determined.   Hint: Clearly, these elements form a monotonically increasing subsequence.



  1. Many board games like Snakes-and-Ladders, etc., have a  n x n  (e.g., 10 x10) board, in which the squares are numbered 1..n2.   Moves are made by rolling a  die (singular for “dice”), which is a cube on each face of which is a (unique) number of dots between 1 and 6.    You have to write an efficient program that computes, for each j (1 <= j <= 100), the number of different ways that one can reach the square numbered j (you do not need to list the different ways).   For example, one way to reaching the square numbered 7 is by rolling 4 and then 3, and another way is by rolling the sequence 1-3-1-2.   Hint:  Having computed the number of ways for reaching a position j, increment the number of ways to reach positions by one roll of the die from j.   



  1. An interesting sorting technique uses the following idea:  consider the array which is to be sorted as being a m x n matrix (m rows and n columns).  Now sort the rows as follows:  sort the first row in ascending order, the second row in descending order, the third in ascending and so on, sorting the alternate rows in opposite order.  Now sort each column in ascending order.     Repeat this process until there is no change to the matrix.    You may use any simple sorting technique for sorting the rows and columns, and you will need to devise a way (e.g., by using a single Boolean flag) to indicate whether the matrix has undergone a change or not.


  1. Suppose you are given n simultaneous equations in n variables x1 to xn with real valued coefficients (i.e., floats).   It is customary to represent the system of equations as Ax = b, where A is an n x n matrix x and b are n x n matrices (i.e., vectors).  A common way to solve the system of equations, i.e., to calculate the vector x, is by the process of repeatedly eliminating variables from equations:  first we eliminate x1 from equations 2 to n, by subtracting an appropriately multiplied version of the first equation from each of the equations such that the coefficient of x1 in equations 2 to n becomes zero.  This procedure is repeated by eliminating x2 from all following equations by taking the second equation and subtracting a scaled version of it from all following equations.   It is possible for the equations not to have a unique solution (when does that happen?).   The solution is calculated by taking the solution for xn and then iteratively plugging in this solution to find the solutions for xn-1, xn-2, …, x1.