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.


Week 1: 1/22-1/24

Topics: introduction; iterative algorithms


Wed   homework #0
due Fri 1/24

Fri Reading: DPV section 0.1


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

Fri Reading: DPV section 0.2-0.3



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.


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

Wed Reading: DPV section 2.1


homework #9
due Fri 2/14

Fri Reading: DPV section 2.2


  • 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


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

Wed Reading: DPV section 2.4


  • 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


Mon Reading: DPV section 3.1


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

Wed Reading: DPV sections 3.2-3.4

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.


homework #14
due Fri 2/28

Fri Reading: DPV sections 4.1-4.4

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.


  • slides (hw 12, divide-and-conquer comments; graph ADT implementation)
  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

Fri Reading: DPV sections 4.6-4.7


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

Week 8: 3/10-3/14

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


Mon Reading: DPV section 4.5


  • 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

Fri Reading: DPV section 5.2-5.4


  • slides (priority queues, heaps)

Spring Break: 3/17-3/21


Week 9: 3/24-3/28

Topics: greedy algorithms


Mon Notes:  

Wed Reading: DPV sections 5.2-5.4
(if not already done)


  • 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


Mon Reading: DPV sections 6.1-6.2


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

Wed Reading: DPV sections 6.3-6.5


homework #19
due Fri 4/11

Fri Reading: DPV sections 6.6-6.7


  • 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


Mon Reading: DPV sections 8.1-8.2


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

Wed Reading: DPV sections 8.3



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)

Week 15: 5/5-5/6

Topics: wrapup


Mon Notes:  

Reading Period: 5/7-5/9





Final Exams: 5/10-5/13



final exam
due Sun 5/11 4:30pm
end-of-semester deadline
no work accepted after 5/11 4:30pm



Valid HTML 4.01!