CPSC 327 Data Structures and Algorithms Spring 2014

# CPSC 327 Syllabus

Readings are to be done for the class period where they are listed.

Dates for things in light gray are tentative and may shift slightly.

Assignments

### Week 1: 1/22-1/24

Topics: introduction; iterative algorithms

Wed   homework #0
due Fri 1/24

Notes:

homework #1
due Mon 1/27

### Week 2: 1/27-1/31

Topics: iterative algorithms; algorithm analysis

Mon Notes:
• slides (examples of developing iterative algorithms)
homework #2
due Wed 1/29

Wed Notes:
homework #3
due Fri 1/31

Notes:

Reference:

homework #4
due Mon 2/3

### Week 3: 2/3-2/7

Topics: algorithm analysis

Mon Notes:
homework #5
due Wed 2/5

Wed Notes:
• slides (hw 2 and 4 comments, T(n) from algorithms)
homework #6
due Fri 2/7

Fri Reading: DPV sections 1.1, 1.2.3

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:

homework #7
due Mon 2/10

### Week 4: 2/10-2/14

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

Mon Notes:
homework #8
due Wed 2/12

Notes:

homework #9
due Fri 2/14

Notes:

• slides (notes on developing recursive algorithms, divide-and-conquer)
homework #10
due Mon 2/17

### Week 5: 2/17-2/21

Topics: recurrence relations; divide-and-conquer

Mon Reading: DPV sections 2.3, 2.5

Notes:

• slides (notes on homeworks 9 and 10, divide-and-conquer)
homework #11
due Wed 2/19

Notes:

• slides (divide-and-conquer - narrowing the search space, more of the output)
homework #12
due Fri 2/21

Fri Notes:
• slides (divide-and-conquer, unwinding recurrence relations)
homework #13
due Mon 2/24

### 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:

homework #14
due Fri 2/28

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:

midterm 1
due Wed Mar 5

(review information)

### Week 7: 3/3-3/7

Topics: graph algorithms

Mon Notes:
• slides (dfs-based graph algorithms)

Wed Notes:
• slides (dfs-based graph algorithms)
programming assignment 1
Travel Agent
part 0 due Wed Mar 12

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)

Wed Reading: DPV section 5.1   programming assignment 1
Travel Agent
rest due Mon Apr 7

Notes:

• slides (priority queues, heaps)

### Week 9: 3/24-3/28

Topics: greedy algorithms

Mon Notes:

Notes:

• slides (greedy algorithms, event scheduling)
homework #15
due Fri 3/28

Fri Notes:
• slides (greedy algorithms - driving to Seattle, most popular CD)
homework #16
due Mon 3/31

### Week 10: 3/31-4/4

Topics: greedy algorithms

Mon Notes:
• slides (greedy algorithms - Kruskal's MST algorithm)
homework #17
due Fri 4/4

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

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

### Week 11: 4/7-4/11

Topics: dynamic programming

Notes:

• slides (dynamic programming)
homework #18
due Wed 4/9

Notes:

homework #19
due Fri 4/11

Notes:

• slides (dynamic programming)
midterm 2
due Wed Apr 16

(review information)

### Week 12: 4/14-4/18

Topics: recursive backtracking, branch-and-bound

Mon Notes:
• slides (recursive backtracking, branch-and-bound)

Wed Notes:
• slides (dynamic programming)
homework #20
due Fri 4/18

Fri Notes:
• slides (branch and bound, a bit on linear programming and integer programming)
homework #21
due Wed 4/22

### Week 13: 4/21-4/25

Topics: complexity and reductions

Notes:

• slides (algorithm techniques recap, reductions)
programming assignment 2
TSP
due Tue May 6

Notes:

Fri Notes:

### Week 14: 4/28-5/2

Topics: balanced trees; rolling your own data structures

Mon Notes:
• slides (AVL trees, 2-4 trees)
homework #22
due Wed 4/30

Wed Notes:
• slides (bound functions, initial solution estimates for TSP, maximum independent set)
• slides (2-4 trees - insert, remove)
homework #23
due Fri 5/2

Fri Notes:
• slides (red-black trees, splay trees)

Topics: wrapup

Mon Notes:

Wed

Thu

Fri

### Final Exams: 5/10-5/13

Sat

Sun
final exam
due Sun 5/11 4:30pm