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