COMP251: Final Review
Jérôme Waldispühl
School of Computer Science
McGill University
Overview of the exam
• 11 questions.
• 200 points + 30 bonus
• 20 point True or False (Warning: -1 penalty for wrong answers!)
• 20 point for multiple choices answers.
• 28 points for short answers (no justification)
• 97 points questions/applications
• 35 points + 30 bonus problems
• Unless specified, all answers must be justified.
• Partial answers will receive credits.
• The clarity and presentation of your answers is an integral part
of the grading. Be neat!
• Books and electronic devices are not allowed.
• 2 crib sheets (4 pages).
Advices
• When practicing, do not look at the solution immediately.
• Look at resources from other similar classes (e.g. Mike Langer
COMP 251 web page, OCW at MIT, etc.)
• At the exam, do the questions you know the answer to. Do not
spend time on the difficult ones. You will do them after.
• Sleep well!
MIDTERM SOLUTIONS





Suppose that we are given a weighted, directed acyclic graph G = (V,E) in which edges
that leave the source vertex s may have negative weights, all other edge weights are
strictly positives.

MASTER THEOREM
• ! " = 3 % ! &' + "'
• ! " = ! &' + 2&
• ! " = *' % ! &' + *&
• ! " = 4 % ! &' + "'
• "' = Ω "-./0 12('4-./0 1)
• 3 % &' ' ≤ 17 % "', " ≥ 0 (case 3) ⇒ Θ "'
• 2& = Ω "-./0 *2*
• 2=0 ≤ *' % 2& = 2&4*, " ≥ 2 (case 3)⇒ Θ 2&Theorem does not apply (a<1)
"' = Θ "-./0 7 % log " P (case 2)⇒ Θ "' % log "
DYNAMIC PROGRAMMING
Knapsack problem
False start…
New variable
Dynamic programming algorithm
Example
Analysis
AMORTIZED ANALYSIS
Dynamic tables
Scenario
• Have a table - maybe a hash table.
• Don’t know in advance how many objects will be stored in it.
• When it fills, must reallocate with a larger size, copying all
objects into the new, larger table.
• When it gets sufficiently small, might want to reallocate with
a smaller size.
Goals
1. O(1) amortized time per operation.
2. Unused space always ≤ constant fraction of allocated space.
Load factor α = (# items stored) / (allocated size)
Never allow α > 1; Keep α > a constant fraction Goal 2.
Table expansion
Consider only insertion.
• When the table becomes full, double its size and reinsert all existing items.
• Guarantees that α ≥ ½.
• Each time we insert an item into the table, it is an elementary insertion.
TABLE-INSERT(T,x)
if size[T ]=0
then allocate table[T] with 1 slot
size[T]←1
if num[T]=size[T] then
allocate new-table with 2 · size[T] slots
insert all items in table[T] into new-table
free table[T]
table[T]←new-table
size[T]←2·size[T]
insert x into table[T]
num[T]←num[T] + 1 (Initially, num[T]=size[T]= 0)
Aggregate analysis
• Charge 1 per elementary insertion.
• Count only elementary insertions (other costs = constant).
ci = actual cost of ith operation
• If not full, ci =1.
• If full, have i−1 items in the table at the start of the ith operation.
Have to copy all i − 1 existing items, then insert ith item ci = i.
n operations ci = O(n) O(n2) time for n operations
Total cost =
Amortized cost per operation = 3.
ci =
i if i−1 is power of 2
1 Otherwise
"
#
$
%$
ci ≤ n+ 2 j
j=0
logn"# $%
∑
i=1
n
∑ = n+ 2
logn"# $%+1 −1
2−1 < n+ 2n = 3n
Accounting method
Charge $3 per insertion of x.
• $1 pays for x’s insertion.
• $1 pays for x to be moved in the future.
• $1 pays for some other item to be moved.
Suppose we’ve just expanded, size=m before next expansion,
size=2m after next expansion.
• Assume that the expansion used up all the credit, so that there’s
no credit stored after the expansion.
• Will expand again after another m insertions.
• Each insertion will put $1 on one of the m items that were in the
table just after expansion and will put $1 on the item inserted.
• Have $2m of credit by next expansion, when there are 2m items
to move. Just enough to pay for the expansion…
The End
Do not focus on grades, what you learned is more important.
Be curious. Get involved in projects. You now have the tools and
knowledge to do interesting things.
Questions? [email protected]

欢迎咨询51作业君