MATH 317 Lecture 6: CPSC_320__Amortized_Analysis_I
Document Summary
Beginning of class announcements: assignment 5 was due on october 30. October 30 and 3:30pm on october 31 will not be considered late: assignment 6 has been posted and is due on monday, november 10, the second midterm will be on wednesday, november 12. No material which was examined on midterm 1 will be examined explicitly in midterm: in other words, the examinable material for midterm two starts after the cut-o for midterm one. Amortized analysis is topic which is not covered well in most standard algo- rithms textbooks. We will follow the handout at http://www. ugrad. cs. ubc. ca/~cs320/2014w1/handouts/aa-nutshell. pdf for a reference and chapter. 17 of the most recent edition of cormen"s introduction to algorithms as ref- erences. Example: we are given a stack with the following operations: Push(x), x is the item which we push. Multipop(j), j is the number of elements we want to pop.