Computer Science 477/677: Design and Analysis of Algorithms

Spring 2001

Assignments

This page will be updated frequently. Most recent update: May 16, 2001.

• Wednesday January 17, 2001.
  Today, we will given an overview of the course, and introduce a few basic concepts.
  Please read Chapter 1 of your textbook, pages 1-19.
  Please read Chapter 2 of your textbook, pages 23-41.
• Monday January 22, 2001.
  Today's lecture will concentrate on the definitions of Big Oh, Big Omega, and Big Theta, and applications to the asymptotic time complexity of an algorithm.
  This lecture should give you all the hints you need to work Assignment 1.
• Wednesday January 24, 2001.
  Homework due.
  Assignment 1 will be due on Wednesday, January 24, in class.
  Having successfully completed courses in calculus and finite mathematics, you should be familiar with all the material in Chapter 3 of your textbook, pages 42-52. I do not plan to lecture on that material, but I will assume that you know it.
  Today's lecture will be an introduction to the calculation of time complexity using recurrences. Although natural for the calculation of the time complexity of recursive algorithms, recurrences are quite helpful in dealing with problems relating to other kinds of algorithms.
• Monday January 29, 2001.
  Today's lecture will be on relations and graphs.
• Wednesday January 31, 2001.
  Today we will continue discussion of some earlier topics.
• Monday February 5, 2001. I have, so far, failed to get a better room.
  Today, we will discuss heaps and heapsort. Read Chapter 7 of your textbook, pages 147-152. Assignment 2 will be due on Monday, February 5, in class.
• Wednesday February 7, 2001. Today, we will discuss quicksort. Read Chapter 8 of your textbook, pages 153-171.
• Monday February 12, 2001.
  Homework due. Assignment 3 will be due on Monday, February 12, in class.
  Examination.
  There will be an examination on Monday, February 12, in class.
• Wednesday February 14, 2001. Today, I will return the graded examination from Monday.
  We will discuss radix sort and bucket sort. Reach Chapter 9 of your textbook, pages 172-184.
  We will begin the discussion on medians and order statistics. Reach Chapter 10 of your textbook, pages 185-199.
  I have officially requested that our room be changed to one of the other classrooms in BHS -- specifically, one that has student desks. I expect this to be done by Monday.
  We will meet in our usual room tonight, and I will announce our new room on this web page as soon as I get word.
• Wednesday February 21, 2001. Homework due. Assignment 4 will be due on Wednesday, February 21, in class.
  Today we will begin Data Structures. Reach Chapter 11 of your textbook, pages 197-218.
  We will discuss lists, stacks, and queues.
• Monday February 26, 2001.
  Today we will continue the discussion of lists, stacks and queues. We will introduce array implementation of linked structures.
  If time permits, we will begin the dicsussion of hashing.
• Wednesday February 28, 2001.
  Today we will introduce binary trees
• Monday March 5, 2001.
  Assignment 5 will be due Monday, March 5, in class.
  Today we will continue our discussion of binary trees.
  If time permits, we will begin to discuss dynamic programming. Please read Chapter 16 of your textbook, pages 299-354.
• Wednesday March 7, 2001.
  Today, we will continue our discussion of dynamic programming.
• Monday March 19, 2001.
  Today, we will continue our discussion of dynamic programming. We will also introduce greedy algorithms.
• Wednesday March 21, 2001.
  Assignment 6 will be due on Wednesday, March 21, in class.
  I must end office hours before 11:00 today, due to a faculty meeting with the Regents' Consultants.
• Monday March 26, 2001.
  There will be an examination on Monday, March 26, in class.
• Wednesday March 28, 2001.
  We will discuss amortized analysis. Reach Chapter 18 of your textbook, pages 356-378.
• Monday April 2, 2001.
  Graduate Assignment 1 will be due on Monday, April 2, in class.
  We will finish the discussion of amortized analysis, if needed.
  
• Wednesday April 4, 2001.
  Assignment 7 will be due on Wednesday, April 4, in class.
  Today we will begin discussion of advanced data structures. Read Section V of your textbook, starting on page 378.
• Monday April 9, 2001.
  I will hand back the graded exam today. The exam grades are now available by email. Be sure to include your student id number in your message, for verification purposes. The median grade on the examination is 53.
  We will review Kruskal's algorithm.
  If time permits, we will begin discussing B-trees, 2-3 trees, and other forms of search trees. Read Chapter 19 of your textbook, pages 381-399.
• Wednesday April 11, 2001.
  Today we will discuss data structures which represent graphs. We will also discuss breadth-first search, depth-first search, and topological sort. Read Chapter 23 of your textbook, pages 465-497.
• Monday April 16, 2001.
  Today we will continue the discussion of graphs, breadth-first search, depth-first search, and topological sort.
  We will also discuss minimum spanning trees. Read Chapter 24 of your textbook, pages 498-513.
• Wednesday April 18, 2001.
  Assignment 8 will be due on Wednesday, April 18, in class.
  Today we will discuss the shortest path problem. Read Chapters 25 and 26 of your textbook, pages 514-578.
• Monday April 23, 2001.
  Today we will continue the discussion of the shortest path problem. Read Chapters 25 and 26 of your textbook, pages 514-578.
  In particular, we will present Dijkstra's Algorithm, which is in Section 25.2 of your textbook, pages 527-532.
  We finally have a suitable classroom. It is BHS 212, just down the hall.
• Wednesday April 25, 2001.
  Today we will discuss Dijkstra's Algorithm and Floyd's Algorithm for the shortest path problem.
• Monday April 30, 2001.
  Today we will introduce the Bellman-Ford Algorithm and Johnson's Algorithm.
• Wednesday May 2, 2001.
  Today we will review some topics, rather than introduce new material.
  The final examination for Spring 1999 is now available.
• Monday May 7, 2001.
  Final Examination at 6:00 PM. Two hours.
• Final Grades are now ready.
  You may email a request for your grade. Be sure to write "CSC477" or "CSC677" in the subject field. For identification purposes, please include your student ID number in the message.