Algorithms and Data Structures PPT PDF SLIDES
Description. This course surveys the most important algorithms and data structures in use on computers today. Particular emphasis is given to algorithms for sorting, searching, and string processing. Fundamental algorithms in a number of other areas are covered as well, including geometric and graph algorithms. The course will concentrate on developing implementations, understanding their performance characteristics, and estimating their potential effectiveness in applications.
Course website. The course website
http://www.princeton.edu/~cos226
includes links to course content, including programming assignments, exercises, lecture slides, and old exams. You will also use it to submit programming assignments. Readings. The following textbook is required. It contains a wealth of information beyond what we can cover in lecture; it is certain to enhance your understanding of algorithms and data structures.
- Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
Slides download here:
| TOPIC | SLIDES | READINGS | DEMOS |
|---|---|---|---|
| Intro · Union Find | 1up · 4up | 1.5 | Quick-union |
| Analysis of Algorithms | 1up · 4up | 1.4 | Binary search |
| Stacks and Queues | 1up · 4up | 1.3 | Dijkstra 2-stack |
| Elementary Sorts | 1up · 4up | 2.1 | Selection · Insertion · Shuffle · Graham |
| Mergesort | 1up · 4up | 2.2 | Merging |
| Quicksort | 1up · 4up | 2.3 | Partitioning |
| Priority Queues | 1up · 4up | 2.4 | Heap · Heapsort |
| Elementary Symbol Tables · BSTs | 1up · 4up | 3.1–3.2 | BST |
| Geometric Applications of BSTs | 1up · 4up | – | Kd tree · Interval search tree |
| Balanced Search Trees | 1up · 4up | 3.3 | Red-black BST · GrowingTree |
| Hash Tables | 1up · 4up | 3.4 | – |
| Midterm Exam | – | – | |
| Undirected Graphs | 1up · 4up | 4.1 | DFS · BFS |
| Directed Graphs | 1up · 4up | 4.2 | DFS · Topological sort |
| Minimum Spanning Trees | 1up · 4up | 4.3 | Greedy · Kruskal · Prim |
| Shortest Paths | 1up · 4up | 4.4 | Dijkstra · Acyclic · Bellman-Ford |
| Maximum Flow | 1up · 4up | 6.4 | Ford-Fulkerson |
| String Sorts | 1up · 4up | 5.1 | Key-indexed counting · String sorts |
| Tries | 1up · 4up | 5.2 | Trie |
| Substring Search | 1up · 4up | 5.3 | KMP |
| Regular Expressions | 1up · 4up | 5.4 | NFA simulation · NFA construction |
| Data Compression | 1up · 4up | 5.5 | Huffman · LZW |
| Reductions | 1up · 4up | – | – |
| Combinatorial Search | 1up · 4up | – | The Longest Path |
