CSCI 4117 Study Guide - Fall 2018, Comprehensive Midterm Notes -
12 Oct 2018
School
Department
Course
Professor
CSCI 4117
MIDTERM EXAM
STUDY GUIDE
Fall 2018
Amortized Analysis
1. What is amortized analysis
(1) To amortize means to pay off over time
(2) Time required to perform a sequence of operations is averaged over all the operations
(3) An amortized analysis guarantees the average performance of each operation in the worst case.
Average- case analysis.
2. Why amortize?
(1) Can be used to show the average cost of an operation is small, even though a single operation can be costly.
(2) Extra flexibility of amortized bounds can lead to more data structures
Eg. Balanced search trees VS. Splay trees
3. Aggregate analysis
(1) Steps
Show off all , a sequence of operations
Uses worst case time in total
The amortized cost per operation is
(2) Each operation has the same amortized cost
(3) Example: Stack with Multipop
Problem : stack
MULTIPOP(S,k)
while(k!=0) and not STACK- EMPTY(S) do
{
POP(S)
K<- (k- 1)
}
Analysis of a sequence of , and operations on an initially empty stack.
:
Worst case running time of any operation:
Total cost of operations:
Issue: not tight
Considered each operation individually
find more resources at oneclass.com
find more resources at oneclass.com
Aggregate Analysis
Observations : Each object can be popped at most once for each time it is pushed
The times can be called on an initially empty stack including calls within is at most operations, which is
The total cost of / / on an initially empty stack:
Amortized cost of any operation:
(4) Example: Increment a binary counter
Problem
- A counter that counts upward from
- Stored in an array of bit
- : Scan bits from right to left
Zeroing out s until it finds a flip the to
INCREMENT(A[0, …, k- 1])
i <- 0
while i <k and A[ i ] is 1 do
{
A[ i ] <- 0
i <- i+1
}
if i < k then
A[ i ] <- 1
Worst- case analysis
- :
- :
value A[4] A[3] A[2] A[1] A[0]
0 00000
1 00001
2 00010
3 00011
4 00100
5 00101
6 00110
7 00111
8 01000
Observation: flips each time increment is called
flips every other times
flips every four times
…..
For bit flips times in a sequence of operations on an initially zero counter.
For , bit never flips.
Total numbers of bit flips in the sequence is
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Balanced search trees vs. splay trees: aggregate analysis (1) steps. The amortized cost per operation is (2) each operation has the same amortized cost (3) example: stack with multipop. Analysis of a sequence of and operations on an initially empty stack. Observations : each object can be popped at most once for each time it is pushed. The times can be called on an initially empty stack including calls within is at most operations, which is. The total cost of on an initially empty stack: Amortized cost of any operation: (4) example: increment a binary counter. Increment(a[0, , k- 1]) i
