Algorithms and Data Structures

"Obviousness is always the enemy of correctness." - Bertrand Russell

Outline of Course Contents

### The Complexity of Algorithms:

1. Models of computation (old and new)
2. Upper bounds (the complexity of algorithms)
3. Lower bounds (the complexity of problems)
4. Actual complexity (input and output sensitive algorithms)
5. Expected complexity

### Proving the Correctness of Algorithms:

1. Logic
2. Proof by contradiction
3. Proof by construction
4. Proof by induction
5. Existence Proofs

### Linear Data Structures:

1. Arrays
2. Stacks
3. Deques
4. Linked lists
5. Adjacency matrices
6. Adjacency lists

### Graphs:

1. Graph data structures:
1. Doubly-Connected-Edge-List (DCEL)
2. Winged-Edge
3. Twin-Edge
4. Quad-edge
2. Shortest paths
3. Minimal spanning trees
4. Proximity graphs
5. Hamiltonian cycles
6. Graph coloring
7. Planarity

### Trees:

1. Binary trees
2. Quad trees
3. Balanced trees
4. Heaps
5. Huffman trees
6. Decision trees
7. Game trees

### Divide and Conquer:

1. Sorting
2. The skyline problem
3. Convex hulls
4. Finding closest pairs

### Greedy Algorithms:

1. Complexity, convexity and unimodality
2. Hill climbing algorithms
3. Quick sort
4. Quick hull

### Searching Methods:

1. Maze searching
2. Binary search
1. Pure binary search
2. Binary search in a cyclic sequence
3. Binary search for a special index
4. Binary search in sequences of unknown size
5. The Bolzano method (bisection) for solving equations
6. Interpolation search
3. Depth-first search
4. Breadth-first search
5. Plane-sweep
6. Range search
7. Branch-and-bound
8. The A* algorithm

### Elimination Methods:

1. Convex hulls of point sets

### On-Line and Real-Time Algorithms:

1. Convex hulls of polygons
2. Convex hulls of points

### Distributive Algorithms:

1. Distributive sorting
2. Bucketing methods

### Prune-and-Search Algorithms:

1. Median finding
2. Ear-cutting and polygon triangulation
3. Convex hulls

### Linear Programming:

1. The Simplex method
2. Megiddo's linear time algorithm

### Probabilistic Algorithms:

1. Randomization
2. Randomized convex hull
Approximate Algorithms:
1. Travelling salesman problem
2. The vertex-cover problem
3. The bin-packing problem