CPSC 327 Data Structures and Algorithms Spring 2016

CPSC 327 Syllabus

Reading is to be done for the class period where it is listed.

Note on reading the war stories: you may not be familiar with all of the techniques, algorithms, or data structures mentioned in the stories. That's OK - read the war stories for what they illustrate about the real world of developing algorithms rather than for necessarily understanding every detail of the algorithm. (Though feel free to ask about things!)

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

Note on homework problems: [PC] denotes a pre-class problem - these are intended as part of the first exposure to the material and are graded primarily on effort. You should try to do these problems yourself before discussing with others (if you discuss). [P] denotes a practice problem - these are meant for practice applying things that have been discussed in class and are graded primarily on correctness. Both kinds of problems are due when the homework is due.


Week 1: 1/19-1/22

Topics: course introduction, introduction to algorithm design, analysis of algorithms


Wed Reading:
  • ADM chapter 1 introduction
  • ADM sections 1.1-1.2, 1.3-1.6
homework 1
due Fri 1/22

Fri Reading:
  • ADM chapter 2 introduction
  • ADM sections 2.1-2.8
Reference: Slides and Examples:
homework 2
due Mon 1/25

Week 2: 1/25-1/29

Topics: analysis of algorithms, review of basic ADTs and data structures, lookup


Mon Slides: homework 3
due Wed 1/27

Wed Reading:
  • ADM chapter 3 introduction
  • ADM sections 3.1-3.2
homework 4
due Fri 1/29

Fri Reading:
  • ADM sections 3.3-3.4
homework 5
due Mon 2/1

Week 3: 2/1-2/5

Topics: balanced binary trees; hashtables


Mon Reading: Slides: homework 6
due Wed 2/3

Wed Reading: Slides: homework 7
due Fri 2/5

Fri Reading:
  • ADM sections 3.7, 3.9
homework 8
due Mon 2/8

Week 4: 2/8-2/12

Topics: ordered sequences (priority queues, heaps); other data structures (and rolling your own); searching and sorting


Mon Reading:
  • ADM sections 3.5
  • ADM sections 4.3.1-4.3.4
homework 9
due Wed 2/10

Wed Reading:
  • ADM sections 3.6, 3.9
homework 10
due Fri 2/12

Fri Reading:
  • ADM sections 4.1-4.2, 4.4
  project 1
Code Breaker

due Fri 3/4

Week 5: 2/15-2/19

Topics: sorting and searching, iterative algorithms


Mon Reading:
  • ADM sections 4.3 (introduction), 4.3.5, 4.4-4.9
homework 11
due Wed 2/17

Wed Reading: Slides and Examples: homework 12
due Fri 2/19

Fri Slides and Handouts: homework 13
due Mon 2/22

Week 6: 2/22-2/26

Topics: greedy algorithms

Mon Reading: Slides and Examples:  

Wed Slides and Examples: homework 14
due Fri 2/26

Fri Slides and Examples: homework 15
due Mon 2/29

Week 7: 2/29-3/4

Topics: iterative and greedy algorithms, divide-and-conquer algorithms, recurrence relations

Mon Slides and Examples: homework 16
due Wed 3/2

Wed Reading: Slides and Examples:  

Fri Slides and Examples:   exam 1
(review information)
(comments and partial solutions)

Week 8: 3/7-3/11

Topics: divide-and-conquer


Mon Slides and Examples:  

Wed Slides and Examples: homework 17
due Mon 3/21
project 2
Iterative, Greedy, Divide-and-Conquer

due Wed 4/6

Fri meet with your group to work on project 2

Spring Break: 3/12-3/20

Week 9: 3/21-3/25

Topics: solving recurrence relations; graphs - applications, ADT, implementation, traversal

Mon Slides: homework 18
due Wed 3/23

Wed Reading:
  • ADM sections 5.1-5.4
homework 19
due Fri 3/25

Fri Reading:
  • ADM sections 5.5-5.7

Week 10: 3/28-4/1

Topics: graphs - traversal, shortest paths, solving problems with graphs


Mon Slides: homework 20
due Wed 3/30

Wed Reading:
  • ADM sections 6.3-6.4
homework 21
due Fri 4/1

Fri Reading:
  • ADM sections 5.8-5.10

Week 11: 4/4-4/8

Topics: solving problems with graphs, minimum spanning trees


Mon Reading:
  • ADM sections 6.2, 6.6

Wed Reading:
  • ADM section 6.1
  exam 2
(review information)

Fri Reading: Slides and Examples:  

Week 12: 4/11-4/15

Topics: backtracking, pruning, branch and bound, heuristic search


Mon Reading:
  • ADM sections 7.1-7.4
homework 22
due Wed 4/13
project 3
Finding Your Way

due Tue 5/3

Wed Slides: homework 23
due Mon 4/18

Fri Reading:
  • ADM sections 7.5-7.8
  • branch-and-bound (with some comments on recursive backtracking structure and tactics, plus things not covered in class: another example of bound functions, strategies for efficient generation of partial solutions and subproblems, and an important application of branch and bound)

Week 13: 4/18-4/22

Topics: dynamic programming

Mon Reading:
  • ADM sections 8.1-8.3
homework 24
due Wed 4/20

Wed Reading:
  • ADM sections 8.4-8.6
Slides and Examples:
homework 25
due Fri 4/22

Fri Reading:
  • ADM sections 8.7-8.9
Slides and Examples:
homework 26
due Mon 4/25

Week 14: 4/25-4/29

Topics: reductions, complexity, dealing with NP-complete problems

Mon Reading:
  • ADM sections 9.1-9.5
Slides and Examples:
homework 27
due Wed 4/27

Wed Reading:
  • ADM sections 9.6-9.9

Fri Reading:
  • ADM section 9.10
Slides and Notes:

Week 15: 5/2-5/3

Topics: how to design algorithms, wrapup


Mon Reading:
  • ADM chapter 10
  • ADM part II - browse to get a sampling of what's there, then read at least one section in chapters 12, 15, or 16
Slides: Homework Solutions:

Reading Period: 5/4-5/6


Wed office hours 1-3pm    

Thu office hours 1-3pm    

Fri office hours 10:30-12 and 1:30-3pm    

Exams: 5/7-5/10




final exam
Mon 5/9 8:30-11:30am
end-of-semester deadline
no work accepted after 5/9 11:30am


Valid HTML 4.01!