CPSC 327 Syllabus

Week 1: 1/19-1/23

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.

Week 2: 1/26-1/30

Topics: applying algorithm analysis, motivating applications (sorting and lookup)

• 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?

Notes:

• big-Theta from algorithms

Week 3: 2/2-2/6

Topics: iterative algorithms

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.

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 big-Theta for your S(n)?

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:

• notes on loop invariants, monster problem discussion, fractional knapsack discussion

Week 4: 2/9-2/13

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

• notes on loop invariants, proving correctness, and running time

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:

• notes on array searching problem and solving recurrence relations

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:

• unwinding example

Week 5: 2/16-2/20

Topics: divide-and-conquer algorithms

Notes:

• ugly sums, T(n) = T(an)+T(bn)+n, steps for developing recursive algorithms

Notes:

• coming up with algorithms, solution to Monday's thinking problem

Week 6: 2/23-2/27

Topics: divide-and-conquer algorithms; ADTs and data structures

• strategies for coming up with algorithms, inversions and stock prices examples

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)

• ADTs and data structures (updated 3/2)

Week 7: 3/2-3/6

Topics: trees

Notes:

• union find

Week 8: 3/9-3/12

Topics: trees

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

• skyline problem, places to try to make your algorithm faster, some heaps

Notes:

• heaps

Notes:

• AVL trees and 2-4 trees

Spring Break

Week 9: 3/23-3/27

Topics: graphs and graph algorithms

Thinking Problems:

• exercise 14.1.1 (page 178)
• exercise 14.3.3 #4, #5 only (page 188)

Notes:

• Graph ADT and implementation

• reachability (bfs, dfs)

Week 10: 3/30-4/3

Topics: graph algorithms; greedy algorithms

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

• reachability-inspired algorithms wrapup, greedy algorithms, Dijkstra's algorithm as a greedy algorithm

Notes:

• minimum spanning tree, maximal independent set (greedy algorithms)

Week 11: 4/6-4/10

Topics: greedy algorithms; recursive backtracking and branch-and-bound

• making change (example of "staying ahead" loop invariant and proof)

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

Notes:

• event scheduling (greedy), introduction to recursive backtracking

• recursive backtracking, pruning

Week 12: 4/13-4/17

Topics: branch-and-bound; dynamic programming

• notes on project 2, branch and bound

Thinking Problems:

1. Does a dynamic programming algorithm have to be iterative? Can you write it recursively instead without changing the big-Oh?

2. Where does the polynomial running time come from?

• branch and bound wrapup, dynamic programming

Notes:

• comments on greedy and branch-and-bound (from homework), with a tiny bit of dynamic programming

Week 13: 4/20-4/24

Topics: dynamic programming; reductions

Notes:

• 0-1 knapsack (dynamic programming)

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:

• notes on hw 22, longest common subsequence, weighted interval scheduling (greedy algorithms and dynamic programming)

• matrix multiplication, dynamic programming wrapup

Week 14: 4/27-5/1

Topics: NP-completeness

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

Notes:

• reductions

• complexity and NP-completeness

Week 15: 5/4-5/5

Topics: nifty data structures (splay trees and skip lists)

• skip lists, splay trees

Reading Period & Exams: 5/6-5/12

last updated: --Mon May 4 21:24:36 EDT 2009--
page owned by: bridgeman@hws.edu