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.
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.
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.
The second (and mercifully final) examination is scheduled for 7 December at 9 am in the Sports Complex. More information will appear here in due time.