CPSC 327 Schedule

Class preparation assignments are generally based on the assigned reading and are due by 10pm the night before the class for which they are listed. For readings, "ADM" refers to the textbook (The Algorithm Design Manual).

Dates for things in light gray are for planning purposes and may be adjusted slightly. Expect class preparation assignments for most classes, weekly homeworks, and several programming assignments.

		Assignments
Week 1: 1/21-1/24 Topics: course introduction; analysis of algorithms

Wed	Materials from class: slides: course introduction	introductory survey (on Canvas)

Fri	Reading: ADM 2.1-2.4 (RAM model of computation, big-Oh, growth rates and dominance relations, working with big-Oh) Materials from class: slides: analysis of algorithms	class prep — ADM 2.1-2.4 (on Canvas) due Thu 1/23 10pm
Week 2: 1/27-1/31 Topics: analysis of algorithms; ADTs

Mon	Reading: ADM 2.5 (reasoning about efficiency) ADM 2.7-2.8, logarithms and exponents reference (logarithms and exponents) ADM 2.9 (war story) big-Oh for sums, big-Oh for recurrence relations Materials from class: slides: analysis of algorithms	class prep — big-Oh for sums and recurrence relations, ADM 2.7-2.8 (on Canvas) due Sun 1/26 10pm

Wed	Reading: ADM 4.6.3 (limitations of asymptotic complexity) Materials from class: slides: analysis of algorithms		homework 1 due Fri 2/7 in class

Fri	Reading: ADM chapter 3 intro (page 69) ADM 3.1 (arrays and linked lists) ADM 3.2-3.3 (stacks, queues, dictionaries) ADM 3.5 (priority queues) — for the "stop and think" about implementation, focus on the unsorted and sorted array implementations Materials from class: examples: big-Oh from code slides: common ADTs	class prep — ADM 3.1 (on Canvas) due Thu 1/30 10pm
Week 3: 2/3-2/7 Topics: data structures: arrays, linked lists, binary trees; binary search trees, balanced BSTs

Mon	Materials from class: slides: data structures (arrays, linked lists, implementations of containers)

Wed	Reading: ADM 3.4-3.4.2 (binary search trees) Materials from class: slides: data structures (basic implementations of Map/Dictionary, PriorityQueue) slides: binary search trees supplemental: binary trees (BinaryTree ADT, working with binary trees, tree implementation)	class prep — BSTs (on Canvas) due Tue 2/4 10pm

Fri	Reading: ADM 3.4.3 (balanced search trees) AVL trees Materials from class: slides: AVL trees (balanced search trees)	class prep — AVL trees (on Canvas) due Thu 2/6 10pm	homework 2 [corrected!] due Fri 2/14 in class
Week 4: 2/10-2/14 Topics: balanced search trees (2-4 trees); heaps; hashtables

Mon	Reading: 2-4 trees Materials from class: slides: 2-4 trees (balanced search trees)	class prep — 2-4 trees (on Canvas) due Sun 2/9 10pm

Wed	Reading: ADM 4.3.1-4.3.4 (heaps) Materials from class: slides: balanced search trees (wrapup) slides: heaps	class prep — heaps (on Canvas) due Tue 2/11 10pm

Fri	Reading: ADM 3.7-3.7.1 (hashing and hashtables) Materials from class: slides: heaps (wrapup) slides: hashtables	class prep — hashtables (on Canvas) due Thu 2/13 10pm	homework 3 due Fri 2/21 in class
Week 5: 2/17-2/21 Topics: specialized data structures; developing data structures; applications of data structures and fundamental techniques

