CPSC 327 Schedule

Reading is to be done for the class period where it is listed; "ADM" refers to the textbook (The Algorithm Design Manual). Warmups are due by 10pm the night before the class for which they are listed.

Dates for things in light gray are for planning purposes and may be adjusted slightly.

		Assignments
Week 1: 1/23-1/27 Topics: course introduction; analysis of algorithms

Mon	Materials from class: slides: course introduction	introductory survey (on Canvas, under "Quizzes") due Fri 1/27

Wed	Reading: ADM 2.1-2.5 (RAM model of computation, big-Oh, growth rates and dominance relations, working with big-Oh, reasoning about efficiency) Warmup: on Canvas, under "Quizzes" Materials from class: slides: analysis of algorithms (running time, growth rate, and big-Oh)

Fri	Reading: big-Oh for sums ADM 2.7-2.8, logarithms and exponents reference (logarithms and exponents) big-Oh for recursive algorithms ADM 2.9 (war story) (optional) ADM 2.6, 5.3-5.4 (behind the sums and recurrence relations tables) Warmup: on Canvas, under "Quizzes" Materials from class: slides: analysis of algorithms (big-Oh for sums and recurrence relations; logarithms and exponents)	homework 1 due Mon 1/30 resubmit due Wed 2/8
Week 2: 1/30-2/3 Topics: analysis of algorithms; data structures: building blocks, designing implementations; containers

Mon	Reading: ADM 4.6.3 (limitations of asymptotic complexity) Warmup: no warmup (but do the reading anyway!) Materials from class: handout: big-Oh from code	homework 2 due Wed 2/1 resubmit due Wed 2/15
		homework 2 due Wed 2/1 resubmit due Wed 2/15
Wed	Reading: ADM ch 3 intro, 3.1-3.2 (review of arrays and linked lists, stacks and queues) Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw1 slides: data structures toolbox (ADTs vs data structures, categories of collections ADTs, container ADTs, linked lists)	homework 3 due Mon 2/6 resubmit due Wed 2/15
		homework 3 due Mon 2/6 resubmit due Wed 2/15
Fri	Reading: data structures toolbox (arrays vs linked lists, incremental improvement, specific strategies: tail pointers, circular array)	homework 4 due Mon 2/6 resubmit due Fri 2/17
Week 3: 2/6-2/10 Topics: data structures: searching and lookup; balanced search trees

Mon	Reading: ADM 3.3 (dictionaries) ADM 3.4-3.4.2 (BSTs) Warmup: on Canvas, under "Quizzes" Materials from class: slides: data structures toolbox (searching and lookup, Map/Dictionary and Set, binary search trees)	homework 5 due Wed 2/8 resubmit due Fri 2/17
		homework 5 due Wed 2/8 resubmit due Fri 2/17
Wed	Reading: ADM 3.4.3 (balanced search trees) AVL trees Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw2, hw3 slides: data structures toolbox (takeaways, AVL trees)	homework 6 due Fri 2/10 resubmit due Mon 2/20
		homework 6 due Fri 2/10 resubmit due Mon 2/20
Fri	Reading: 2-4 trees Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw4, hw5 slides: data structures toolbox (2-4 trees)	homework 7 due Mon 2/13 resubmit due Fri 2/24
Week 4: 2/13-2/17 Topics: hashtables; data structures: sorting; priority queues, heaps

Mon	Reading: ADM 3.7 (hashing and hashtables) Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw6 slides: data structures toolbox (other balanced BSTs (red-black, splay), hashtables - hash functions, separate chaining)	homework 8 due Fri 2/17 resubmit due Mon 2/27

Wed	Reading: ADM 4.1, 4.2, 4.4 (applications and pragmatics of sorting) ADM 3.5 (priority queues) Warmup: on Canvas, under "Quizzes" Additional reading/reference: ADM 17.1 (sorting) Materials from class: slides: comments on hw1 slides: data structures toolbox (hashtables - open addressing)

Fri	Reading: ADM 4.3 (heaps and heapsort) Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw7 slides: sorting and heaps (sorting algorithms, priority queue implementations, heaps)	homework 9 due Mon 2/20 resubmit due Mon 3/6
Week 5: 2/20-2/24 Topics: data structures toolbox; graphs

