Course Materials Outline

[next] [prev] [prev-tail] [tail] [up]

5 Course Materials Outline

5.1 Textbook Materials Outline

The following is a section-by-section outline of the textbook. For each section, a symbol is given which indicates the nature of coverage in the course. The meaning of these symbols is provided in the table below.


✔	Material will be covered in the course.

✘	Material will not be covered in the course.

✙	Review material, prior knowledge is expected.

✥	Material will be covered partially or selectively.

✻	Tentative material, may be covered, time permitting.

Entries have not been provided for sections entitled ”References and Readings” or ”Additional Exercises.” In addition, no section-by-section breakdown is given for chapters which are to be omitted entirely.

1.

Introduction

1.1.: What is an algorithm? ✔
1.2.: Algorithm specification ✔
1.3.: Performance analysis ✔
1.4.: Randomized algorithms ✘

2.

Elementary Data Structures

2.1.: Stacks and queues ✙
2.2.: Trees ✙
2.3.: Dictionaries ✙
2.4.: Priority queues ✔(with Kruskal’s algorithm: 4.5.2)
2.5.: Sets and disjoint union ✔(with job sequencing with deadlines: 4.4)
2.6.: Graphs ✙

3.

Divide and Conquer

3.1.: General method ✔
3.2.: Binary search ✔
3.3.: Finding the maximum and minimum ✘
3.4.: Merge sort ✔
3.5.: Quicksort ✔
3.6.: Selection ✔
3.7.: Strassen’s matrix multiplication ✘
3.8.: Convex hull ✔

4.

The Greedy Method

4.1.: The general method ✔
4.2.: Knapsack problem ✔
4.3.: Tree vertex splitting ✘
4.4.: Job sequencing with deadlines ✔
4.5.: Minimum-cost spanning trees ✔
4.6.: Optimal storage on tapes ✘
4.7.: Optimal merge patterns ✘
4.8.: Single-source shortest paths ✔

5.

Dynamic Programming

5.1.: The general method ✔
5.2.: Multistage graphs ✔
5.3.: All pairs shortest paths ✔
5.4.: Single-source shortest paths: general weights ✔
5.5.: Optimal binary search trees ✘
5.6.: String editing ✘
5.7.: 0/1 knapsack ✔
5.8.: Reliability design ✘
5.9.: The travelling salesperson problem ✔
5.10.: Flow shop scheduling ✘

6.

Basic Search and Traversal Techniques

6.1.: Techniques for binary trees ✔
6.2.: Techniques for graphs ✔
6.3.: Connected components and spanning trees ✘
6.4.: Biconnected components and DFS ✘

7.

Backtracking

7.1.: The general method ✔
7.2.: The 8-queens problem ✔
7.3.: Sum of subsets ✘
7.4.: Graph coloring ✘
7.5.: Hamiltonian cycles ✘
7.6.: Knapsack problem ✔

8.

Branch-and-Bound

8.1.: The method ✔
8.2.: 0/1 knapsack problem ✔
8.3.: Travelling salesperson ✔
8.4.: Efficiency considerations ✔

9.

Algebraic Problems

9.1.: The general method ✔
9.2.: Evaluation and interpolation ✔
9.3.: The fast Fourier transform ✔
9.4.: Modular arithmetic ✘
9.5.: Even faster evaluation and interpolation ✘

10.

Lower Bound Theory

10.1.: Comparison trees ✔
10.2.: Oracles and adversary arguments ✔
10.3.: Lower bounds through reductions ✔
10.4.: Techniques for algebraic problems ✘

11.

NP-Hard and NP-Complete Problems

11.1.: Basic concepts ✔
11.2.: Cook’s theorem ✥
11.3.: NP-hard graph problems ✥
11.4.: NP-hard scheduling problems ✥
11.5.: NP-hard code-generation problems ✥
11.6.: Some simplified NP-hard problems ✥

12.

Approximation Algorithms

12.1.: Introduction ✔
12.2.: Absolute approximations ✔
12.3.: ε–approximations ✔
12.4.: Polynomial-time approximation schemes ✔
12.5.: Fully polynomial-time approximation schemes ✔
12.6.: Probabilistically good algorithms ✘

13.

PRAM Algorithms ✘

14.

Mesh Algorithms ✘

15.

Hypercube Algorithms ✘

5.2 Supplementary Materials Outline

Several topics which are not covered in the textbook, or are covered insufficiently, will be included in the course. For these topics, supplementary materials (which may be part of the lecture notes) will be made available. The major topics, together with the associated topic number from Section 4 of this syllabus, are as follows.

Documentation on the gprof profiling package [2.2]
Recurrence relations [2.1]
Matroids and the formalization of the greedy method [3.2]
AND/OR graphs and game trees [3.4]
Cook’s theorem [4.2]

[next] [prev] [prev-tail] [front] [up]