CPSC 327  Data Structures and Algorithms  Spring 2010 
Readings are to be done before the class period where they are listed. Dates for assignments shown in gray are tenative and are subject to change.
Assignments  

Week 1: 1/201/22Topics: introduction; algorithm analysis 

Wed  
Fri  Reading: Edmonds ch 23.1, 24 (review if you aren't
familiar with the mathematics of logs and exponents), 25
(introduction and section 25.1 only), 26 (introduction and section
26.1 only)
Thinking Problem: An algorithm takes n English words as input. Is the number of words a fair measure of input size? Explain. 
homework #1 due 

Week 2: 1/251/29Topics: algorithm analysis 

Mon  Notes: bigTheta  
Wed  Notes: bigTheta for sums, sums from algorithms 
homework #2 due Fri 1/29 

Fri  Notes: homework #1, sums from algorithms  project #1: Sort
Analysis due Fri 2/12 

Week 3: 2/12/5Topics: iterative algorithms 

Mon  Reading: Edmonds ch 1
Thinking Problem: Using example 1.4.3, write down code or pseudocode for an actual implementation of binary search. Point out how the code matches up with the 11 steps given. (What lines of code correspond to which of the steps?) Notes: iterative algorithms 
homework #3 due Wed 2/3 

Wed  Reading: Edmonds ch 2 
homework #4 due Fri 2/5 

Fri  Reading: Edmonds ch 4, 5 (no thinking problem)
Notes: monsters and graph coloring 
homework #5 due Mon 2/8 

Week 4: 2/82/12Topics: iterative algorithms; recursion and recurrence relations 

Mon  Notes: fractional knapsack, more of the output, narrowing the search space  
Wed  Reading: Edmonds ch 8, 9 (skip the discussions of running
times in ch 9)
Thinking Problem: Construct a recursive algorithm for the task of finding the smallest element in an array. (Yes, I know there is a simple iterative algorithm. That's not the point here.) Write your algorithm in code or pseudocode, and demonstrate that you satisfied the checklist for recursive algorithms in section 8.5. 

Fri  Reading: Edmonds ch 27.1
Thinking Problem: Do either #1 or #2 and any one of #3#7 (two problems total) from exercise 27.1.1 (pages 400401)  without looking at the solution in the back of the book. Notes: recurrence relations 
homework #6 due Mon 2/15 

Week 5: 2/152/19Topics: recursion and recurrence relations; divideandconquer 

Mon  Reading: Edmonds ch 9 (the discussions of running times
this time)
Thinking Problem: In general, having fewer subproblems and reducing the amount of work needed to create and combine subproblems will make a recursive algorithm run faster. But what about specific advice? Imagine that you've developed a recursive algorithm with a time T(n) = a T(n/b) + f(n). Would it be more productive to think about how to reduce the number of subproblems (as was done in the exponentiation, multiplication, and matrix multiplication examples) or how to reduce the work done splitting/combining? Does your answer depend on the particular equation for T(n)? If so, how? Notes: messy sums 
homework #7 due Wed 2/17 

Wed  Notes: T(n) = T(n/4)+T(3n/4)+n, designing recursive algorithms 
homework #8 due Fri 2/19 

Fri  Notes: designing recursive algorithms (recursive vs iterative spirit, min/max with 3n/2 comparisons, stock problem)  midterm
#1 due Wed 2/24 in class 

Week 6: 2/222/26Topics: divideandconquer; ADTs 

Mon  Notes: designing recursive algorithms (VLSI chip problem)  
Wed  Notes: designing recursive algorithms (recap of method, skyline, approaching a new problem) 
homework #9 due Fri 2/26 

Fri  Reading: Edmonds ch 3
Thinking Problem: Categorize the ADTs presented in the reading according to how elements are positioned and the primary kinds of methods the collection supports:
Notes:

homework #10 due Mon 3/1 
project #2:
Algorithm X due Fri 3/12 
Week 7: 3/13/5Topics: ADTs; implementing ADTs 

Mon  Notes: 
homework #11 due Wed 3/3 

Wed  Reading: Edmonds ch 10
Thinking Problem: exercise 10.4.1 (page 149), without looking at the solutions in the back of the book Notes: 

Fri  Reading:
Thinking Problems:
Notes: 

Week 8: 3/83/12Topics: implementing ADTs: more data structures 

Mon  Notes: 
homework #12 due Wed 3/10 

Wed  Reading:
Thinking Problems:


Fri  no reading  
Spring Break 

Week 9: 3/223/26Topics: graphs and graph algorithms 

Mon  Notes: 
homework #13 due Fri 3/26 

Wed  Reading: Edmonds ch 14.1, 14.414.5
Thinking Problem: exercise 14.1.1 (page 178) Notes: 

Fri  Reading: Edmonds ch 14.214.3, 14.6
Thinking Problem: exercise 14.3.3 #4, #5 only (page 188) Notes: 
homework #14 due Mon 3/29 

Week 10: 3/294/2Topics: graph algorithms; greedy algorithms 

Mon  Notes:  project
#3: Travel Agent due 

Wed  Reading: Edmonds ch 16.1, 16.2.3
Thinking Problem: exercise 16.1.1 (page 235) [justify your answer in the style of the proof in the chapter (a proof or a counterexample)  don't just state "yes" or "no"] Notes: 

Fri  Reading: Edmonds ch 16.2.116.2.2
Notes: 

Week 11: 4/54/9Topics: greedy algorithms 

Mon  Notes: 
homework #15 due Wed 4/7 

Wed  Notes: 
homework #16 due Fri 4/9 

Fri  Notes:  
Week 12: 4/124/16Topics: recursive backtracking / branchandbound 

Mon  Reading: Edmonds ch 17
Thinking Problem: exercise 17.5.1 (page 265), without looking at the solutions in the back of the book Notes: 
homework #17 due Wed 4/14 

Wed  Notes:  midterm
#2 due Mon 4/19 in class 

Fri  Notes:  
Week 13: 4/194/23Topics: dynamic programming 

Mon  Reading: Edmonds ch 18.118.2
Thinking Problems:
Notes: 
homework #18 due Wed 4/21 
project
#4: TSP due Tue 5/4 
Wed  Reading: Edmonds ch 18.3
Thinking Problem: List two pieces of advice and/or strategies for developing dynamic programming algorithms. Notes: 

Fri  Reading: Edmonds ch 19.119.4
Notes: 
homework #19 due Wed 4/28 

Week 14: 4/264/30Topics: dynamic programming; reductions and complexity 

Mon  Notes:  
Wed 
Reading: Edmonds ch 19.8
Thinking Problem: exercise 19.8.1 (just explain how map the elephant problem to the graph problem, and how to turn a solution to the graph problem into a solution for the elephant problem  you do not need to repeat how to solve the graph problem) Notes: 
(optional) homework #20 due Sun 5/9 4:30 handin by Thu 5/6 encouraged 

Fri 
Reading: Edmonds ch 20 (read 20.220.3 just to get an overview
of the ideas)
Thinking Problem: exercise 20.1.1 (choose three of the parts) Notes: 

Week 15: 5/35/4Topics: complexity 

Mon  Notes:  
Exams: 5/85/11 

Sat  
Sun  endofsemester super
deadline no work accepted after 5/9 4:30pm 
final exam due Sun 5/9 4:30pm 

Mon  
Tue 