Homework assignments

You can either drop the assignment off in a wednesday tutorial, or in the drop box which has been set up in front of room S625.
Remember to submit the signed statement that is mentioned in the course information sheet with your assignment -- otherwise your assignment will not be marked!
At St.George campus there is an enriched tutorial which covers harder questions. You may find it beneficial to work on these questions, but they are not to be handed in, and they will usually not be discussed in our tutorials.
IMPORTANT: If you have used ANY outside help on the programming part of assignment 2 or 4, like down-loading RBT source-code from the web for use in your own program, then you have to acknowledge this. Failure to acknowledge using the work of somebody else is plagiarism and will be dealt with harshly.

Assignment 1 ( ps , pdf ), due Wednesday September 27, 3PM.

Enriched Assignment 1
Q1: C is a SET, so it will not contain repeated elements.
Q2: in the algorithm it should be "j <- j+1" instead of "j -> j+1".
Q2e: For example Pr(x[2]=2) is the probability that the second coordinate in the randomly chosen array (according to the probability space) is 2.
Q4: Every node contains one separate bit of information for every path. Thus if v is a leaf (or a node which has only one leaf as a child) then one bit is stored. If v has two children, both of them leaves, then 2 bits are needed and so on. For this question finding the exact answer is no harder than finding an approximate one.
Q5: The main difference between the partition of our algorithm in class and the algorithm in the book is that in the book the set is split into 2 parts, whereas in class we split the set into 3 sets. (This is the main difference between RANDOMIZED-SELECT on the one hand and RANDOMIZED-SELECT2 and RANDOMIZED-SELECT3 on the other hand.)
Q5: PARTITION is a subroutine for RANDOMIZED-PARTITION, so that changing various PARTITION algorithms still makes the overall algorithm a randomized one.
Q5: The difference between RANDOMIZED-SELECT2 and RANDOMIZED-SELECT3 is the difference between using 2-way and 3-way comparisons. In a 2-way comparison x:y, the answer is <= or >. In a 3-way comparison x:y the answer is one of <, > or =.
Q5: I just found out that there seems to be no predefined 3-way comparison in some of the permitted languages. For this reason we will drop RANDOMIZED_SELECT3 from the question. Those of you who have implemented this already will receive some amount of extra-credit for it.

Assignment 2 ( ps , pdf ) due Wednesday October 18, 3PM.

The grading scheme for Assignment 2 (99 marks total): (see also Luke's webpage)
- Q1: 10+10 = 20
- Q2: 5+5+10 = 20
- Q3: 2+5+5+8 = 20
- Q4: 40
Enriched Assignment 2
Q3a): you have to say which one of gray/white corresponds to red and which to black. Explain why this is a correct choice. Also explain if the other way around would work or not.
Q3d) mistake: The tree in which you are supposed to rotate Turgeon to the top is the one obtained in 3c) and not the original tree.
Q4:
- Acceptable languages are C, C++ and java.
- The programs must run on Unix machines (like fissure).
- You have to submit both a hard copy of the code and the identical original file to a submission directory.
- Submission information.
- Input/Output format information.
- There is a mistake in the I/O information: the example given should return
  3.34
  0
  since the second displayheight ought to return 0.

Assignment 3 ( ps , pdf ) due Thursday November 9, 3PM (drop box).

The grading scheme for Assignment 3 (100 marks total):
- Q1: 8+7+10 = 25
- Q2: 6+6+4+6+8 = 30
- Q3: 5 each = 20
- Q4: 5 each = 25
There will be no further extension beyond the one given above. You will receive NO credit for the assignment if you do not submit it by 3PM sharp, since the Erindale tutorials will discuss the solutions.
The PHP (pigeonhole principle) can be useful for your assignment: If n pigeons fly into m holes (usually n>m), then some hole must contain at least n/m pigeons.
Q1a: The fact that h₁, ... , h_i are constant means that if x and y are from U_i then h₁(x)=h₁(y), h₂(x)=h₂(y), ... , h_i(x)=h_i(y). In other words the elements from U_i collide no matter which one of these i functions you pick.
Q2b-e: In this problem all addition is done modulo 2, since we are working over Z₂, so here 1+1=0.
Q2d: One valid vector x in S (part d) is 110010, since x₁+x₂=1+1=0, x₃+x₄+x₅+1=0+0+1+1=0 and x₆=0.
Q4c: There is no mistake in the statement. Take a good look at the anlysis of the binary counter on pg 360, to get a better understanding how this works.

