For question 4 on A3, a solution for the problem is called "legal" if it is a single tree that has m leaves, and each leaf is labelled by one of the arrays (A_1...A_m), and no two leaves have the same label. In other words, a legal tree gives you a correct way to merge all the arrays by doing pairwise merges.
For 4(b) on A3, you should give a formula for cost(T)-cost(T'). In the formula, you're allowed to use depth_T(v_1), depth_T(v_2) and the values of some nodesof the tree. No other variables should appear in the formula.
NOTE: The TAs will have an office hour on Tuesday, March 5 at 7:00p.m. in room 2017 of the Computer Science Building. That's a good opportunity to talk to them if you want to ask about the marking of your assignments or test.
Marks for A2 have been posted. Students in daytime section should type courseInfo 3101 M. (Note M instead of A.) Students in evening section should type courseInfo 3101 N. (Note the space!)
For Q1(b) on A3: Fix the values of n and t. Then consider all possible output sequences (for inputs of size n) whose last element is equal to t. How many such output sequences are there? (Or equivalently, if we fix the values of n and t, how many different output sequences are there for inputs of length n where the maximum element in the input appears in position t?)
For Assignment 2, question 3: In the line where z_1 is concatenated with (z_0 mod h), the latter number should be thought of as having floor(n/2) bits. I.e. if (z_0 mod h) has fewer than floor(n/2) bits, you should think of it having extra leading 0's to make it the right length.
IMPORTANT: For Assignment 2, question 2: There is a mistake in the textbook. The invariant given there is not really strong enough to make the proof work nicely. Instead you should use the following invariant: At the start of each iteration, every node in the heap, except possibly A[i], is less than or equal to all of its ancestors. Sorry for the confusion.
Marking scheme for assignment 1:
5 for each part of #1 and #2 (2 for right answer, 3 for proof)
7 marks for #3
8 marks for #4
5 marks each for #5 and #6.
So the total is out of 55.
Example for question 4 on assignment 2: Suppose f(11) = 5 and the input to your algorithm is S = [12 5 10 21 4 17 19 7 25 1 9]. Then your algorithm should output 12, 5, 10, 7, 9 (in any order). This is because 10 is the median of S and the 5 numbers listed are the 5 (=f(11)) elements of S whose numerical values are closest to 10.
What's the median of an even number of elements? For the purposes of this assignment, assume that the median of 2k elements is just the kth smallest element. (Thus the median of n elements is the (ceiling(n/2))th smallest element, whether n is odd or even.)
Note: some of the material needed for question 4 on assignment 2 will not be covered until the first lecture after reading week. If you want to get started on the problem before then, you may use the following fact, which will be proved in class right after reading week:
There is an algorithm Select(A[1..n],k) that selects the k'th smallest element of the array A in O(n) time (where 1 <= k <= n). If you want to read ahead about this topic, see Chapter 9.
For assignment 1, question 6: the base of the logarithm is e. (In mathematics, the base of a log is usually assumed to be e unless stated otherwise.)
For assignment 1, question 1(b): Note that the factorial function is really only well-defined for natural numbers. Thus it doesn't make sense to talk about something like (n/3)!, where n is an arbitrary integer.
Question 2(c) on assignment 1 is quite challenging. Don't panic if you can't solve it.