1 Introduction

Notes

More on Asymptotic Notation

2 Data Structures

Notes

Data Structure Interfaces

Sequence Interface (L02, L07)

TypeInterfaceSpecification
Containerbuild(X)given an iterable X, build sequence from items in X
 len()return the number of stored items
Staticiter_seq()return the stored items one-by-one in sequence order
 get_at(i)return the ith item
 set_at(i, x)replace the ith item with x
Dynamicinsert_at(i, x)add x as the ith item
 delete_at(i, x)remove and return the ith item
 insert_fist(x)add x as the first item
 delete_first(x)remove and return the first item
 insert_last(x)add x as the last item
 delete_last(x)remove and return the last item

Set Interface (L03-L08)

Array Sequence

Sequence Data StructureAPI Type  Worst Case O() 
ArrayContainerStaticDynamic  
APIbuild(x)get_at(i)
set_at(i)
insert_first(x)
delete_first()
insert_last(x)
delete_last()
insert_at(i, x)
delete_at(i)
Arrayn1nnn

Linked List Sequence

Sequence Data StructureAPI Type  Worst Case O() 
ArrayContainerStaticDynamic  
APIbuild(x)get_at(i)
set_at(i)
insert_first(x)
delete_first()
insert_last(x)
delete_last()
insert_at(i, x)
delete_at(i)
Linked Listnn1n # 1 if we keep track of tailn

Dynamic Array Sequence

Sequence Data StructureAPI Type  Worst Case O() 
ArrayContainerStaticDynamic  
APIbuild(x)get_at(i)
set_at(i)
insert_first(x)
delete_first()
insert_last(x)
delete_last()
insert_at(i, x)
delete_at(i)
Dynamic Arrayn1n1(a)n

Amortized Analysis

Dynamic Array Deletion

Sequence Data StructureAPI Type  Worst Case O() 
ArrayContainerStaticDynamic  
APIbuild(x)get_at(i)
set_at(i)
insert_first(x)
delete_first()
insert_last(x)
delete_last()
insert_at(i, x)
delete_at(i)
Static Arrayn1nnn
Linked Listnn1n # 1 if we keep track of tailn
Dynamic Arrayn1n1(a)n

3 Sorting

Notes

Set Interface

Set Data StructureAPI Type  Worst Case O() 
SetContainerStaticDynamic  
APIbuild(x)find(k)insert(k)
delete(k)
find_min()
find_max()
find_prev(k)
find_next(k)
Arraynnnnn
Sorted Arraynlognlognn1logn

Sorting

Permutation Sort

Solving Recurrences

Selection Sort

Insertion Sort

Merge Sort

Master Theorem

tree

casesolutionconditions
1T(n)=Θ(nlogba)f(n)=Θ(nlogbaϵ) for some constant ε>0
2T(n)=Θ(nlogbalogk+1n)T(n)=Θ(nlogbalogkn) for some constant k0
3T(n)=Θ(f(n))f(n)=Θ(nlogba+ϵ) for some constant ε>0
and af(n/b)<cf(n) for some constant 0<c<1
casesolutionconditionsintuition
1T(n)=Θ(nlogba)c<logbaWork done at leaves dominates
2T(n)=Θ(nclogn)c=logbaWork balanced across the tree
3T(n)=Θ(nc)c>logbaWork done at root dominates

4 Hashing

Notes

Comparison Model

Decision Tree

Comparison Search Lower Bound

Direct Access Array

Hashing

Chaining

Hash Functions

Division (bad): h(k)=k mod m

Universal (good, theoretically): hab(k)=(((ak+b)mod p)mod m)

EhHXi=EhH{ΣjXij}=ΣjEhHXij=1+ΣjiEhHXij=1+Σji(1)PrhH{h(ki)=h(kj)}+(0)PrhH{h(ki)h(kj)}1+Σji1/m=1+(n1)/m

Dynamic

Data StructureAPI Type  Worst Case O() 
SetContainerStaticDynamic  
APIbuild(x)find(k)insert(k)
delete(k)
find_min()
find_max()
find_prev(k)
find_next(k)
Arraynnnnn
Sorted Arraynlogn