Computer Science 477/677
Analysis of Algorithms
Spring 2019
Assignments and Lecture Topics

Revised May 13, 2019

Wednesday, January 23, 2019

We will begin by discussing asymptotic complexity.

Monday, January 28, 2019

38 students turned in the not-for-credit quiz. Of those:

1. 28 answered the high school algebra problem correctly.
2. 15 answered the calculus problem correctly.
3. 34 answered the CS302 problem correctly.

Turn in Assignment 1 at the beginning of class today.

Monday, Februay 4, 2019

Turn in Assignment 2 at the beginning of class today.

Wednesday, February 13, 2019

Examination.

Practice Exam

Distribution:
  113 25 %-ile
  125 50 %-ile (median)
  129 mean
  145 75 %-ile
  188 highest
  200 possible

Monday, February 25, 2019

I was almost right about the potential. The correct formula is
Φ =
  hi − lo − 1   if X[lo + 1] < pivot and X[hi] > pivot
  hi − lo         otherwise.

Thursday, February 28, 2019

Assignment 3 is now ready.

Monday, March 4, 2019

Read about Double Rotation in AVL trees.

Problems on loop invariants

Answers to problems on loop invariants

Wednesday, March 6, 2019

Turn in Assignment 3 at the beginning of class today.

Answers to Assignment 3

Wednesday, March 13, 2019

Examination.

Practice Exam

Some of the answers to the practice exam
Error in answer file corrected Tue Mar 12 14:53:41 PDT 2019

Distribution:
  180 25 %-ile
  204 50 %-ile (median)
  200 mean
  220 75 %-ile
  highest 255
  possible 260

Monday, March 25, 2019

Dynamic Programming.

1. Identify subproblems.
2. Solve the subproblems in topological order.
3. The simplest dynamic programming problem: the shortest path problem in a weighted acyclic digraph
4. Rod cutting problem
5. Some other dynamic programming practice problems:
6. A tutorial on dynamic programming
   

Memoizing.

1. Identify subproblems.
2. Solve subproblems in top-down order using recursion, storing each solution as a memo in a search structure.
3. You don't solve all subproblems; only those that are used for the final solution. Your recursive function determines which ones are needed.

Monday, April 1, 2019

Turn in Assignment 4 at the beginning of class today.
Revised March 27, 2019
Read This!

Wednesday, April 10, 2019

A* algorithm

A longer discussion

Wednesday, April 17, 2019

Examination.

Practice Exam

Distribution:
  135 25 %-ile
  153 50 %-ile (median)
  152 mean
  172 75 %-ile
  210 highest
  210 possible
One person did not put his/her name on his/her paper.

The Collatz problem.

Practice Exam

Monday, April 22, 2019

Longest Common Subsequence

Iterated logarithm

Inverse Ackermann function

Computing the convex hull of a set of points in the plane: Graham scan

Wednesday, April 23, 2019

Various reductions to prove NP-completeness

Wednesday, May 1, 2019

Turn in Assignment 5 at the beginning of class today.

Tuesday, May 14, 2019

I will be in my office most of the morning. I might have to take time to meet a faculty candidate.

Wednesday, May 15, 2019

Final Examination. 8:00 to 10:00.

Practice Exam

Answers to Practice Exam .
The most important correction is for Problem 6. If you find any more mistakes, please email me immediately.

Distribution:
  229 25 %-ile
  250 50 %-ile (median)
  254 mean
  279 75 %-ile
  335 highest
  350 possible