COP 3530

Data Structures and Algorithms

University of Florida

Powerpoint Handouts



The slides used in class are available in postcript and pdf formats; 2 slides per page, 4 slides per page and 6 slides per page (e.g., Postscript6 is a 6 slide per page postscript file). Hard copy (4 slides/page) is available from Target Copy on 13th St as well as Target Copy on Archer Rd.

.
Lecture Content Reading Slides
1 Course overview and insertion sort. Chapters 1 through 3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
2 Insertion sort and practical complexities. Section 3.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
3 Run-time measurement. Chapter 4. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
4 Linear lists and array representation. Sections 5.1-5.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
5 Array representation and array resizing. Section 5.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
6 Walk through of code for ArrayLinearList. Section 5.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
7 Iterators. Linked representation of a linear list. Sections 5.3 and 6.1. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
8 Walk through of code for Chain. Head nodes, circular lists, doubly linked lists. Sections 6.2 and 6.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
9 Simulated pointers and available-space lists. Sections 7.1 and 7.2.Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
10 Row-major and column-major indexing, and special matrices. Sections 8.1, 8.2, and 8.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
11 Sparse matrices. Section 8.4. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
12 Stacks--application to parentheses matching, towers-of-hanoi, railroad car rearrangement, and switchbox routing; array stacks. Sections 9.1, 9.2, 9.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
13 Array and linked stacks. Section 9.3 and 9.4. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
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 10.1-10.4, 10.5.1-10.5.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
15 Exam. - -
16 Dictionaries, linear list representation, and hashing. Sections 11.1, 11.2, 11.3, and 11.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
17 Hashing and hash table design. Section 11.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
18 LZW compression. Section 11.6. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
19 Trees, binary trees, and properties. Sections 12.1-12.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
20 Binary tree representation and operations. Sections 12.4 and 12.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
21 Binary tree traversal methods-- preorder, inorder, postorder, level order. Reconstruction from two orders Sections 12.6-12.8. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
22 Online equivalence classes. Section 12.9.2. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
23 Application of priority queues to heap sort and machine scheduling. Min and max heaps. Sections 13.1-13.3, 13.6.1, and 13.6.2. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
24 Initialization of min and max heaps. Height- and weight-biased leftist trees. Sections 13.4.4 and 13.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
25 Winner and loser trees and application to k-way merging, run generation, and first-fit bin packing. Chapter 14. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
26 Binary search trees and indexed binary search trees. Sections 15.1-15.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
27 Definition of AVL trees. Graph applications and properties. Sections 16.1, 17.1-17.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
28 Graph operations and representation. Sections 17.4-17.7. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
29 Breadth-first and depth-first search. Application to path finding, connected components, and spanning trees. Sections 17.8 and 17.9. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
30 Greedy method and application to bin packing, loading, and knapsack problems. Sections 18.1, 18.2, 18.3.1, and 18.3.2. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
31 Exam. -
32 Single source all destinations shortest paths algorithm. Section 18.3.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
33 Kruskal's and Prim's minimum-cost spanning tree algorithms. Section 18.3.6. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
34 Divide and conquer, and application to defective chessboard and min-max problem. Iterative min-max implementation. Sections 19.1 and 19.2.1. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
35 Merge sort, natural merge sort, and quick sort. Sections 19.2.2 and 19.2.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
36 Selection and closest pair of points. Sections 19.2.4 and 19.2.5. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
37 Dynamic programming, 0/1 knapsack problem, recursive and iterative solutions. Sections 20.1 and 20.2.1. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
38 Matrix multiplication chains, dynamic programming recurrence, recursive solution. Section 20.2.2. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
39 Iterative solution to matrix multiplication chains. Section 20.2.2. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
40 All pairs shortest paths. Section 20.2.3. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
41 Single source shortest paths with negative edge weights. Section 20.2.4. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
42 Solution space trees and backtracking. Section 21.1. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6
43 Branch and bound. Section 22.1. Postscript2
Postscript4
Postscript6
pdf2
pdf4
pdf6