Search This Blog

Friday, September 30, 2011

DATA STRUCTURES AND ALGORITHMS PPT



DATA STRUCTURE AND ALGORITHMS PPT
 
The specific topics are given below. 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.
  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) 

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

No comments:

Post a Comment

Popular Courses

Resources Higher Education Blogs - BlogCatalog Blog Directory Resources Blogs