Computer Science 477/677: Design and Analysis of Algorithms
Fall 2002
Assignments
This page will be updated frequently.
Most recent update: December 15, 2002.
-
Background.
I expect you to be somewhat familiar with the material in Sections
1.4, 1.5, 1.6, and 1.7 of your textbook (pages 7-56). Some of that
at material is very important for the course, and will appear in tests,
but I do not plan to lecture on it. Please scan those sections before
the end of the first week. I will then go over the topics in class,
indicating which you need to review in depth.
-
Tuesday, August 27, 2002.
Today we will cover Sections 1.1, 1.2, 1.3, all of Chapter 2, and
Sections 3.1, 3.2, and 3.3 of your textbook.
This may seem like a lot of material for the first day, but, since
almost all of that material is in CSC 269, this is mostly just a review.
-
Thursday, August 29, 2002.
Assignment 1 is due today.
We will discuss the use of recurrences to analyze the asymptotic
performance of an algorithm. (Chapter 4 of your textbook.)
-
Tuesday, September 3, 2002.
We will continue the discussion of recurrences.
-
Thursday, September 5, 2002.
Assignment 2 is due today.
Some practice questions on recurrences.
-
Tuesday, September 10, 2002.
Today we will discuss virtually initialized arrays.
(See the diagram on page 150 of your textbook.)
We will also review some of the past homework assignments.
If there is enough time, we will introduce graphs, trees, and heaps.
(Sections 5.4, 5.5 and 5.7 of your textbook.)
-
Thursday, September 12, 2002.
Assignment 3 is due today.
We will continue the discussion of graphs, trees, and heaps.
-
Tuesday, September 17, 2002.
We will continue the discussion of graphs and trees.
We will also introduce directed graphs.
-
Thursday, September 19, 2002.
Today we will discuss matrix representation of graphs and weighted
graphs, and use
min,+ matrix multiplication to find minimum cost paths.
-
Tuesday, September 24, 2002.
Today we will discuss hashing and hash tables.
We will also summarize the material
that might be on the examination tomorrow.
-
Thursday, September 26, 2002.
Examination today.
-
Tuesday, October 1, 2002.
Today I plan to hand back the exam and go over it.
If time permits, we will discuss the minimum spanning tree problem
(Section 6.3 of your textbook, pages 190-197.)
-
Thursday, October 3, 2002.
Today we will discuss a general
algorithmic technique called divide and conquer.
Among the well-known algorithms of this type, we have
binary search,
mergesort,
quicksort,
linear time finding of the median.
-
Tuesday, October 8, 2002.
Today we will complete the discussion of the linear time algorithm for
finding the median, and really do quicksort. We will also discuss a
fast form of multiplication.
-
Thursday, October 10, 2002.
Assignment 4 is due today.
Today we will instroduce dynamic programming.
-
Tuesday, October 15, 2002.
Today, we will discuss a pseudo-polynomial-time algorithm for
the knapsack problem, as well as dynamic programming algorithms for
shortest paths.
-
Thursday, October 17, 2002.
Assignment 5 is due today.
We will discuss chained matrix multiplication (Section 8.7 of your textbook)
and memoizing (Section 8.8 of your textbook).
Note: that is not a mispelling. I didn't say "memorizing."
We will also talk about quicksort, once again, using the split
procedure of quicksort
as an example to illustrate the usefulness of loop invariants.
-
Tuesday, October 22, 2002.
Today we will discuss the recursive exponentiation algorithm introduced
on page 245 of your textbook.
We will discuss cryptography, and how the recursive exponentiation algorithm
is used for RSA coding, a cryptography scheme for one-way
coding which is widely used today, despite the fact that no one has proved
it secure.
-
Thursday, October 24, 2002.
I will be somewhat late for my office hour today.
-
Tuesday, October 29, 2002.
Today we will discuss pattern-matching algorithms and finding subsequences
by dynamic programming.
We will also (finally) give the answer to that hard problem in fast
multiplication that nobody was able to solve.
We will then spend some time discussing topics that will be on the upcoming
examination Thursday.
-
Thursday, October 31, 2002.
Office hour is at a different time today.
Examination today.
A partial summary of the material
that might be on the examination.
-
Tuesday, November 5, 2002.
Office hour is at a different time today.
Today I will introduce the concept of a polynomial time algorithm
and a tractable problem
There is a polynomial
time algorithm which determines whether a number is prime.
-
Thursday, November 7, 2002.
Office hour is at a different time today.
I will hand back the test today.
-
Tuesday, November 12, 2002.
-
Thursday, November 14, 2002.
Office hour will be canceled today.
I will, be in class tonight, though.
-
Tuesday, November 19, 2002.
Office hour is at a different time today.
Today we will start discussiong balanced search structures,
which include AVL trees, B-trees, 2-3 trees, red-black trees,
and splay trees.
-
Thursday, November 21, 2002.
Cartoons referring to NP-completeness.
Assignment 6
is due today.
Today we will discuss probabilistic algorithms
(Chapter 10 of your textbook). These are also known as
randomized algorithms.
-
Tuesday, November 26, 2002.
Today I will touch briefly on a subject that will become far more important
in the future -- parallel algorithms.
The speed of light constrains the speed of any computer, as no signal of any
kind can move faster than light. In one nanosecond, light moves 30
centimeters. Since computer components are usually closer than that, signals
can theoretically get from one part of the computer to another in a nanosecond.
But recent news stories have talked about machines whose speeds are in the
"teraflop" range. That means, one calculation ever picosecond, i.e., every
trillionth of a second. In that amount of time, light moves only 0.3
millimeters. Can a super-computer be crammed into a space that size?
One solution is to use multiprocessing. That means, a machine could consist
of a large number of parallel processors, all working together to solve one
problem. But what algorithm should be used for each problem?
Can you find the minimum element of an array of size n in less than linear
time if you have lots of processors? How about the sum?
(For an answer, go to class today.)
Does it take Omega(n) time to add two n-bit numbers if you have lots of
processors? It would seem so, but it doesn't.
-
Thursday, November 28, 2002.
Thanksgiving Recess.
-
Tuesday, December 3, 2002.
Today we will discuss the contents of the final examination.
-
Thursday, December 5, 2002.
Do Assignment 7 by today.
-
Thursday, December 12, 2002.
Office hour today, 9:30 to 11:00.
Final Examination, 6:00 PM.
I will try to summarize the material
that might be on the final exam.
-
Monday, December 16, 2002.
Final course grades are now available.
![](../../bluhorsa.gif)
Back to
Course Page