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