Assignment 4 ( ps , pdf ) due Thursday November 23, 3PM (drop box).

The grading scheme for Assignment 4 (100 marks total):
- Q1: 25
- Q2: 21
- Q3: 3 each = 24
- Q4: 30
The extension on the assignment again is up to 3PM and no minute extra, so make sure that you are on time, since otherwise you will receive a zero for the assignment.
Remember to submit the signed statement that is mentioned in the course information sheet with your assignment -- otherwise your assignment will not be marked!
Here are the program specifications.
For those students who would rather work on more theoretical questions, here is an alternative to question 4 which is more challenging mathematically, but does not involve any programming: ( ps , pdf ).
Q1b): this had some typos that have now been fixed.
Q2: The data structure does not need to support MAX (like a PQ), only DELETEMAX and INSERT.
Q3: For the LINK operation given in the book the following instruction needs to be inserted as the new first line in order for everything to work properly: If x=y then return
Q4: your output MUST be to specifications, even in the case that your program does not work properly. In other words give the improper output in the correct format, if necessary.
Q4: you can not necessarily assume that there is a fixed bound on the number of clones, or on the size of their ID numbers. Be sure to explain in part a) why you think your data structure is reasonable.
Q4: Your print operation does not have to be efficient (as long as it runs in time polynomial in the size of the input that suffices), and it does not need to return the keys in the contig in any particular order.
Q4: Don't worry about the fact that if the program reaches EOF, then the last line is printed twice. In the autotesting there will be a "q" at the end of the file.

Assignment 5 ( ps , pdf ) due Monday December 4, 7PM (lecture).

The grading scheme for Assignment 5 (100 marks total):
- Q1: 5 each = 25
- Q2: 5 each = 20
- Q3: 25
- Q4: 30
- Q5: 20
As you can see this adds up 120 so that one question is effectively a bonus.
There will be no extension for this assignment, since it is due on the last day of classes.
Q2: Two spanning trees are edge-disjoint if there is no edge that is in both of them. k spanning trees are pairwise edge-disjoint if there is no edge that is in more than 1 of the k trees.
Q2: We are only talking about graphs on at least 2 vertices. The 1-vertex graph has infinitely many (identical) pairwise edge-disjoint spanning trees, so that we do not consider it.
Q4: You do not have to draw all intermediate graphs/trees. It is sufficient if you give a table that contains, for every intermediate step, the relevant edges and important variables like d[v].
Q4: The tie-breaking rule only makes sense for Kruskal's algorithm (see next point). For Prim's and Dijkstra's algorithm simply pick the vertex with smallest label (i.e. vertex 1 would be preferred over vertex 2).
Q4: In some cases Kruskal's algorithm has the choice of which edge to take. To break this tie, sum up the labels of the endpoints. For example: if you have to choose between edge (0,1) (which has weight 8) and edge (2,5) (which has weight 7), then you will take (0,1) since 0+1=1, whereas 2+5=7 (which is larger). REMARK: should the edges still be tied after this procedure, then take the one with smaller difference between the endpoints (i.e. (2,3) would be preferred over (0,5)).

Miscellania

Midterm Raw Marks. The recorded mark for the midterm is the raw mark plus 12.
The Final exam was Monday, December 11, 2-5PM in room H305.
You were responsible for all the material that was done in class, in tutorial or on homework assignments. In terms of sections in the book this is most accurately, but not completetly, described as follows:
- 1-6.2, 7-9, 11-15, 18, 22-23.3, 24-25.2
Here is a copy of last years final ( ps , pdf ). I was not involved in teaching this course prior to last year, so the exams from other years may not be as valuable for you in preparing for this years final. I will go over questions from this exam in the review session if you ask me to -- please save all your questions on it until the review session.
The exam is closed book and notes. The only aid you are allowed to bring is a two-sided, hand-written (not computer-typed or photocopied) cheat sheet (8.5 x 11).
Remember to bring your Photo identification card (T-card).