Computer Science and Engineering 101
Design and Analysis of Algorithms
Summer 2003
Assignments

Revised August 4, 2003

Monday, June 30, 2003

Lecture topic: Overview.
Time analysis, big O, Omega, Theta.

Tuesday, July 1, 2003

Lecture topic: big O, Omega, Theta. Solving recurrences.

Timing analysis.

The combinatorial explosion.

In every usage of stacks that I have ever seen in programming, the stack holds unfulfilled obligations..

Today I will introduce the master theorem for solving recurrences. The master theorem does not permit you to solve all recurrences, but it does help for many that arise in practice.

Discussion Session 3:00-4:00, CNTR 113

Wednesday, July 2, 2003

Today I will given an informal proof of the master theorem for recurrences.

I will also give the algorithm to translate an infix expression into a postfix expression.

Thursday, July 3, 2003

Lecture subject: basic algorithmic techniques.

Lecture topic: Using data structures to improve the efficiency of algorithms.

There was a last little bit of the proof of the master theorem leftover from yesterday. I finished it up on the board after class, with some help from three of the students. (You have to manipulate logarithms.)

Today I will explain how to use a queue to visit a directed graph in breadth-first order.

Today I will explain how to use a binary search tree to speed up insertion sort.

Homework 1 is due today.

Discussion Session 2:00 - 3:00, CNTR 113

Monday, July 7, 2003

Lecture subject: basic algorithmic techniques.

O(n²)-time simple sorting algorithms: bubblesort, array insertion sort, and array selection sort.

Divide and conquer sorting algorithms: mergesort and quicksort.

Lower bounds on sorting time.

Tuesday, July 8, 2003

Lecture subject: basic algorithmic techniques.

Radix sort / Bucket sort, Shell's sort, and polyphase mergesort.

Can your computer add n-bit integers in o(n) time? A divide-and-conquer algorithm for very fast addition that is wired into some computers.

Master theorem review. Some practice recurrence problems. Answers.

Discussion Session 3:00-4:00, CNTR 113

Wednesday, July 9, 2003

Midterm Examination

Study Guide.

Thursday, July 10, 2003

Lecture subject: basic algorithmic techniques.

I will hand back the examination, but not discuss it.

Heaps and heapsort.

Using a heap to find minimum paths in a weighted directed graph. (Dijkstra's algorithm.)

Discussion Session 2:00 - 3:00, CNTR 113. The examination will be discussed.

Monday, July 14, 2003

Homework 2 is due today.

Lecture subject: basic algorithmic techniques.

Fast addition using parallel processors.

Fast powers, with applications to RSA coding.

Lecture topic: Backtracking. /dd>

The 8 queens problem.

Lecture topic: Dynamic Programming.

Tuesday, July 15, 2003

Lecture subject: basic algorithmic techniques.

Lecture topic: Dynamic programming, dynamic programming and memoization, and parallel dynamic programming.

Discussion Session 3:00-4:00, CNTR 113

Wednesday, July 16, 2003

Lecture subject: basic algorithmic techniques.

Lecture topic: Dynamic Programming.

Bellman's algorithms.

Thursday, July 17, 2003

Lecture subject: basic algorithmic techniques.

Lecture topic: Dynamic Programming.

Edit distance.

Lecture topic: Bounding the Search Space.

Matrix searching. Read about Gaspard Monge.

Homework 3 is due today.

Discussion Session 2:00 - 3:00, CNTR 113

Monday, July 21, 2003

Lecture subject: basic algorithmic techniques.

Lecture topics: backtracking, dynamic programming.

Graham's scan, a backtracking algorithm for the convex hull of a set of points in the plane.

Challenge for the top students: Work these problems

before the end of the term.

Tuesday, July 22, 2003

Lecture subject: basic algorithmic techniques.

Lecture topic: greedy algorithms.

Kruskal's algorithm for minimal spanning trees, a greedy algorithm which uses the union/find ADT.

Prim's algorithm for minimal spanning trees.

Another algorithm for minimal spanning trees.

The coin collector's problem.

Huffman's algorithm for optimal prefix codes.

Hu and Tucker's algorithm for optimal alphabetic trees, a greedy algorithm which uses mergeable heaps.

Discussion Session 3:00-4:00, CNTR 113

Wednesday, July 23, 2003

Midterm Examination.

Study Guide.

Thursday, July 24, 2003

I will give the correct version of Prim's algorithm today. (We will have three greedy algorithms for the minimum spanning tree problem: Kruskal's, Prim's, and the one I presented Tuesday, where you delete the maximum weight edge that does not disconnect the subgraph.)

Knuth's dynamic programming algorithm, making use of a Monge property to speed up the search for an optimal binary search trees from O(n³)-time to O(n²)-time.

I will be in email contact Friday and Saturday from Las Vegas.

Discussion Session 2:00 - 3:00, CNTR 113

Monday, July 28, 2003

Today we will revisit recurrences, and show how to work many problems which do not yield immediately to the master theorem.

We will also introduce a number of definitions involving graphs, and discuss some graph algorithms that we have not yet covered.

Homework 4 is due today.

Tuesday, July 29, 2003

Today we will discuss hashing. (Section 7.3 of your textbook.)

Discussion Session 3:00-4:00, CNTR 113

Wednesday, July 30, 2003

Final Examination, Part 1. Note Change!

Study Guide.

Thursday, July 31, 2003

Final Examination, Part 2.

Friday, August 1, 2003

I can now email grades. Please include your student ID in your email request.

Eventually, grades will be available at Student Link. Click on Academic History.