Some students are unaware of the deep cultural references in assignment 4. To fill this lacuna in your knowledge, see here (or here for pictures).
For question 25.1-6 on assignment 4, you are given the adjacency matrix of the graph and a matrix L that is already filled in so that L[i,j] is the weight of the shortest path from vertex i to vertex j. You must compute the matrix Pi, which is defined on page 621. Further note: you can also assume the matrix of edge weights is given.
The drop boxes for assignments have been moved to the new Computer Science Building. They are in the hall across from the Prism lab on the first floor.
Correction to solutions for 4(b) on assignment 2: Each occurrence of "+1" should be replaced by "-1". (The variable k represents the number of nodes in the left subtree, so the number of nodes in the right subtree is n-k-1.)
The exam schedule has been posted.
For question 2(b) of assignment 3, it will make the TA's life easier if you put your answer in a table with the following standard format:
| j
| 1 2 3 4
----+-----------------
1 |
i 2 |
3 |
4 |
filled in with 16 pairs. If the entry in row i, column j is (A_k, A_l)
that means that when an elt of A_i is compared to an elt of A_j and the
elt of A_i is found to be the smaller of the two, the elt of A_i moves
into A_k and the elt of A_j moves into A_l.In question 2 on assignment 3, "the algorithm" in parts (a), (b) and (c) refers to the arbitrary comparison-based algorithm S. I.e. you must prove a lower bound on the number of comparisons performed by any comparison-based algorithm that finds the minimum and maximum elements of E.
For question 1 on assignment 2, (0,0)^0 is undefined, and (a,b)^0 is (1,0) if (a,b) is not (0,0).
For question 2 on assignment 2, the algorithm for which you should prove the lower bound is simply
H = empty heap
for i = 1 .. n
MAX-HEAP-INSERT(H, element number i)
(see page 140).
For question 3 on assignment 2, your algorithm should run in O(n log f(n)) time or better.
Students in the daytime section should hand in their assignment at the beginning of class on the due date.
For question 6 on assignment 1, just use the definition of non-decreasing functions: to say R(n) is non-decreasing just means that, for all natural numbers n, R(n) is less than or equal to R(n+1). (Don't start messing around with derivatives.)
For the last question on assignment 1, you can assume that each entry in the array is represented using exactly log_2 (n+1) bits: leading 0's are added to fill in all the bits if necessary. For example, if n=7, a possible input would be A=[001,111,000,010,100,110,011]. (Note that A is not sorted.)
For students using the first edition of the text: ordinarily, it will be up to you to figure out the differences between the two editions. I have asked the library to put a copy of the second edition on reserve, but it isn't there yet. So just this once, I will post problem 4-2 from page 85 of CLRS, which appears on your assignment:
An array A[1..n] contains all the integers from 0 to n except one. It would be easy to determine the missing integer in O(n) time by using an auxiliary array B[0..n] to record which numbers appear in A. In this problem, however, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]," which takes constant time. Show that if we use only this operation, we can still determine the missing integer in O(n) time.