**Algorithms and Data Structures**

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

**Outline of Course Contents**

### The Complexity
of Algorithms:

- Models of computation (old and new)
- Upper bounds (the complexity of algorithms)
- Lower bounds (the complexity of problems)
- Actual complexity (input and output sensitive algorithms)
- Expected complexity

### Proving
the Correctness of Algorithms:

- Logic
- Proof by contradiction
- Proof by construction
- Proof by induction
- Existence Proofs

### Linear
Data Structures:

- Arrays
- Stacks
- Deques
- Linked lists
- Adjacency matrices
- Adjacency lists

### Graphs:

- Graph data structures:
- Doubly-Connected-Edge-List (DCEL)
- Winged-Edge
- Twin-Edge
- Quad-edge

- Shortest paths
- Minimal spanning trees
- Proximity graphs
- Hamiltonian cycles
- Graph coloring
- Planarity

### Trees:

- Binary trees
- Quad trees
- Balanced trees
- Heaps
- Huffman trees
- Decision trees
- Game trees

### Divide
and Conquer:

- Sorting
- The skyline problem
- Convex hulls
- Finding closest pairs

### Greedy
Algorithms:

- Complexity, convexity and unimodality
- Hill climbing algorithms
- Quick sort
- Quick hull

### Searching
Methods:

- Maze searching
- Binary search
- Pure binary search
- Binary search in a cyclic sequence
- Binary search for a special index
- Binary search in sequences of unknown size
- The Bolzano method (bisection) for solving equations
- Interpolation search

- Depth-first search
- Breadth-first search
- Plane-sweep
- Range search
- Branch-and-bound
- The A* algorithm

### Elimination
Methods:

- Convex hulls of point sets

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

- Convex hulls of polygons
- Convex hulls of points

### Distributive
Algorithms:

- Distributive sorting
- Bucketing methods

### Prune-and-Search
Algorithms:

- Median finding
- Ear-cutting and polygon triangulation
- Convex hulls

### Linear
Programming:

- The Simplex method
- Megiddo's linear time algorithm

### Probabilistic
Algorithms:

- Randomization
- Randomized convex hull

**Approximate Algorithms:**
- Travelling salesman problem
- The vertex-cover problem
- The bin-packing problem

*Teaching Activities*
*Homepage *