CPSC 327 Syllabus

Week 1: 1/22-1/24

Topics: introduction; iterative algorithms

Notes:

• slides (15 steps to iterative success)
• reversing linked list example

Week 2: 1/27-1/31

Topics: iterative algorithms; algorithm analysis

• slides (examples of developing iterative algorithms)

• slides (examples of developing iterative algorithms, advice on the process)
• 2D array searching, monster problem examples

Notes:

• slides (algorithm analysis - introduction, definitions)
• big-Oh examples

Reference:

• log and exponent rules

Week 3: 2/3-2/7

Topics: algorithm analysis

• slides (hw 2 comments)
• big-Oh examples

• slides (hw 2 and 4 comments, T(n) from algorithms)

Our interest in chapter 1 is practicing determining running times and a closer consideration of the notion of "input size", so we will only cover a small part of the chapter (and thus only a few sections are required). The book's theme is the interesting contrast in difficulty between factoring (determining a number's prime factors) and primality (determining if a number is prime). It is well worth reading the whole chapter for that reason, or if you are interested in cryptography.

Notes:

• slides (T(n) from algorithms, sums)
• sums, comb sort examples
• Θ from sums table

Week 4: 2/10-2/14

Topics: recursive algorithms; divide-and-conquer; recurrence relations

• slides (hw 3 comments)
• slides (developing recursive algorithms)
• example of developing a recursive algorithm using the steps

Notes:

• slides (sums, recursive algorithms, recurrence relations)
• examples - sums, recursive algorithms, recurrence relations
• Θ for recurrence relations table

Notes:

• slides (notes on developing recursive algorithms, divide-and-conquer)

Week 5: 2/17-2/21

Topics: recurrence relations; divide-and-conquer

Notes:

• slides (notes on homeworks 9 and 10, divide-and-conquer)

Notes:

• slides (divide-and-conquer - narrowing the search space, more of the output)

• slides (divide-and-conquer, unwinding recurrence relations)

Week 6: 2/24-2/28

Topics: graphs and graph algorithms

Notes:

• slides (notes on hw 11 / developing recursive algorithms)
• slides (graphs - applications, ADT)

Things to pay attention to in the reading: the algorithms themselves (DFS, checking connectivity, finding directed cycles, strongly connected components), how the algorithms build on DFS, and the strategies for arguing correctness.

Notes:

• unwinding recurrence relations example
• slides (graph ADT implementation - edge list)

Things to pay attention to in the reading: the algorithms themselves (BFS, Dijsktra's algorithm), how the algorithms build on BFS, and the strategies for arguing correctness.

Notes:

• slides (hw 12, divide-and-conquer comments; graph ADT implementation)

Week 7: 3/3-3/7

Topics: graph algorithms

• slides (dfs-based graph algorithms)

• slides (dfs-based graph algorithms)

Notes:

• slides (prerequisites example, breadth-first search, Dijkstra's algorithm)

Week 8: 3/10-3/14

Topics: graph algorithms; data structures (priority queues, heaps)

Notes:

• slides (shortest paths with negative weight edges, examples of problems solved with graph algorithms)

Notes:

• slides (priority queues, heaps)

Spring Break: 3/17-3/21

Week 9: 3/24-3/28

Topics: greedy algorithms

• slides (travel agent algorithms)
• more discussion of the travel agent algorithms

Notes:

• slides (greedy algorithms, event scheduling)

• slides (greedy algorithms - driving to Seattle, most popular CD)

Week 10: 3/31-4/4

Topics: greedy algorithms

• slides (greedy algorithms - Kruskal's MST algorithm)

• slides (greedy algorithms - on hold; union-find)

• slides (union-find conclusion, Prim's algorithm)

Week 11: 4/7-4/11

Topics: dynamic programming

Notes:

• slides (dynamic programming)

Notes:

• slides (dynamic programming)
• print jobs scheduling discussion

Notes:

• slides (dynamic programming)

Week 12: 4/14-4/18

Topics: recursive backtracking, branch-and-bound

• slides (recursive backtracking, branch-and-bound)

• slides (dynamic programming)

• slides (branch and bound, a bit on linear programming and integer programming)

Week 13: 4/21-4/25

Topics: complexity and reductions

Notes:

• slides (algorithm techniques recap, reductions)

Notes:

• slides (complexity)

• slides (complexity)

Week 14: 4/28-5/2

Topics: balanced trees; rolling your own data structures

• slides (AVL trees, 2-4 trees)

• slides (bound functions, initial solution estimates for TSP, maximum independent set)
• slides (2-4 trees - insert, remove)

• slides (red-black trees, splay trees)

Week 15: 5/5-5/6

Topics: wrapup

• slides (algorithm and data structure development)
• ADT taxonomy
• solution for hw 22 #1b

Reading Period: 5/7-5/9

Final Exams: 5/10-5/13

• review information

last updated: --Mon May 5 16:38:04 EDT 2014--
page owned by: bridgeman@hws.edu