This is what the first two and last pages of the exam will look like. Please read the instructions carefully, so that you can save the time during the exam, and so that you don't run into unnecessary difficulties due to not being aware of the instructions and rules.

A couple of “last minute tips” on this; do check carefully the second page of the exam (see link above) for instructions. For some of the questions (the “explain why” or “show/prove that” sort of questions, the notion of “you have to justify the answer” does not apply. For the rest, when nothing explicit is said, even if it says “show your work”, you can decide to just write the answer without justification, and that means that you will have a deduction of 20% the value of that question (1 or 2 marks, for questions worth 5 or 10 marks, respectively).

There are special cases in which the math or the procedure is so easy that can be done in our heads --- for those cases, it is explicitly said that you don't have to justify the answer (that's the case for two of the questions in the exam);

There are also special cases where the answer can be so trivially obtained by visual
inspection that in those cases you're *not allowed* to write an answer without
justification; obvious examples are: Shortest path in a graph; if you don't show the steps
of Dijkstra's algorithm, obviously you can't expect partial marks (seeing the shortest path
by visual inspection is too easy); same thing for minimum spanning trees (both Prim's or
Kruskal's algorithms would have to be shown step-by-step).

In general, the instructions would say *you must* justify/explain/show your work
(the use of the verb “must” is the key detail here). There are three questions
that are in this category.

Please do keep in mind that if an answer is given with no justification, and the answer is not correct (as in 100% strictly equal to the correct answer), you get no part marks for that particular question. You can try to be brief in your justifications, but try to avoid vague explanations or too general sentences that don't specifically explain why your answer is whatever it is.

Wednesday and Thursday, you can see the TAs for any assistance:

Wednesday: 4-5PM: Mahsa (DC-3577R); 5-6PM: Nima (DC-3577A)

Thursday: 11-12: Nima (DC-3577A); 2-3PM: Mehdi (DC-2542); 3-4PM: Keyvan (E5-5117); 4-5PM: Mahsa (DC-3577R); 5-6PM: Ahmad (E5-4111)

I will be available at least Thursday afternoon (say, from 1PM), but you can e-mail me if some other time works better for you

The formula for ID scrambling (hashing) is as follows: Take last 6 digits of your
student ID; multiply times **281**; take last 7 digits of result.

These are some *suggested* solutions. Different solutions
could be applicable and equally acceptable.

- Problem set —
Corrections made – 2012-02-22 16:20:
- Typo fixed in question 5 (the innermost loop had j in the condition and increment, when it should be k)
- Added clarification on question 6 (expanded on the behaviour of binary_search)

- Suggested solutions to some of the problems

For the midterm, see also course slides from Feb 17 (last class before the exam) for tips and information on the midterm.

In particular, do remember that there is a bonus marks question (2 points out of 100) on the
article *Getting it Wrong: Surprising Tips on How to Learn* (and do notice that it spans two pages). I would think that
there are none of you who thought that I was joking. But in case there were:
no, *I was not joking*!!

Tue | Wed | Thu | Fri | |
---|---|---|---|---|

10AM - 11AM | Mehdi (DC-2542) |
Teng (EIT-4129) | Teng (EIT-4129) | Teng (EIT-4129) |

11AM - 12PM | Keyvan (E5-5117) | -- | Keyvan (E5-5117) | Keyvan (E5-5117) |

1PM - 2PM | Nima (DC-3577A) | Nima (DC-3577A) | Mehdi (DC-2542) |
Ahmad (E5-4111) |

2PM - 3PM | Nima (DC-3577A) | -- | Mahsa (DC-3577R) |
Mahsa (DC-3577R) |

3PM - 4PM | Ahmad (E5-4111) | Mehdi (DC-2542) |
Ahmad (E5-4111) | Mahsa (DC-3577R) |

I will be available the whole week; normally, between 1PM and 3PM; e-mail me if some other time works better for you.

Digging up a little bit on this, I found out that it is not a departmental
requirement, but rather, a * recommendation*. The
rationale being two-fold: (1) Avoid distractions/disruptions during the exam; and
(2) As an “anti-cheating” technique — yes, quite
unfortunately, there are those who ask bogus questions to the proctor(s) to distract
them and allow their accomplices to then freely exchange/copy answers!

I actually see several additional inconveniences:

- Asking questions / asking for clarifications can (and most likely will) give an unfair advantage to those who ask the questions (the TAs could inadvertently give away too much when answering, or subsonsciously, through body language).
- The TAs could inadvertently/unintentionally end up answering quite incorrectly, and actually making things far worse for the person who asks the question
- It simply is unfair — every single student should be subject
to the exact same conditions; if one person gets a clarification,
*every single person*should get the same clarification, or neither one does; since the former introduces a big logistic problem, in addition to representing an annoying distraction, the latter makes a lot more sense

Now, again: to me, by far the most important consideration is the fact that asking questions is a disruption for those around the person that asks the question(s).

So, the rule will stand (including the penalty for not respecting it! remember that the idea is to avoid distractions/disruptions; so, answering with “what part of no questions allowed did you not understand” unfortunately is not enough (since the disruption already took place!). If there is no strong discouragement to ask the questions, then there will be questions with the side-effect of the disruptions!

However, in the spirit of addressing your concerns and in the spirit of compromising,
I will include an extra page at the end with a short form to report problems (things like
what some of you guys pointed out in class: what if there is a question missing? what if
there is a page missing? what if a given question *really* is incorrectly written
to the point that it simply is not possible to guess what you're being asked... etc.)

So, you will be allowed to call one of the TAs (or myself) and give them the form,
*in complete and absolute silence*, so that I will personally look at it and
address it if necessary. If after reading it I believe that the request/report is
unjustified, then I would ignore it.

Also importantly: do keep in mind that you can write any assumptions and answer the question based on those assumptions — if you make a reasonable case that the question was not clear, ambiguous, etc., AND if your assumption makes sense, there is no reason why you wouldn't get full marks for the question, even if your answer was not the answer originally expected.

These include a few aspects beyond what we covered in class — needless to say that if we did not cover it in class, it will not appear in the midterm. Still, the notes should be useful, as it goes over the material in more detail than what I include in the slides.