Mon	Reading: ADM 3.8-3.9 (specialized data structures) ADM 15 (hitchhiker's guide) — skim, focusing on what each data structure is, its applications, and an overview of the relevant variations and considerations Materials from class: slides: hashtables (deletion, other operations) slides: specialized data structures (fundamental ADTs wrapup, data structures for other domains)	class prep — ADM 15 (on Canvas) due Sun 2/16 10pm

Wed	Reading: ADM 4.1-4.2, 4.3, 4.3.5, 4.5-4.7, 4.8, 17.1 (sorting) Materials from class: slides: sorting	class prep — sorting (on Canvas) due Tue 2/18 10pm

Fri	Reading: ADM 3.6, 4.4 (applications of containers) ADM 17.2-17.3 (searching and selection) ADM 3.7.2-3.7.5 (other uses of hashing) Materials from class: slides: searching, selection, other uses of hashing slides: choosing and designing data structures	class prep — fundamental techniques (on Canvas) due Thu 2/20 10pm	homework 4 due Fri 2/28 in class
Week 6: 2/24-2/28 Topics: graphs, graph traversal, BFS and BFS-based algorithms

Mon	Reading: ADM 7 (introduction), 7.1 (graphs and graph terminology) ADM 7.2 data structures for graphs — pay attention to the data structures and how they work rather than the C code ADM 7.3-7.4 (war stories) Materials from class: slides: graphs (terminology, Graph ADT and implementation)	class prep — ADM 7.1-7.2 (on Canvas) due Sun 2/23 10pm		programming assignment 1 Graph ADT due Fri 3/7 in class help sessions: Wed 2/26 8:30-9:30am Thu 2/27 3-4pm Lansing 301	hw1 resubmit due Mon 2/24 in class feedback

Wed	exam 1 review information

Fri	Reading: ADM 7.5 (graph traversals) ADM 7.6-7.7 (BFS and BFS-based algorithms and applications) Materials from class: slides: graphs (Graph ADT implementation) slides: graph traversals (traversal, BFS)	class prep — ADM 7.5-7.7 (on Canvas) due Thu 2/27 10pm	homework 5 due Mon 3/10 in class
Week 7: 3/3-3/7 Topics: DFS and DFS-based algorithms, shortest paths, minimum spanning tree

Mon	Reading: ADM 7.8-7.10 (DFS and DFS-based algorithms and applications) Materials from class: slides: BFS (BFS-based algorithms) slides: DFS (DFS, DFS-based algorithms)	class prep — ADM 7.8-7.10 (on Canvas) due Sun 3/2 10pm			hw2 resubmit due Mon 3/3 in class feedback

Wed	Reading: ADM 8 introduction (weighted graph algorithms) ADM 8.3 (shortest paths) Materials from class: slides: DFS (DFS-based algorithms for directed graphs) slides: shortest paths (Dijkstra's algorithm)	class prep — ADM 8 intro, 8.3 (on Canvas) due Tue 3/4 10pm

Fri	Reading: ADM 8.1-8.1.3 (minimum spanning trees) Materials from class: slides: shortest paths and related algorithms (Dijkstra, Bellman-Ford, all pairs shortest path, transitive closure) slides: minimum spanning trees slides: union-find	class prep — ADM 8.1-8.1.3 (on Canvas) due Thu 3/6 10pm		programming assignment 2 Dijkstra's Algorithm due Fri 3/14 in class
Week 8: 3/10-3/14 Topics: solving problems with graphs; divide-and-conquer algorithms

Mon	Reading: ADM 8.7 (design graphs, not algorithms) ADM 7.1.1, 8.2, 8.4 (examples and war stories) Materials from class: slides: minimum spanning trees (Kruskal's running time, Prim's algorithm) slides: solving problems with graphs	class prep — ADM 8.7 (on Canvas) due Sun 3/9 10pm	homework 6 due Wed 3/26 in class

Wed	Reading: ADM 18 (hitchhiker's guide) — skim, focusing on what each problem is, its applications, and an overview of the relevant variations and considerations ADM 8.1.4 (variations on MST) ADM 8.5 (except 8.5.2), 8.6 (network flows, bipartite matching, min-cut) — skim, focusing on what each problem is and its applications rather than the algorithms for solving the problem Materials from class: slides: solving problems with graphs	class prep — ADM 8.1.4, 8.2, 8.5-8.6, 18 (on Canvas) due Tue 3/11 10pm			hw3 resubmit due Wed 3/12 in class feedback

Fri	Reading: (for the week after spring break if you don't get to it before class) ADM chapter 5 introduction (divide-and-conquer) how to design algorithms developing recursive algorithms developing divide-and-conquer algorithms ADM 1.4 (induction) ADM 5.3, big-Oh for recursive algorithms (recurrence relations) Materials from class: slides: developing divide-and-conquer algorithms examples: sorting — from class (in progress) (developing divide-and-conquer algorithms)
Spring Break: 3/17-3/21
Week 9: 3/24-3/28 Topics: divide-and-conquer algorithms; iterative algorithms

Mon	Materials from class: examples: sorting — from class (in progress) (developing divide-and-conquer algorithms)			programming assignment 3 Ski-O due Mon 4/7 in class

Wed	Reading: ADM 5.1, 5.5-5.6, 4.5-4.6 (divide and conquer examples) ADM 5.2 (war stories) Materials from class: examples: sorting — draft from class, final writeup (developing divide-and-conquer algorithms)		homework 7 due Fri 4/4 in class

Fri	Reading: developing iterative algorithms ADM 1.3, 1.4, 1.6 (reasoning about correctness, induction, proof by contradiction) big-Oh for sums Materials from class: examples: stocks — draft from class, final writeup (developing divide-and-conquer algorithms) examples: majority element — final writeup (developing divide-and-conquer algorithms) slides: developing iterative algorithms	class prep — iterative algorithms (on Canvas) due Thu 3/27 10pm
Week 10: 3/31-4/4 Topics: iterative algorithms; greedy algorithms

Mon	Materials from class: slides: developing iterative algorithms examples: assigning groups — draft from class, final writeup (to be posted) (developing iterative algorithms)				hw4 resubmit due Mon 3/31 in class feedback

Wed	exam 2 review information

Fri	Reading: developing greedy algorithms (to be posted)	class prep (to be posted) due Thu 4/3 10pm			hw5 resubmit due Fri 4/4 in class feedback
Week 11: 4/7-4/11 Topics:

Mon				design problem

Wed

Fri				programming assignment 4
Week 12: 4/14-4/18 Topics:

Mon					Graph ADT resubmit due Mon 4/14 in class hand in as `graphv2` feedback

Wed	exam 3

Fri
Week 13: 4/21-4/25 Topics:

Mon

Wed

Fri
Week 14: 4/28-5/2 Topics:

Mon

Wed

Fri
Week 15: 5/5 Topics:

Mon
Reading Period: 5/6-5/8

Tue

Wed

Thu
Final Exams: 5/9-5/12

Fri

Sat	final exam 5/10 7-10pm	end-of-semester deadline no work accepted after 5/10 10pm

Sun

Mon

CPSC 327 Schedule

Week 1: 1/21-1/24

Week 2: 1/27-1/31

Week 3: 2/3-2/7

Week 4: 2/10-2/14

Week 5: 2/17-2/21

Week 6: 2/24-2/28

Week 7: 3/3-3/7

Week 8: 3/10-3/14

Spring Break: 3/17-3/21

Week 9: 3/24-3/28

Week 10: 3/31-4/4

Week 11: 4/7-4/11

Week 12: 4/14-4/18

Week 13: 4/21-4/25

Week 14: 4/28-5/2

Week 15: 5/5

Reading Period: 5/6-5/8

Final Exams: 5/9-5/12