Data Structures and Algorithms

Sample Course Syllabus

The specific topics for a possible one-semester course based on the book Data Structures, Algorithms, and Applications in C++ are given below. This list is based on a corresponding Java-based course the author teaches at the University of Florida. The number of lectures devoted to each topic is only an estimate. The actual time spent on each topic may be different from the estimate. The powerpoint lectures available from this site correspond to this syllabus.

  1. Simple sort methods and performance measurement. (2 lectures).
  2. Data representation methods and linear lists. (7 lectures)
  3. Arrays & matrices. (2 lectures)
  4. Stacks. (2 lectures)
  5. Queues. (1 lecture)
  6. Hashing and LZW compression. (3 lectures)
  7. Binary trees. (4 lectures)
  8. Priority queues. (2 lectures)
  9. Tournament trees. (1 lecture)
  10. Search trees. (2 lectures)
  11. Graphs. (3 lectures)
  12. The greedy method. (3 lectures)
  13. Divide-and-conquer. (3 lectures)
  14. Dynamic programming. (5 lectures)
  15. Backtracking. (2 lectures)
  16. Branch-and-bound. (1 lecture)


A more detailed outline of each of the lectures is given below.

.
Lecture Content Reading
1 Course overview and insertion sort. Chapters 1 through 3.
2 Insertion sort and practical complexities. Section 3.5.
3 Run-time measurement. Chapter 4.
4 Linear lists. Sections 5.1-5.2.
5 Array representation and array resizing. Section 5.3.
6 Walk through of code for arrayList. Section 5.3.
7 Iterators. Linked representation of a linear list. Sections 5.3 and 6.1.
8 Walk through of code for chain. Head nodes, circular lists, doubly linked lists. Sections 6.1, 6.2, and 6.3.
9 Simulated pointers, available-space lists and garbage collection. -
10 Row-major and column-major indexing, and special matrices. Sections 7.1, 7.2, and 7.3.
11 Sparse matrices. Section 7.4.
12 Stacks--application to parentheses matching, towers-of-hanoi, railroad car rearrangement, and switchbox routing; array stacks. Sections 8.1, 8.2, 8.5.
13 Array and linked stacks. Section 8.3 and 8.4.
14 Nonapplicability of queues for parantheses matching, towers-of-hanoi, railroad problem with LIFO tracks, and switchbox routing. Application of queues to railroad problem with FIFO tracks, wire routing, and component labeling. Array and linked queues. Sections 9.1-9.4, 9.5.1-9.5.3.
15 Exam. -
16 Dictionaries, linear list representation, and hashing. Sections 10.1, 10.2, 10.3, and 10.5.
17 Hashing and hash table design. Section 10.5.
18 LZW compression. Section 10.6.
19 Trees, binary trees, and properties. Sections 11.1-11.3.
20 Binary tree representation and operations. Sections 11.4 and 11.5.
21 Binary tree traversal methods-- preorder, inorder, postorder, level order. Reconstruction from two orders Sections 11.6-11.8.
22 Online equivalence classes, union-find. Section 11.9.2.
23 Application of priority queues to heap sort and machine scheduling. Min and max heaps. Sections 12.1-12.4, 12.6.1, and 12.6.2.
24 Initialization of min and max heaps. Height- and weight-biased leftist trees. Sections 12.4.4 and 12.5.
25 Winner and loser trees and application to k-way merging, run generation, and first-fit bin packing. Chapter 13.
26 Binary search trees and indexed binary search trees. Sections 14.1-14.5.
27 Definition of AVL trees. Graph applications and properties. Sections 15.1, 16.1-16.3.
28 Graph operations and representation. Sections 16.4-16.7.
29 Breadth-first and depth-first search. Application to path finding, connected components, and spanning trees. Sections 16.8 and 16.9.
30 Greedy method and application to bin packing, loading, and knapsack problems. Sections 17.1, 17.2, 17.3.1, and 17.3.2.
31 Exam. -
32 Single source all destinations shortest paths algorithm. Section 17.3.5.
33 Kruskal's and Prim's minimum-cost spanning tree algorithms. Section 17.3.6.
34 Divide and conquer, and application to defective chessboard and min-max problem. Iterative min-max implementation. Sections 18.1 and 18.2.1.
35 Merge sort, natural merge sort, and quick sort. Sections 18.2.2 and 18.2.3.
36 Selection and closest pair of points. Sections 18.2.4 and 18.2.5.
37 Dynamic programming, 0/1 knapsack problem, recursive and iterative solutions. Sections 19.1 and 19.2.1.
38 Matrix multiplication chains, dynamic programming recurrence, recursive solution. Section 19.2.2.
39 Iterative solution to matrix multiplication chains. Section 19.2.2.
40 All pairs shortest paths. Section 19.2.3.
41 Single source shortest paths with negative edge weights. Section 19.2.4.
42 Solution space trees and backtracking. Section 20.1.
43 Branch and bound. Section 20.1.