CPSC 327 Data Strutures and Algorithms Spring 2006

# CPSC 327 Syllabus

AssignmentsImportant Dates

### Week 1: 1/16-1/20

Topics: introduction; algorithm analysis

Reading: GT (Goodrich & Tamassia) ch 1.1-1.4, 1.6

Do the readings before coming to class, so that class time can be spent on addressing questions and trickier topics.

homework #0
due Wed 1/18

homework #1
due Fri 1/20

homework #2
due Wed 1/25

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

Topics: running time of stacks, queues, vectors, lists, sequences; introduction to searching/lookup, hash tables

Reading: GT 2.1-2.2, 1.5 (Mon); GT 2.5 (Wed)

homework #3
due Fri 1/27

homework #4
due Mon 1/30
programming exercise #1
due Fri 2/10

### Week 3: 1/30-2/3

Topics: binary search trees and balanced binary trees: AVL trees, 2-4 trees

Reading: GT 3.1.1-3.1.6, 2.3 (Mon); GT 3.2 (Wed); GT 3.3.2 (Fri)

homework #5
due Mon 2/6

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

Topics: more balanced binary trees and efficient ordered dictionary implementations: 2-4 trees, splay trees, skip lists

Reading: GT 3.3.2 (Mon); GT 3.4 (Mon); 3.5 (Wed)

homework #6
due Fri 2/10

programming exercise #2
due Fri 2/24

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

Reading: GT 4.1, 4.3 (Mon); 4.4-4.6 (Wed); 4.7 (Fri)

Examples:

### Week 6: 2/20-2/24

Topics: selection, greedy algorithms

Reading: GT 4.7 (Mon); 5.1 (Wed)

midterm #1
due Wed 3/1 at the start of class
(exam review information)

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

Topics: divide-and-conquer, recurrence relations

homework #7
due Thu 3/9

### Week 8: 3/6-3/10

Topics: divide-and-conquer

homework #8
due Fri 3/24

no class Fri 3/10 or 3/13-3/17 (spring break)

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

Topics: dynamic programming

homework #9
due Wed 3/29

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

Topics: graphs, graph implementations, graph traversal

Reading: GT 6.1, 6.2 (Mon), 6.3 (Wed)

homework #10
due Fri 3/31

homework #11
due Wed 4/5

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

Topics: directed graphs

no class Fri 4/7

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

Topics: weighted graphs

midterm #2
due Mon 4/17 at the start of class
(exam review information)

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

Topics: weighted graphs

Reading: GT 7.2 (Mon), 7.3 (Wed)

homework #12
due Fri 4/21

homework #13
due Wed 4/25

### Week 14: 4/24-4/28

Topics: priority queues; P, NP, and NP completeness; backtracking and branch-and-bound

Reading: GT 2.4 (Mon); 13.1-13.3 (Wed); 13.5 (Fri)
Skim 13.2.2 and 13.3.

extra credit programming exercise
due Tue 5/9 11:30am

homework #14
due Mon 5/1

### Week 15: 5/1-5/2

Topics: backtracking and branch-and-bound

take-home final exam
due Tue 5/9 11:30am
(exam review information)