CS 223 Review Final Exam

Test Date: August 7

Trees

ü Definition

ü Inserting

ü Deleting

ü Traversing

o InOrder

o PreOrder

o PostOrder

ü Heaps

Maps

ü Sets

ü Maps

ü Hashing

o Open Addressing (linear probing)

o Chaining

o Load factor

ü Performance

ü Implementation

Self Balancing Trees

ü AVL Trees

o Insertion – Balancing

ü Red/Black Trees

o Insertion – Balancing

Graphs

ü What is a graph

ü Breadth-First Search

ü Depth-First Search

ü Dijkstra’s Algorithm

ü Primm’s Algorithm

Understand Time Complexities on everything.

Algorithms Book

25 – Graphs

ü Floyd-Warsall’s algorithm

ü Mininum Spanning Tree

ü Same as above

Greedy Algorithms

ü Dykstra’s

ü Primm’s

ü Kruskal’s

ü Huffman codes

ü Theory behind the greedy algorithms

– Divide and Conquer

ü Merge Sort

ü Closest Pair of Points

ü Stock Market game strategy

ü Theory behind the algorithms

Dynamic Programming

ü Be able to describe the theory behind Dynamic programming and maybe create a small solution

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