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.*

- The
*All Nearest Smaller Value*problem (ANSV) is to identify for each number*a*, the_{i}*least**j such that j > i*(0 <=*i,j < n*) and*a*<_{j}*a*. It is undefined if no such_{i}*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.

- 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..n^{2}. 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*.

- 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.

- Suppose
you are given
*n*simultaneous equations in*n*variables*x*to_{1}*x*with real valued coefficients (i.e., floats). It is customary to represent the system of equations as_{n}**Ax = b,**where**A**is an*n*x*n*matrix**x****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*x*from_{1}*n*, by subtracting an appropriately multiplied version of the first equation from each of the equations such that the coefficient of*x*in equations 2 to_{1}*n*becomes zero. This procedure is repeated by eliminating*x*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_{2 }*x*and then iteratively plugging in this solution to find the solutions for_{n}*x*_{n-1}, x_{n-2}, É, x_{1}.