Below are the readings for DSA2. These reading are optional, but many find them useful – either as pre-reads or as review. All readings are from CLRS, 4th edition, which you can view for free via this link to the UVA library.
To see what reading is for what lecture, you can look ahead at the next set of slides in the posted slide sets – we might go through 30 or so slides in a given lecture. Then match the topics that are in those slides with the topics below.
DISCLAIMER: Some of these readings may change as we approach a given lecture. But we do not expect there to be significant changes.
- Review:
- CLRS Chapter 2: insertion sort (if needed), book’s pseudo-code conventions
- CLRS Chapter 3: info on order-class (more than we cover in lecture), math review
- Note: book goes into more depth than we do, and topics we don’t need. Use it to reinforce what’s taught in lectures.
- Graphs
- Chapter 20: Elementary Graph Algorithms
- 20.1: Representation of graphs
- 20.2: Breadth-first search
- 20.3: Depth-first search
- 20.4: Topological sort
- 20.5: Strongly connected components, through Section 2
- Chapter 22: Single-Source Shortest Paths
- 22.3: Dijkstra’s algorithm
- Divide and Conquer
- Chapter 4: Divide and Conquer
- 4.1: Multiplying square matrices
- 4.2: Strassen’s algorithm for matrix multiplication
- 4.3: The substitution method for solving recurrences
- 4.4: The recursion-tree method for solving recurrences
- 4.5: The master method for solving recurrences
- Greedy
- Chapter 15: Greedy Algorithms
- 15.1: An activity-selection problem
- 15.2: Elements of the greedy strategy
- 15.3: Huffman codes
- Chapter 21: Minimum Spanning Trees
- 21.1: Growing a minimum spanning tree
- 21.2: The algorithms of Kruskal and Prim
Chapter 16
- Dynamic Programming
- Chapter 24: Maximum Flow
- 24.1: Flow networks
- 24.2: The Ford-Fulkerson method
- 24.3: Maximum bipartite matching
- Reductions are covered in CLRS but in a context we’re not studying in CS3100
- Machine Learning