CS 223 Review Final Exam
Test Date: August 4
Koffman/Wolfgang Book
Chapter 8 – Trees
ü Definition
ü Inserting
ü Deleting
ü
Traversing
o
InOrder
o
PreOrder
o
PostOrder
ü
Heaps
Chapter 9 – Maps
ü Sets
ü Maps
ü Hashing
o Open Addressing (linear probing)
o Chaining
o Load factor
ü Performance
ü Implementation
Chapter 10 – Self Balancing Trees
ü AVL Trees
o Insertion – Balancing
ü Red/Black Trees
o Insertion – Balancing
Chapter 12 – Graphs
ü What is a graph
ü Breadth-First Search
ü Depth-First Search
ü Dijkstra’s Algorithm
ü Primm’s Algorithm
Understand Time Complexities on everything.
Kleinberg/Tardos Book
Chapter 2 – Algorithm Analysis
ü
Computational Tractabiltiy
ü
Time Complexities
Chapter 3 – Graphs
ü Floyd-Warsall’s algorithm
ü Mininum Spanning Tree
ü Same as chapter 12 above
Chapter 4 – Greedy Algorithms
ü Dykstra’s
ü Primm’s
ü Kruskal’s
ü Theory behind the algorithms
Chapter 5 – Divide and Conquer
ü Merge Sort
ü Closest Pair of Points
ü
Integer Multiplication
ü
Theory behind the algorithms
Chapter 6 – Dynamic Programming
ü
Knapsack
ü
Coins/Change lab
Chapter 8 – NP and Computabilty
ü If a problem is NP what does that mean?
ü If a problem is NP-Complete what does that mean?
ü If a problem is P what does that mean?
ü
P = NP??
Other
ü
Turing Machines