Slides, links, material for Fall 2018: Data Structures and Algorithm Analysis (CS317):
Note everything is developed on the board in class; these are supporting written slides (and extra links to animations or optional papers) that cover the same scope of material.
-
- Aug 21: Introduction to algorithms: Algorithms1aSlides_fall18.pdf
- Aug 23: Introduction to algorithms: Algorithms1bSlides_fall18.pdf
- Aug 28: Loop invariants in Aug 23 slides; Started intro to complexity classes and growth of functions, including big Oh, Omega, Theta: Algorithms2aSlides_fall18.pdf
Website on complexity classes beyond scope of class: ComplexityZoo
Loop Invariants for Findmin: LoopInvariantExample
Loop Invariant Example Code: LoopInvariantExampleCode2.pdf - Aug 30: Continued intro to complexity classes and growth of functions, including big Oh, Omega, Theta. Slides above and also: Algorithms2bSlides_fall18.pdf
Started Divide and Conquer part 1 up to and including Max Subarray problem: Algorithms3aSlidesClass_fall18.pdf - Sept 4: Continued Divide and Conquer part 1 and 2. Divide and Conquer part 2: Algorithms3bSlides_class_fall18.pdf
- Sept 6: Continued Divide and Conquer part 2 (slides above), and part 3: Algorithms3c_2018.pdf
- Sept 11: Continued divide and Conquer part 3 (slides 3c above).
- Sept 13: Randomized algorithms 1, Probability review: Algorithms4aSlides_fall18.pdf
- Sept 18: Randomized algorithms 2, and Quicksort: Algorithms4b_fall18.pdf
-
- Partition algorithm for quicksort animation by Burt Rosenberg:
- We also talked about optimal stopping algorithms for hiring and other applications in the book: Algorithms to Live By: The Computer Science of Human Decisions (Brian Christian, Tom Griffiths).
- Sept 20: Finished Randomized algorithms with brief mention of Order Statistics (slides above). Review/Intro of data structures: Algorithms5aSlides_fall18.pdf
- Sept 25: Hash functions part 1: Algorithms5b_fall18.pdf
- Sept 27: Hash functions part 2: Algorithms5c_fall18.pdf
- Oct 2: Binary Search trees: Algorithms6aClass_fall18.pdf
- Oct 4: Red Black Trees part 1: Algorithms6b_RedBlackTree_fall18.pdf (material not on midterm)
- Oct 9: Review for midterm.
- Oct 11: Midterm in class.
- Oct 16: Red Black Trees part 2: Algorithms6c_RedBlackTreeCont_fall18.pdf
See also Red Black Tree animation website by David Galles. - October 23: Graph algorithms 1: Intro and BFS.
friendsArticle2018.pdf
Networks, Crowds, and Markets book. By David Easley and Jon Kleinberg
BFS_animation website by David Galles.
AlgorithmsGraphsClass1_fall18.pdf - October 25: Graph algorithms 2: DFS and Topological Sort.
DFS_animation website by David Galles.
AlgorithmsGraphsClass2_fall18.pdf
Topological Sort in: AlgorithmsGraphsClass3_fall18.pdf - October 30: Graph algorithms part 3: Strongly Connected Components: Strongly Connected Components in: AlgorithmsGraphsClass3_fall18.pdf
Broder paper on web connectivity - Nov 1: Graph algorithms part 4: Dijkstra: AlgorithmsGraphsClass4_fall18.pdf
- Nov 6: Dynamic programming part 1: Fibonacci and (only motivation for) Longest Common Subsequence:
DP1_2018.pdf (notes up to the intuition of Longest Common Subsequence).
Bellman birth of Dynamic Programming
Fibonacci animation website by David Galles.
Fibonacci compute time by Burt Rosenberg.
Cipher Thomas Jefferson. - Nov 8: Dynamic programming part 2: Longest Common Subsequence from slides above. LCS animation website by David Galles.
- Nov 13: Dynamic programming part 3: Rod cutting problem: Algorithms7b_DynamicP_fall18.pdf
- Nov 15: Greedy algorithms part 1: Activity Selection problem: Algorithms8a_greedy_fall18.pdf
- Nov 20; 22: Thanksgiving break!
- Nov 27: Greedy algorithms part 2: Huffman coding: (slides also include the knapsack problem we discussed in the previos class) Algorithms8b_greedy_fall18.pdf
Compression intro slides
Topics covered:
- Introduction to algorithms
- Sorting as example
- Correctness
- Growth of functions and Big-Oh notation
- Divide and conquer and recursion equations
- Randomized algorithms
- Hashing
- Trees and Red Black Trees
- Algorithmic paradigms: Dynamic programming, Greedy algorithms
- Graph Algorithms