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
Fall 2005
Assignments
Revised December 8, 2005
![](../../../../bluhorsa.gif)
-
Tuesday August 30, 2005.
-
Today we will discuss the time complexity and
space complexity of an algorithm, and more specifically,
of a computer program. We will define the "big-Oh", "Omega", and "Theta"
notations.
-
Complexity was largely ignored by mathematicians until fairly recently
(about 40 years ago). If a problem could be solved using an algorithm, most
mathematicians didn't think much about whether, or how, it could be solved in
a reasonable amount of computation time. (The
problem of determining whether a number is prime was an exception.)
But as people started to use computers to solve problems, the issue became
prominent.
-
I will introduce a simple problem (or two) and show several correct algorithms
for solving the problem, some far faster than others.
-
Answer these questions in class.
-
Goals of this lecture.
-
Thursday September 1, 2005.
-
Today
-
Goals of this lecture.
-
Tuesday September 6, 2005.
-
Assignment 1 is due today in class.
-
Today we will catch up on some unfinished material from the previous two
Goals, including a proof of the
Master Theorem. See also
additional notes on the Master Theorem and
the NIST page on the Master Theorem.
-
Here are some practice recurrence problems..
-
Thursday September 8, 2005.
-
Today we will spend most of the time going over problems which use the
Master Theorem, and, in general, techniques for analyzing complexity of
algorithms.
-
-
Tuesday September 13, 2005.
-
Today we will discuss data structures, including arrays, linked lists,
stacks, queues, and heaps.
-
If time permits, we will begin the dicussion of divide and
conquer algorithms, such as binary search, mergesort, and quicksort.
-
Goals of this lecture.
-
Thursday September 15, 2005.
-
We will continue the discussion of elementary data structures and their
applications, and divide and conquer algorithms.
-
Goals of this lecture.
-
Assignment 2 is due today in class.
-
Tuesday September 20, 2005.
-
I will spend today's lecture discussing material that will be on the
examination on Thursday. This will include material that is in
Study Problems.
-
Thursday September 22, 2005.
-
Study Problems should be finished by today.
-
Examination today. The exam will cover all material up until this point
in the course.
-
Tuesday September 27, 2005.
-
I will hand back the graded exams today, and we will go over it.
-
Starting today, we will "back and fill" on a number of topics. These will
include:
-
Loop invariants
and implementation of quicksort.
-
Randomized time complexity of quicksort.
-
Simple quadratic-time sorting algorithms, including
-
simple selection sort
-
simple insertion sort
-
bubblesort
-
Search structures, including:
-
ordered lists and binary search
-
unordered lists and linear search
-
binary search trees, and binary tree insertion sort
-
Heaps and heapsort.
Heapsort could be called "Binary tree selection sort."
-
Heaps, stacks, and queues are examples of priority queues.
Any item can be inserted into a priority queue, but, at any given time,
there is at most one item in the structure that can be deleted.
-
Polyphase mergesort.
-
Radix sort, also known as bucket sort.
-
Shell sort.
Primarily of historical interest now, at one time it was the best
in situ sorting algorithm
commonly available. You might think that it works by dividing the data into
"shells," or something like that, but the name is the name of the
inventor of the algorithm,
Donald Shell.
-
-
-
-
Thursday September 29, 2005.
-
Today we will continue the "back-and-fill" material.
Selection sort, insertion sort, bubblesort, Shell sort, binary search.
-
Tuesday October 4, 2005.
-
Today we will continue the "back-and-fill" material.
Heaps, binary search trees.
-
Thursday October 6, 2005.
Today we will continue the "back-and-fill" material.
-
The
Kepler Conjecture, which dates back to Johannes Kepler (1571-1630),
was finally proved in 1998 by Thomas Hales, but parts of the proof
consist of computer programs which have not been verified.
-
Tuesday October 11, 2005.
-
We will continue the "back-and-fill" material.
-
Programming Problems
-
Thursday October 13, 2005.
-
Today, we will finish the discussion of lower bounds of computation using
information theory, such as in the coin weighing problem. We will then
prove the well-known Omega(n log n) lower bound for sorting.
-
We will go over heapsort, which is a fast form of selection sort,
and binary tree sort, which is a fast form of insertion sort.
-
If time permits, we'll finish up sorting with a discussion of radix sort.
Radix sort does not use the decision tree model of computation, and
so the Omega(n log n) lower bound for sorting does not apply.
-
Tuesday October 18, 2005.
-
Assignment 3 is due today in class.
-
I promised to explain how to store a binary tree in an external file.
Here is one way to do it.
-
Today we will finish up sorting, by explaining binary tree sort and
polyphase mergesort.
-
If time permits, we will discuss the
the philosophy behind some stack algorithms.
-
Programming Problems
-
Thursday October 20, 2005.
-
I will introduce a
linear time algorithm for finding the median of a list of values.
(Actually, the algorithm finds the kthsmallest
element in the set, and the median is simply the element where k = n/2.)
Although it takes O(n) time, this is not very efficient, since the
constant is high. We can improve the expected performance greatly by
using randomization. The worst-case performance then becomes quadratic,
but the probability that the worst-case happens is insignificant for large
lists.
-
This leads directly into our discussion of
search structures, since one way to
make certain search structures efficient is to use randomization.
-
Tuesday October 25, 2005.
-
Today we will discuss the problem of balancing a
binary search tree. One kind of balanced binary search tree is the
AVL tree, which uses
rotations if the tree becomes too lopsided.
A treap (treap = tree+heap)
is a structure that is simultaneously a binary search tree and a heap,
where the heap property for a randomly assigned priority is maintained
by rotations, the same kind or rotations used for AVL trees, as it turns
out. The treap is balanced with a "very high" probability, although
we really need to explain what that means.
-
In this file, we see
an ordinary binary search tree. There are two runs here. In the first,
the input file is a mixed-up list of names. The binary search tree comes
out reasonably balanced. In the second, the input file is a sorted
list of the same names. The binary search tree is terribly unbalanced.
To see the binary tree correctly, turn your head 90 degrees to the left.
The root is in the left margin.
In this file, we see
the same data introduced into a treap. There are also two runs here, using
the same data as before.
-
Answer this question before class: What is the
relation between binary tree sort and quicksort?
We could define treapsort as follows. First, enter
the items one at a time into a treap. Next, write them out in inorder.
Answer this question before class: What is the
relation between treapsort and randomized quicksort?
-
A B-tree stores
all the data in the leaves, which are all at the same height.
It uses a technique called node splitting to maintain balance.
-
Thursday October 27, 2005.
-
Today we will do some catching up, but also introduce the matrix
representation of graphs.
-
Tuesday November 1, 2005.
-
Today we will continue our discussion of the various kinds of graphs.
Terms we will learn include:
-
graph (or "undirected graph")
-
directed graph
-
weighted graph, or weighted directed graph
-
path
-
directed path
-
cycle
-
acyclic graph
-
connected
-
strongly connected
-
component
-
strong component
-
source
-
sink
-
depth first search
-
breadth first search
-
matrix implementations
-
"or and" matrix multiplication
-
"min +" matrix multiplication
-
degree, indegree, outdegree
-
neighborlist implementations
-
sparse
-
other implementations
-
planar graph
-
Euler's formula for planar graphs
-
complete graph
-
shortest path
-
spanning tree
-
Thursday November 3, 2005.
-
Assignment 4 is due today in class.
-
Tuesday November 8, 2005.
-
Examination today.
Study guide.
-
Thursday November 10, 2005.
Graphs.
-
Tuesday November 15, 2005.
-
Today, I will cover
Kruskal's algorithm for minimum spanning trees,
and
Dijkstra's algorithm for the single source minimum path problem in
a non-negative weighted directed graph.
-
Prim's algorithm,
which I have not presented in class, is another
greedy algorithm
for the minimum spanning tree problem.
-
Thursday November 17, 2005.
-
Today I will cover
Huffman's Algorithm for
optimal prefix codes.
-
I will also cover
Graham's Scan, an algorithm for finding the
convex hull of a set of points in a plane.
Print out a copy of
this figure and bring it with you to class today.
It is much more difficult to find all strong components of a directed graph.
I will show you how to do this
using depth-first search.
-
Tuesday November 22, 2005.
- Assignment 5 is due today in class.
-
I will present the
Union-Find problem, and give some applications.
One application is in the implementation of
Kruskal's algorithm.
-
If time permits, I will show you how to find all components of a graph
by depth first search, or breadth first search. (This is easy.)
-
If time permits, I will discuss
stack algorithms
for several problems, and try to give a general philosophy for designing
stack algorithms.
-
Two new
challenge problems for top students
have been added. All challenge problems are due at the time of the final
examination.
- Thursday November 24, 2005.
-
Thanksgiving Day holiday.
-
Tuesday November 29, 2005.
- Assignment 6 is due today in class.
-
we will go over some topics we didn't quite finish, including
some more stack algorithms, Union-Find, and
how
recursion is implemented by the use of a runtime stack.
-
If time permits, we will begin the discussion on
sparse arrays and their implementation.
-
Thursday December 1, 2005.
-
Today we will discuss several implementations of the abstract data
type "Array."
-
An implementation of ragged arrays
which I am currently using in my research.
-
Tuesday December 6, 2005.
-
-
Today we will continue our discussion of implementations of the abstract
data type Array.
-
We also discuss
hashing.
Thursday December 8, 2005.
-
Due to ISPAAN 2005, which is held in Las Vegas this week, I will have
truncated office hours today.
-
Thursday, December 15.
Final Examination.
-
Our final examination is scheduled for 10:10 AM.
The examination will be comprehensive.
-
All finals are held in the same classrooms as the lectures, unless otherwise
announced.
Study guide.
![](../../../../bluhorsa.gif)
ps
pdf