CPSC 327  Data Structures and Algorithms  Spring 2009 
Assignments  Important Dates  

Week 1: 1/191/23Topics: introduction; algorithm analysis 

Mon  
Wed  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 Fri 1/23 

Fri  homework
#2 due Mon 1/26 

Week 2: 1/261/30Topics: applying algorithm analysis, motivating applications (sorting and lookup) 

Mon  homework
#3 due Wed 1/28 

Wed  Reading:
Thinking Problems:
Notes: 
homework
#4 due Fri 1/30 
project
#1 due Wed 2/11 

Fri  homework
#5 due Mon 2/2 

Week 3: 2/22/6Topics: iterative algorithms 

Mon 
Reading: Edmonds ch 1
Thinking Problem: Using example 1.4.1, write down code or pseudocode for an actual implementation of selection sort. Point out how the code matches up with the 11 steps given e.g. how is the measure of progress reflected in the code. 
homework
#6 due Wed 2/4 

Wed 
Reading: Edmonds ch 2
Thinking Problem: Section 2.2 talks about "bounded memory"  in other words, the algorithm is only allowed to use Θ(1) space. Step 4 of example 2.2.1 states that this requirement means we cannot simply count the number of 0s and 1s in the input. (a) Write down an expression for n, the input size, in terms of bits. (b) Write down an (exact) expression S(n) for the space needed to store counts of the number of 0s and the number of 1s in the input. (c) What is the bigTheta for your S(n)? 
homework
#7 due Fri 2/6 

Fri 
Reading: Edmonds ch 4, 5
Thinking Problem: We came up with two ideas for the fractional knapsack problem: plan A takes the weight of items in the pack as the measure of progress and the loop invariant is that we have the best value for the current weight, and plan B takes the number of items considered as the measure of progress and the loop invariant is that we have the best value for items 1..i (those considered so far). For each of these two plans, identify the main steps, show that the loop invariant is established/maintained, and explain what the running time is. Do not assume that the items have first been sorted in any particular order. Notes: 

Week 4: 2/92/13Topics: recursion and recurrence relations 

Mon  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. Notes: 

Wed  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: 
homework
#8 due Fri 2/13 

Fri  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: 
homework
#9 due Mon 2/16 

Week 5: 2/162/20Topics: divideandconquer algorithms 

Mon  Thinking Problem: Design an
algorithm for finding both the smallest and largest numbers in an
array of size n using only 3n/2 comparisons. Give your algorithm
in code or pseudocode, and justify why only 3n/2 comparisons are
needed.
Notes: 
homework
#10 due Wed 2/18 

Wed  Thinking Problem: Revisit the VSLI chip testing algorithm
from section 4.3. Give a recursive algorithm for solving this
problem. (Follow the steps in section 8.3.)
Notes: 
midterm #1 due Mon 2/23 in class (review information) 

Fri  class rescheduled for Tue 2/24 at 10am  
Week 6: 2/232/27Topics: divideandconquer algorithms; ADTs and data structures 

Mon  Notes:  homework
#11 due Wed 2/25 

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


Wed  Notes:

homework
#12 due Fri 2/27 

Fri  homework
#13 due Mon 3/2 

Week 7: 3/23/6Topics: trees 

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

Fri  class rescheduled for Tue 3/10 at 10am  project
#2 due Mon 3/30 

Week 8: 3/93/12Topics: trees 

Mon 
Reading:
Thinking Problems:
Notes: 
homework
#14 due Thu 3/12 5pm 

Tue 
Notes: 

Wed 
Notes: 

Thu  
Spring Break 

Week 9: 3/233/27Topics: graphs and graph algorithms 

Mon  
Wed  Reading: Edmonds ch 14
Thinking Problems:
Notes: 
homework
#15 due Fri 3/25 

Fri  Notes:  
Week 10: 3/304/3Topics: graph algorithms; greedy algorithms 

Mon  Notes:  homework
#16 due Wed 4/1 

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: 
midterm #2 due Mon 4/6 in class (review information) 

Fri  Reading: Edmonds ch 16.2.116.2.2
Notes:


Week 11: 4/64/10Topics: greedy algorithms; recursive backtracking and branchandbound 

Mon  Notes:

homework
#17 due Wed 4/8 

Wed  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
#18 due Fri 4/10 

Fri  Notes:  homework
#19 due Mon 4/13 

Week 12: 4/134/17Topics: branchandbound; dynamic programming 

Mon  Notes:  homework
#20 due Wed 4/15 

Wed  Reading: Edmonds ch 18
Thinking Problems:

homework
#21 due Fri 4/17 

Fri  Reading: Edmonds ch 19.119.4 (do at least one section for
Friday and the rest for next Monday)
Notes: 
homework
#22 due Mon 4/20 

Week 13: 4/204/24Topics: dynamic programming; reductions 

Mon  Reading: the rest of Edmonds ch 19.119.4
Notes:

homework
#23 due Wed 4/22 
project
#3 due Tue 5/5 

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:


Fri  Notes:  
Week 14: 4/275/1Topics: NPcompleteness 

Mon 
Reading: Edmonds ch 2020.1 (introductory
material and section 20.1)
Thinking Problem: exercise 20.1.1 (choose three of the parts) Notes: 
homework
#24 due Fri 5/1 

Wed  Reading: Edmonds ch 20.220.3  
Fri  Notes:  
Week 15: 5/45/5Topics: nifty data structures (splay trees and skip lists) 

Mon  Notes:  
Tue  
Reading Period & Exams: 5/65/12 

Wed  
Thu  
Fri  
Sat  
Sun  
Mon  
Tue  endofsemester deadline no work accepted after 5/12 at noon 
final exam due Tue 5/12 at noon (review information) 