Computer Science 477/677
Design and Analysis of Algorithms
Fall 2005
Assignments

Revised December 8, 2005

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 k^thsmallest 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.