University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 477/677
Design and Analysis of Algorithms
Spring 2004
Assignments
Revised May 17, 2004
![](../../../../bluhorsa.gif)
-
Tuesday, January 20, 2004
-
I will assume that you are familiar with the material in
Chapter 1 of
your textbook.. You should be, if you've learned
the material in the prerequisite courses.
Yet, I will still spend some time today going over some
of the more difficult topics in that Chapter.
-
Also today, we will discuss efficiency of algorithms. Read
Sections 2.1 through 2.6 of your textbook, pages 57-67,
before class.
-
Thursday, January 22, 2004
-
Today, we will continue our discussion of efficiency of algorithms, with
an emphasis on timing analysis.
-
Tuesday, January 27, 2004
-
Turn in Assignment 1 at the beginning of class today.
-
Today we will discuss several of the topics in Chapter 4, pages 98-146
in your textbook.
-
The most difficult topic we will discuss is amortized
complexity, which is in Section 4.6. I plan to spend most of the
time discussing recurrences, introduced in Section 4.7.
-
Thursday, January 29, 2004
-
Today we will continue the discussion of recurrences.
-
-
Tuesday, February 3, 2004
-
Today we will continue the discussion of recurrences.
-
Thursday, February 5, 2004
-
Turn in Assignment 2 at the beginning of class today.
-
Today we will continue the discussion of recurrences.
I will prove the master theorem today.
-
If time permits, we will discuss amortized analysis.
-
Tuesday, February 10, 2004
-
Today we will discuss sorting and searching.
-
Thursday, February 12, 2004
-
Today we will continue our discussion of sorting algorithms.
-
Tuesday, February 17, 2004
-
Today we will continue our discussion of sorting algorithms.
-
Thursday, February 19, 2004
-
Today we will try to finish our discussion of sorting algorithms.
-
Tuesday, February 24, 2004
-
First Examination today. Read the study guide.
-
Thursday, February 26, 2004
-
Today we will begin the discussion of priority queues and search structures.
-
Tuesday, March 2, 2004
-
I will hand back the exam today.
-
Today we will continue the discussion of priority queues and search structures.
-
Thursday, March 4, 2004
-
We will continue the discussion of priority queues and search structures.
-
Tuesday, March 9, 2004
-
Today I will introduce the rather large subject of graph algorithms, and
data structures which implement graphs. Read Section 5.4 of your textbook.
-
Thursday, March 11, 2004
-
Turn in Assignment 3 at the beginning of class today.
-
Read Chapter 5 (pages 147-186) before March 16, except for Section 5.8.
-
Tuesday, March 16, 2004
-
Today we will continue the discussion of graphs and graph algorithms.
-
Thursday, March 18, 2004
-
Tuesday, March 23, 2004
-
Thursday, March 25, 2004
-
Turn in Assignment 4 at the beginning of class today.
-
We will continue our discussion of minimum path problems, including
finishing the discussion of Floyd's algorithm.
-
Tuesday, March 30, 2004
-
Second Examination today. Read the study guide.
-
The exam will contain graph algorithm questions.
-
If a question that you see on one of these old exams is not related to anything
we've covered in class so far this semester, then don't worry: it will not be
on our March 30 exam.
-
Spring 1999: First Examination
-
Spring 1999: Second Examination
-
Spring 1999: Final Examination
-
Spring 2001: First Examination
-
Spring 2001: Second Examination
-
Spring 2001: Final Examination
-
Fall 2002: First Examination
-
Fall 2002: Second Examination
-
Fall 2002: Final Examination
-
Wednesday, March 31, 2004
-
The exams are graded now. The total possible was 145 points.
-
Thursday, April 1, 2004
-
I will hand back the graded examination today.
-
Tuesday, April 13, 2004
-
Today I will introduce the concept of dynamic programming.
This is a technique whose name (I was told, so I am really not sure)
was chosen for political reasons, and gives no clue as to what the method
really is about. Read Chapter 8 of your textbook.
We have already done some dynamic programming.
The linear time algorithm for finding the sublist of maximum sum that
we did in class at the beginning of the semester uses dynamic programming.
Dijkstra's algorithm is not exactly a form of dynamic programming, but uses
similar concepts.
Many experienced programmers (I am absolutely stunned by the number) claim
to have never heard of dynamic programming. But some of them use it anyway,
as it is really a "natural" method that a clever programmer could come up
with on his own. However, many never do.
It is difficult to overestimate the practical importance of dynamic programming.
The need for it occurs constantly in real-life applications, and those who don't
use it sometimes write programs whose time complexity is greater than necessary,
by a truly staggering amount.
-
Thursday, April 15, 2004
-
I am in my office now, at Thu Apr 15 10:18:46 PDT 2004.
-
Today we will continue the discussion of dynamic programming.
-
Tuesday, April 20, 2004
-
Today we will continue our discussion of dynamic programming.
-
If you want to compute the product of a list of numbers
(such as 3*5*22344*113402*12) does it matter in what order
you do the multiplcation? (Assume that you are using the
multiplication algorithm you learned in elementary school,
whose time complexity for multiplying N by M is O(log(N)log(M)).
-
Thursday, April 22, 2004
-
Turn in Assignment 5 at the beginning of class today.
-
Today, I will discuss backtracking. We will give
Graham's Scan as an example of a backtracking algorithm.
-
If time permits, I will introduce the concept of a greedy
algorithm. Examples of greedy algorithms that we have already done include
Prim's algorithm and Kruskal's algorithm. Another example that we will
introduce will be Huffman's algorithm for
optimal prefix coding.
-
Tuesday, April 27, 2004
-
Just a reminder: I now delete all email messages, without reading them,
unless I know exactly who they are from. So, please use your real name
and be sure to write "CSC 477" or "677" in the subject heading.
-
Today we will cover the subject of NP-completeness and NP-hardness.
(This will be done differently and with less rigor than in 456/656.)
Everybody's heard of the concept, but few can define it. Can you?
I will introduce the concept of parallel algorithms
today if we have time. How much time does it take to find the maximum
of n numbers if n processors are working on the problem simultaneously?
-
Thursday, April 29, 2004
-
Turn in Assignment 6 at the beginning of class today.
-
Tuesday, May 4, 2004
-
Today and Thursday we will introduce some new material and clean up some
previously overlooked topics.
A linear time algorithm for finding the median. (Using this algorithm to
choose the cut value, quicksort runs in Theta(n log n) time. But you'd never
use it that way.)
Dynamic data structures. The simplest example is a linked list with
"move-to-front."
-
We have already discussed balancing schemes for binary search trees
that guarantee that the height is always Theta(log n).
-
A more complex example, but with the same spirit as the move-to-front scheme
for lists, is thesplay tree.
-
Thursday, May 6, 2004
-
Tuesday, May 11, 2004
- Final Examination: 6:00-8:00
challenge problems are absolutely due today.
-
Read the study guide.
-
Monday, May 17, 2004
-
The final grades are now finished.
![](../../../../bluhorsa.gif)