CSC 477/677 Assignments Spring 1999

Computer Science 477/677: Design and Analysis of Algorithms

Spring 1999

Assignments

This page will be updated frequently. Most recent update: April 28, 1999.

January 20, 1999. The topics of today's lecture will be algorithms (Chapter 1 of your textbook, pages 1-19) and growth of functions and asymptotic notation (Chapter 2 of your textbook, pages 21-41).
Homework due. Assignment 1 will be due on Wednesday, January 27, in class.
You will be responsible for knowing the material in Chapter 3 of your textbook, although we will not cover that material in class.
January 25, 1999. The topic of today's lecture will be recurrences (Chapter 4 of your textbook, pages 53-76).
No textbooks. If the textbooks are not available in the bookstore by Monday January 25, the due date of the homework will be extended to Monday, February 1.
No homework extension. The textbooks were available in the bookstore by Monday January 25, and thus the due date of Assignment 1 has not been extended.
January 27, 1999. The topics of today's lecture will be Recurrences (Chapter 4 of your textbook, pages 53-76) and Sorting, starting with Heapsort (Introduction to part II, and Chapter 7 of your textbook, pages 125-152).
Homework due. Assignment 2 will be due on Wednesday, February 3, in class.
February 1, 1999. The topic of today's lecture will be sorting algorithms. We shall begin with Selection sort, Insertion sort, and Mergesort, which are discussed in Chapter 1 (pages 1-18 of your textbook). Since I presume that you are already familiar with these three sorting algorithms, and also with Bubblesort, we will discuss them very quickly.
We shall then move on to Heaps and Heapsort (Introduction to part II, and Chapter 7 of your textbook, pages 125-152). If time permits, we shall begin the discussion of Quicksort (Chapter 8 of your textbook).
February 3, 1999. The topic of today's lecture will continue to be sorting algorithms. We shall carefully examine the details of Quicksort (Chapter 8 of your textbook, pages 153-171). We shall also discuss priority queues (Section 7.5 of your textbook, pages 149-152) in more detail.
Homework due. Assignment 3 will be due on Wednesday, February 10, in class.
February 8, 1999. Today we will conclude the discussion of Quicksort (Chapter 8 of your textbook, pages 153-171). We will then discuss medians and order statistics (Chapter 10 of your textbook, pages 184-196).
February 10, 1999. Today we will discuss stacks and queues. Read Chapter 11 of your textbook, pages 200-218.
Holiday. There is no class on February 15. The holiday is officially called Presidents' Day in honor of the first President of the United States of America, George Washington, born in February, 1732, and the sixteenth President, Abraham Lincoln, born February 12, 1809.
Trivia Quiz. What was the calendar date on the day that George Washington was born? (Warning: this is a trick question.) Answer.
Examination. We will have a short exam on February 17.
February 17, 1999. If there is time after the examination, we will continue our discussion of elementary data structures. Finish Chapter 11 of your textbook, pages 200-218.
February 22, 1999. In today's lecture, we will continue our discussion of elementary data structures. Finish Chapter 11 of your textbook, pages 200-218.
Homework due. Assignment 4 will be due on Wednesday, February 24, in class.
February 24, 1999. In today's lecture, we will begin the discussion of hashing. Read Chapter 12, pages 219-243 of your textbook.
March 1, 1999. In today's lecture, we will continue the discussion of hashing.
March 3, 1999. In today's lecture, we will continue the discussion of hashing.
Homework due. Assignment 5 will be due on Monday, March 8, in class.
March 10, 1999. In today's lecture, we will continue the discussion of hashing.
March 12, 1999. In today's lecture, we will continue the discussion of hashing.
March 15, 1999. In today's lecture, we will begin the topic of dynamic programming. This is a large and important topic. Dynamic programming is discussed in Chapter 16 of your textbook, pages 301-328. Please also read the introduction to Part IV of your textbook starting on page 299.
March 17, 1999. In today's lecture, we will continue the discussion of dynamic programming. Please finish reading Chapter 16 of your textbook, pages 301-328.
March 22, 1999. In today's lecture, we will continue the discussion of dynamic programming. Please finish reading Chapter 16 of your textbook, pages 301-328.
March 24, 1999. In today's lecture, we will continue the discussion of dynamic programming. Please finish reading Chapter 16 of your textbook, pages 301-328. We shall also dicuss greedy algorithms. Please read Chapter 17 of your textbook, pages 329-354.
Homework due. Assignment 6 will be due on Monday, April 5, in class.
Examination. We will have an exam on April 7. The examination will cover all material discussed in class up until that point, including Chapters 16 and 17 of your textbook. Answer to Scrabble Problem on Test
Homework due. Special Assignment will be due on Monday, April 19, in class.
April 19, 1999. In today's lecture, we will discuss graph algorithms. Read Chapters 23, 24, 25, and 26 of your textbook, pages 463-557.
April 21, 1999. In today's lecture, we will continue the discussion of graph algorithms. Continue reading Chapters 23, 24, 25, and 26 of your textbook, pages 463-569.
Homework due. Assignment 7 will be due on Monday, April 26, in class.
Homework due. Assignment 8 will be due on Monday, May 3, in class.
April 26, 1999. In today's lecture, we will discuss shortest path problems. Read Chapters 25 and 26, pages 514-569.
April 28, 1999. In today's lecture, we will continue the discussion of shortest path problems. Read Chapters 25 and 26, pages 514-569.
May 3, 1999. Today's lecture will be given by Dr. Laxmi Gewali. He will discuss computational geometry. Read Chapter 35.
May 5, 1999. In today's lecture, we will discuss more graph algorithms. We will also define the concept of NP-complete.
Final Examination. Our final examination is scheduled for 6:00 PM on Monday, May 10. The examination will be comprehensive.

Back to Course Page