Lecture Notes For All: Data Structures and Algorithms PDF

GoDaddy

$3 .COM at GoDaddy.com! Expires 4/16/13. ...................

Thursday, March 11, 2010

Data Structures and Algorithms PDF

Data Structures and Algorithms
SATRAJ SAHANI
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.

LectureContentReadingSlides

1
Course overview and insertion sort. Chapters 1 through 3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
2Insertion sort and practical complexities.Section 3.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
3Run-time measurement.Chapter 4.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
4Linear lists and array representation.Sections 5.1-5.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
5Array representation and array resizing.Section 5.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
6Walk through of code for ArrayLinearList.Section 5.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
7Iterators. Linked representation of a linear list.Sections 5.3 and 6.1.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
8Walk through of code for Chain. Head nodes, circular lists, doubly linked lists.Sections 6.2 and 6.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
9Simulated pointers and available-space lists.Sections 7.1 and 7.2.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
10Row-major and column-major indexing, and
special matrices.
Sections 8.1, 8.2, and 8.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
11Sparse matrices.Section 8.4.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
12Stacks--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
13Array and linked stacks.Section 9.3 and 9.4.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
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.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
15Exam.--
16Dictionaries, linear list representation, and hashing.Sections 11.1, 11.2, 11.3, and 11.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
17Hashing and hash table design.Section 11.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
18LZW compression.Section 11.6.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
19Trees, binary trees, and properties.Sections 12.1-12.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
20Binary tree representation and operations.Sections 12.4 and 12.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
21Binary tree traversal methods-- preorder, inorder, postorder,
level order. Reconstruction from two orders
Sections 12.6-12.8.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
22Online equivalence classes.Section 12.9.2.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
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.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
24Initialization of min and max heaps.
Height- and weight-biased leftist trees.
Sections 13.4.4 and 13.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
25Winner and loser trees and application to k-way merging, run generation,
and first-fit bin packing.
Chapter 14.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
26Binary search trees and indexed binary search trees.Sections 15.1-15.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
27Definition of AVL trees. Graph applications and properties.Sections 16.1, 17.1-17.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
28Graph operations and representation.Sections 17.4-17.7.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
29Breadth-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
30Greedy 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
31Exam.-
32Single source all destinations shortest paths algorithm.Section 18.3.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
33Kruskal's and Prim's minimum-cost spanning tree algorithms.Section 18.3.6.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
34Divide 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
35Merge sort, natural merge sort, and quick sort.Sections 19.2.2 and 19.2.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
36Selection and closest pair of points.Sections 19.2.4 and 19.2.5.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
37Dynamic programming, 0/1 knapsack problem, recursive
and iterative
solutions.
Sections 20.1 and 20.2.1.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
38Matrix multiplication chains, dynamic programming recurrence,
recursive solution.
Section 20.2.2.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
39Iterative solution to matrix multiplication chains.Section 20.2.2.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
40All pairs shortest paths.Section 20.2.3.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
41Single source shortest paths with negative edge weights.Section 20.2.4.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
42Solution space trees and backtracking.Section 21.1.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6
43Branch and bound.Section 22.1.Postscript2


Postscript4


Postscript6


pdf2


pdf4


pdf6

1 comment: