This exam covers chapters 17, 18,19, and 20. The types of questions will resemble the
last exam. You maybe asked to trace algorithms, implement algorithms, or modify algorithms.
This is a open book test. You may use your textbook, lecture notes (ie, the powerpoint slides),
handwritten notes, and the formula sheet handed out in class. You may not use computers or any
other textbook.
Graphs (chapter 17)
- Definitions
- Properties (section 17.1).
- Implementations
- Adjacency matrix vs adjacency lists
- advantages and disadvantages of each
- running time cost of using each
- Graph search methods: breadth-first search vs depth-first search.
- Basic applications
- finding a path (section 17.9.1).
- connected graphs adn components (section 17.9.2)
- spanning trees (section 17.9.3)
Greedy Method
- Optimization problems (section 18.1)
- The greedy criterion (section 18.2)
- Applications
- Container loading. (section 18.3.1)
- Proving the correctness of the greedy solution for container loading.
- 0/1 knapsack problem (section 18.3.2)
- topological sorting (section 18.3.3)
- proof of correctness of the topoloical sorting solution.
- data structures used in topological sorting and complexity.
- bipartite cover problem (section 18.3.4).
- greedy heuristic for bipartite cover problem, data sructures and comlexity of solution.
- single source shortest-paths problem and Dijkstra's greedy solution (section 18.3.5).
The complexity of the solution.
- greedy solution to the minimum cost spanning-tree problem (section 18.3.6).
Kruskal's algorithm, Prim's algorithm, and Sollin's algorithm.
- Data structures and complexity analysis of these solutions.
Divide and Conquer
- The method (section 19.1). You are not responsible for the examples in this section.
- Know how to solve recurrence equations by substitution (see section 19.3).
- Applications
- Defective chessboard solution (section 19.2.1). Solution and complexity analysis.
- Merge sort (section 19.2.2). Solution and complexity analysis.
- Natural merge sort. Difference, solution, complexity analysis.
- Quick sort (section 19.2.3). Solution, complexity. Importance of picking the pivot element.
- Better methods of picking the pivot element (median-of-three).
- Selection (section 19.2.4). Solution and complexity analysis.
- Closest Pair of Points (section 19.2.5). Solution and complexity analysis.
Dynamic Programming
- Method (section 20.1) including principle of optimality, setting up DP recurrence
equations, state, and traceback.
- Applications
- 0/1 Knapsack problem (section 20.2.1)
- All-pairs shortest paths (Floyd's algorithm, section 20.2.3)
- Single-source shortest paths with negative costs (Bellman-Ford algorithm, section 20.2.4)
Return to John Barr's Home Page
Last Modified: 10 December 2001
THIS PAGE MAINTAINED BY:
John Barr, Ithaca College
