Recall that the assignments can be done in groups of up to three students. All the collaborators must be currently enrolled in the course. A single joint solution must be submitted for each group, including the names and student numbers of all the collaborators. Your answers are due at the end of the class on the due date.
The preferred submission is on paper. You can also submit a single PDF containing all your answers by email. Please type your answers or write them by hand neatly. If submitting a scanned document by email also make sure that you provide a quality scan. Submissions rendered obscure by bad handwriting or poor scanning (low light, low contrast, blurry, etc.) will not be marked.
Either way your solution is due at the end of class on the due date. Late submissions will be accepted subject to a penalty of 10% per day late until my solutions are posted on the course’s Web site (which can happen as soon as two days after the due date). No submissions will be accepted afterward.
It goes without saying that a correct answer with no justification will give you full marks (unless the justification is explicitly required in the question), while an incorrect answer with no justification will give you no marks. However, there is also a middle ground: a justification that makes sense may give you partial marks even if the answer in incorrect.
For the purpose of the assignments as well as written tests the only acceptable ways to describe an algorithm are pseudo-code (preferred) or actual code. Textual descriptions in particular are not acceptable.
Here are my answers to the examination questions as well as some statistical data on the grades.
The mid-term examination will take place on 29 October during the regular class time.
This examination covered the first half of the term, up to divide and conquer algorithms (inclusive). You should expect questions similar with the ones asked in Assignments 1 to 3.
There is rather limited variance for the possible questions related to the first four sections (up to and including graphs), so beside understanding the matter solving the assignments should be sufficient practice. By contrast, a huge amount of possible questions exist for divide and conquer algorithms, including but certainly not limited to selecting and sorting. Again understanding the matter and solving Assignments 2 and 3 should be sufficient preparation, but if you feel the need for more practice try the following exercises from the textbook (starting on Page 44): 11, 13, 14, 16, 19, 22, 24, 25, 33, 37, and 39. Note however that (a) these questions are harder than what you would likely see in the exam, and (b) I am not going to provide advice on these questions.
Each question on the examination paper will be assigned a number of marks that also serves as an estimate of the number of minutes you are expected to spend in answering the respective question. The following is such an estimate for the questions in the assignments:
Assignment 1:
Assignment 2:
Assignment 3:
A general rule of thumb for the kind of algorithms considered in the examination you should be able to design them in 15-20 minutes, prove them correct in 10-15 minutes, and calculate their running time in less than 5 minutes.
I am satisfied that I covered the whole matter reasonably well in the assignments (or more precisely, that I cannot cover it better in another set of questions), so I will not provide a mock examination.
Note that there are generally three phases in the development of an algorithm: design, proof of correctness, and running time calculations. They are grouped together in the assignments, but it is very possible for them to be separated in the examination. For example, I might ask you to prove the correctness and/or analyze the running time for an algorithm that is given in the question. I might also ask you to develop an algorithm without proving it correct. One way of another you can rest assured that all the three phases of algorithm design will be covered.
The second (and mercifully final) examination is scheduled for 7 December at 9 am in the Sports Complex.
This examination covered the second half of the term, starting from greedy algorithms (inclusive). You should expect questions similar with the ones asked in Assignments 4 to 6. Like in Assignment 4, I might ask some specific question about the particular problem we spend a not insignificant time on namely, minimum-cost spanning trees.
As before, a huge amount of questions exist for greedy algorithms, dynamic programming, and backtracking (Google is your friend). The extent to which we covered the complexity theory by contrast limits the kind of questions I can ask on this matter to something related to nondeterministic algorithms and perhaps a question about reductions such as the meaning of the existence (or absence) of a certain kind of reduction.
Understanding the matter and solving the respective assignments should be sufficient preparation for the exam, but if you feel the need for more practice try some of the following textbook exercises:
This all being said, note that (a) the textbook questions are harder than what you would likely see in the exam, and (b) I am not going to provide advice on these questions.
The only thing whose coverage is unbalanced in the assignments is greedy algorithms (due to Question 3 in Assignment 4 turning out to be different from what I intended). I therefore suggest that you try a few more greedy solutions. Note in passing that my mistake in Assignment 4 illustrates the weak point of greedy algorithms: One needs to be absolutely sure that a greedy approach will work for the problem at hand before even thinking about a greedy algorithm. In many circumstances the suitability or unsuitability of a greedy approach is not obvious. I might throw in a question in this respect so I recommend that you revise the proof in the famous Question 3 and also try your hand at similar proofs for different problems.
As for timing expectations, the rule of thumb that you should be able to design an algorithm in 15-20 minutes, provide a proof (of correctness, of nonexistence of a greedy solution, etc.) in 10-15 minutes, and analyze the running time of an algorithm in less than 5 minutes continues to hold. That is the case for all the assignment questions so I am not going to provide individual assessments of expected time for them individually.
Recall that the examination is open book, meaning that you are allowed to use any kind of documentation. Electronic devices are not permitted. You are not allowed to share any material with your colleagues. Here you can find some generic information about open book exams. I strongly recommend that you (a) index well your material so that you can find the information you seek in short order and (b) ignore your material as much as possible (ideally, completely). If you stop every time to look things up you will most likely run out of time. Instead of bringing your textbook and/or lecture notes I also recommend that you prepare some cheat sheets (no more than 4 pages) summarizing key concepts; this is going to save you considerable time during the exam.