Mon	Reading: ADM 3.7.2-3.7.5 (other uses of hashing) ADM 3.6, 3.8-3.9 (custom and specialized data structures) ADM 15 intro, 15.1-15.3, 15.5-15.6 (hitchhiker's guide) - read to be aware of what is there Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw2, hw3, hw8 slides: heaps (implementation, running time, heapify) slides: data structures roundup		exam 1 due Wed 2/22 in the Assignments section on Canvas (review information) resubmit due Wed 5/10 4:30pm

Wed	Reading: ADM 7 intro, 7.1 (graphs) Warmup: on Canvas, under "Quizzes" Materials from class: slides: data structures roundup slides: graphs (terminology, modeling with graphs)	homework 10 due Fri 2/24 resubmit due Mon 4/3
		homework 10 due Fri 2/24 resubmit due Mon 4/3
Fri	Reading: ADM 7.2-7.4 (data structures for graphs) - pay attention to the data structures and how they work rather than the C code Warmup: on Canvas, under "Quizzes" Materials from class: slides: Graph ADT and implementation	homework 11 due Fri 3/3 resubmit due Mon 4/3
Week 6: 2/27-3/3 Topics: graph algorithms: traversals, best-first search, depth-first search, weighted shortest path

Mon	Reading: ADM 7.5 (graph traversals) ADM 7.6-7.7 (BFS and applications of BFS) Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw 6, 7, 9 slides: breadth-first search (graph traversal, BFS, and BFS applications)

Wed	Reading: ADM 7.8-7.10 (DFS and applications of DFS) Warmup: on Canvas, under "Quizzes" Materials from class: slides: depth-first search (graph traversal, DFS, and DFS applications)

Fri	Reading: ADM 8 intro, ADM 8.3 (weighted graph algorithms, shortest paths) Warmup: on Canvas, under "Quizzes" Materials from class: slides: weighted graph algorithms (topological sort, strongly connected components; shortest path, all pairs shortest path, transitive closure)	homework 12 due Mon 3/6 resubmit due Fri 3/17
Week 7: 3/6-3/10 Topics: minimum spanning trees; solving problems with graphs; algorithm development: establishing correctness

Mon	Reading: ADM 8.1-8.1.3, including the introduction for section 8.1 (minimum spanning trees) Warmup: on Canvas, under "Quizzes" Materials from class: slides: comments on hw5 slides: minimum spanning trees (Kruskal's algorithm, union-find data structure)	homework 13 due Mon 3/13 resubmit due Mon 4/10

Wed	Reading: ADM 8.2, 8.4, 8.7 (solving problems using graphs) ADM 8.1.4, 8.5, 8.6 (more graph algorithms) - read to be aware of what things like maximum spanning trees, network flow, bipartite matching, min-cut, etc are and how they might come up in graph modeling problem (you don't need to know algorithms or running times) ADM 18 (hitchhiker's guide) - read to be aware of what is there Warmup: on Canvas, under "Quizzes" Materials from class: slides: minimum spanning trees and roundup (Kruskal's algorithm, Prim's algorithm, other graph algorithms, recap and takeaways)

Fri	Reading: ADM 1.1-1.3 (reasoning about algorithm correctness) Warmup: on Canvas, under "Quizzes" Materials from class: slides: more graph algorithms slides: developing algorithms (correctness, incorrectness, counterexamples)
Week 8: 3/13-3/17 Topics: developing iterative algorithms

Mon	Reading: developing iterative algorithms ADM 1.4, 1.6 (proof techniques - induction, contradiction) Warmup: on Canvas, under "Quizzes" Materials from class: slides: developing iterative algorithms (12-step process)		exam 2 due Wed 3/15 in the Assignments section on Canvas (review information) resubmit due Wed 5/10 4:30pm

Wed	Materials from class: examples: region coloring (developing iterative algorithms) - in progress	homework 14 due Fri 3/17 resubmit due Wed 4/5
		homework 14 due Fri 3/17 resubmit due Wed 4/5
Fri	Materials from class: examples: region coloring (developing iterative algorithms) - in progress examples: region coloring (developing iterative algorithms) - solution/writeup
Spring Break: 3/20-3/24
Week 9: 3/27-3/31 Topics: developing iterative algorithms; developing greedy algorithms

Mon	Reading: developing greedy algorithms - complete by Mon if you can, otherwise read by Wed Materials from class: examples: comments on things handed back (exam resubmit information; comments on exam 1, exam 2, hw 10-12)	homework 15 due Wed 3/29 resubmit due Mon 4/10
		homework 15 due Wed 3/29 resubmit due Mon 4/10
Wed	Materials from class: examples: snowplowing (developing iterative algorithms) - in progress examples: snowplowing (developing iterative algorithms) - solution/writeup	homework 16 due Fri 3/31 resubmit due Mon 4/10
		homework 16 due Fri 3/31 resubmit due Mon 4/10
Fri	Materials from class: slides: developing greedy algorithms (12.5-step process) examples: driving from Boston to Seattle (developing greedy algorithms) - in progress	homework 17 due Mon 4/3 resubmit due Mon 4/24
Week 10: 4/3-4/7 Topics: developing greedy algorithms; developing recursive algorithms; divide-and-conquer

Mon	Materials from class: examples: driving from Boston to Seattle (developing greedy algorithms) - in progress examples: driving from Boston to Seattle (developing greedy algorithms) - solution/writeup	homework 18 due Wed 4/5 resubmit due Wed 4/26
		homework 18 due Wed 4/5 resubmit due Wed 4/26
Wed	Reading: developing recursive algorithms big-Oh for recursive algorithms developing divide-and-conquer algorithms Warmup: on Canvas, under "Quizzes" Materials from class: examples: callers on hold (developing greedy algorithms) - in progress examples: callers on hold (developing greedy algorithms) - solution/writeup slides: developing recursive and divide-and-conquer algorithms (15-step process)	homework 19 due Fri 4/7 resubmit due Wed 4/26
		homework 19 due Fri 4/7 resubmit due Wed 4/26
Fri	Reading: ADM 5.1, 5.2 (binary search and related algorithms) ADM 4.5-4.6 intro, 5.5-5.6 (divide-and-conquer examples) Warmup: no warmup (but do the reading anyway!) Materials from class: slides: comments on homework 10 examples: stocks (developing divide-and-conquer algorithms) - in progress	homework 20 due Mon 4/10 resubmit due Fri 4/28
Week 11: 4/10-4/14 Topics: developing recursive algorithms: divide-and-conquer, recursive backtracking, branch and bound

Mon	Materials from class: examples: hw10 - monster (developing iterative algorithms) - solution/writeup examples: stocks (developing divide-and-conquer algorithms) - in progress examples: stocks (developing divide-and-conquer algorithms) - solution/writeup examples: majority element (developing divide-and-conquer algorithms) - in progress examples: majority element (developing divide-and-conquer algorithms) - solution/writeup		exam 3 due Wed 4/12 in the Assignments section on Canvas (review information) resubmit due Wed 5/10 4:30pm

Wed	Reading: developing backtracking algorithms ADM 9-9.3 (recursive backtracking, pruning) ADM 9.4-9.5 (examples) Warmup: no warmup Materials from class: slides: recursive backtracking examples: n queens (developing recursive backtracking algorithms) - solution/writeup	homework 21 due Fri 4/14 resubmit due Wed 5/3
		homework 21 due Fri 4/14 resubmit due Wed 5/3
Fri	Reading: making recursive backtracking practical (including branch and bound) ADM 9.6-9.7 (branch and bound) Warmup: no warmup Materials from class: slides: recursive backtracking (making backtracking practical)	homework 22 due Mon 4/17 resubmit due Wed 5/3
Week 12: 4/17-4/21 Topics: dynamic programming

Mon	Reading: ADM 10-10.3 (dynamic programming) Warmup: no warmup Materials from class: slides: dynamic programming examples: longest increasing subsequence (developing dynamic programming algorithms) - in progress	homework 23 due Wed 4/19 resubmit due Mon 5/1
		homework 23 due Wed 4/19 resubmit due Mon 5/1
Wed	Reading: ADM 10.5, 10.7-10.8 (dynamic programming examples) Warmup: no warmup Materials from class: slides: comments on hw15 (iterative algorithms) examples: longest increasing subsequence (developing dynamic programming algorithms) - in progress	homework 24 due Fri 4/21 resubmit due Fri 5/5
		homework 24 due Fri 4/21 resubmit due Fri 5/5
Fri	Reading: ADM 10.4, 10.6, 10.10 (war stories) Warmup: no warmup Materials from class: slides: comments on hw15-18 (iterative and greedy algorithms) examples: longest increasing subsequence (developing dynamic programming algorithms) - in progress examples: longest increasing subsequence (developing dynamic programming algorithms) - solution/writeup	homework 25 due Mon 4/24 resubmit due Fri 5/5
Week 13: 4/24-4/28 Topics: developing algorithms: wrapup, strategies for improvement, beyond big-Oh; hard problems: reductions, complexity classes

Mon	Reading: ADM 4.7 (distribution sort) ADM 4.6.2, chapter 6 introduction (randomization as an algorithmic technique) ADM 4.6.3, 4.8 (beyond big-Oh) (optional) ADM chapter 6 (randomized algorithms) Warmup: no warmup Materials from class: slides: developing algorithms (recap, strategies for improvement)	homework 26 due Fri 5/5

Wed	Reading: ADM 11.1-11.8 (reductions) Warmup: on Canvas, under "Quizzes" Materials from class: slides: developing algorithms (strategies for improvement - heuristics, randomization, data structures; beyond big-Oh) slides: reductions examples: reductions

Fri	Reading: ADM 11.9 (P vs NP) Warmup: on Canvas, under "Quizzes" Materials from class: examples: reductions slides: complexity
Week 14: 5/1-5/5 Topics: dealing with NP-complete problems; wrapup

Mon	Reading: ADM 9.6-9.7 (best-first search, A) ADM 12.6-12.9 (heuristic seach methods) Warmup:* no warmup Materials from class: slides: complexity (P/NP/FP/FNP, P- and NP-complete, reductions for lower bounds and completeness)	homework 27 due Wed 5/3 resubmit due Wed 5/10
		homework 27 due Wed 5/3 resubmit due Wed 5/10
Wed	Reading: ADM 12.1-12.5 (approximation) Warmup: no warmup Materials from class: slides: complexity (Cook-Levin, hardness, dealing with NP-complete problems) slides: comments on exam 3 (and a reminder of the rules/information for exam resubmits) solutions/examples: time-o problem (homework 23)	homework 26 (continued) due Fri 5/5
		homework 26 (continued) due Fri 5/5
Fri	Reading: browse ADM part II (chapters 14-22) - for each chapter, read the introduction, skim the section titles, and pick one or two unfamiliar problems to read about Warmup: no warmup Materials from class: slides: complexity (local search, dealing with local minima; approximation) slides: wrapup (designing algorithms and data structures, course takeaways, a few useful problems) solutions/examples: captioning problem (homework 16), watersheds problem (homework 19), challenges problem (homework 24)
Reading Period: 5/6-5/8

Sat

Sun

Mon	review session 10am-noon (Lansing 301) office hours 12:30-2:30pm Materials from class: solutions/examples: winning-the-series problem (homework 24) solutions/examples: print jobs scheduling (homework 18)
Final Exams: 5/9-5/12

Tue	office hours 11:30-1:30pm

Wed	office hours 11:30-1:30pm	end-of-semester deadline no work accepted after 5/10 4:30pm	final exam due 5/10 4:30pm in the Assignments section on Canvas (available after 5/8 12pm) (review information)

Thu

Fri

CPSC 327 Schedule

Week 1: 1/23-1/27

Week 2: 1/30-2/3

Week 3: 2/6-2/10

Week 4: 2/13-2/17

Week 5: 2/20-2/24

Week 6: 2/27-3/3

Week 7: 3/6-3/10

Week 8: 3/13-3/17

Spring Break: 3/20-3/24

Week 9: 3/27-3/31

Week 10: 4/3-4/7

Week 11: 4/10-4/14

Week 12: 4/17-4/21

Week 13: 4/24-4/28

Week 14: 5/1-5/5

Reading Period: 5/6-5/8

Final Exams: 5/9-5/12