CPSC 327 Syllabus

Week 1: 1/20-1/22

Topics: introduction; algorithm analysis

Thinking Problem: An algorithm takes n English words as input. Is the number of words a fair measure of input size? Explain.

Notes: time and space complexity, growth rates, big-Theta

Week 2: 1/25-1/29

Topics: algorithm analysis

Week 3: 2/1-2/5

Topics: iterative algorithms

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

Notes: iterative algorithms, more-of-the-input

Notes: monsters and graph coloring

Week 4: 2/8-2/12

Topics: iterative algorithms; recursion and recurrence relations

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: searching a sorted matrix, recursion

Thinking Problem: Do either #1 or #2 and any one of #3-#7 (two problems total) from exercise 27.1.1 (pages 400-401) - without looking at the solution in the back of the book.

Notes: recurrence relations

Week 5: 2/15-2/19

Topics: recursion and recurrence relations; divide-and-conquer

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

Week 6: 2/22-2/26

Topics: divide-and-conquer; ADTs

Thinking Problem: Categorize the ADTs presented in the reading according to how elements are positioned and the primary kinds of methods the collection supports:

• how elements are positioned: algorithmically (the ADT determines how elements are arranged) or manually (the user of the ADT has control over how elements are arranged)
• what methods the collection supports: determine if an element is a member of the collection, after/before (methods based on ordering of elements), access elements with highest priority, access elements at any position, access elements only at ends (first/last)

Notes:

• designing recursive algorithms (closest pair of points)
• designing ADTs and data structures (development strategy, conceptual design)

Week 7: 3/1-3/5

Topics: ADTs; implementing ADTs

• ADTs, implementing ADTs

Thinking Problem: exercise 10.4.1 (page 149), without looking at the solutions in the back of the book

Notes:

• implementing ADTs, motivating heaps

• AVL trees: source 1, source 2
• 2-4 trees: source 1, source 2

Thinking Problems:

1. Insert the elements 50, 60, 70, 20, 10, 25, 40, 30, 28 into an initially empty AVL tree, drawing the tree after each step.
2. Insert the elements 5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1 into an initially empty 2-4 tree, drawing the tree after each step.

Notes:

• heaps

Week 8: 3/8-3/12

Topics: implementing ADTs: more data structures

• AVL trees, 2-4 trees

• Hashtables (skip the parts with code, and the sections titled "Interface for..." and "Implementation of...")
• Problems with Hash Tables

Thinking Problems:

• How do you delete an element from a hashtable?
• How likely are collisions? Do a calculation: assuming that each day is equally likely as someone's birthday, what is the probability that there are no shared birthdays in a class of 30 students?

• project 1 comments, 2-4 trees, hashtables

Spring Break

Week 9: 3/22-3/26

Topics: graphs and graph algorithms

• hw/exam/project comments, ADT/data structure recap, graph ADT

Thinking Problem: exercise 14.1.1 (page 178)

Notes:

• implementing the Graph ADT

Thinking Problem: exercise 14.3.3 #4, #5 only (page 188)

Notes:

• graph algorithms: reachability

Week 10: 3/29-4/2

Topics: graph algorithms; greedy algorithms

• ADTs vs implementations; graph algorithms: reachability, shortest path

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:

• graph running times hw comments, shortest path correctness

Notes:

• shortest path correctness, greedy algorithms, Dijkstra's algorithm

Week 11: 4/5-4/9

Topics: greedy algorithms

• Dijkstra's algorithm, minimum spanning tree

• "staying ahead" arguments (MST, making change)

• "staying ahead" arguments (making change, fractional knapsack, event scheduling)

Week 12: 4/12-4/16

Topics: recursive backtracking / branch-and-bound

Thinking Problem: exercise 17.5.1 (page 265), without looking at the solutions in the back of the book

Notes:

• driving to Seattle, recursive backtracking

• branch and bound

• branch and bound

Week 13: 4/19-4/23

Topics: dynamic programming

Thinking Problems:

1. The book discusses turning a recursive backtracking algorithm into an iterative dynamic programming algorithm. Does a dynamic programming algorithm have to be iterative? That is, could you write it recursively without changing the big-Oh? Explain.
2. Where does the polynomial running time come from?

Notes:

• branch and bound wrapup, dynamic programming

Thinking Problem: List two pieces of advice and/or strategies for developing dynamic programming algorithms.

Notes:

• dynamic programming - 0-1 knapsack wrapup, longest common subsequence

Notes:

• dynamic programming - longest common subsequence, weighted interval scheduling

Week 14: 4/26-4/30

Topics: dynamic programming; reductions and complexity

• dynamic programming - matrix chain product, dynamic programming wrapup

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:

• technique summary
• adapting algorithms and a bit of reductions

Thinking Problem: exercise 20.1.1 (choose three of the parts)

Notes:

• reductions

Week 15: 5/3-5/4

Topics: complexity

• complexity and wrapup

Exams: 5/8-5/11

last updated: --Mon May 3 15:36:29 EDT 2010--
page owned by: bridgeman@hws.edu