CMSC 641 Design & Analysis of Algorithms, Spring 2008

News Archive

• [Tue May 27 13:03 2008]
  Final exam scores and letter grades has been posted to Blackboard.

  FYI, the average on the final exam was 76.2 (out of 100) and the average total score was 83.09.

• [Thu May 08 16:15 2008]
  Here are 3 java applets for visualizing Fortune's plane sweep algorithm for computing the Voronoi diagram:

  • University of Copenhagen: this applet has the most control for stepping through the simulation, but the points are fixed: [link].

  • University of Waterloo: this applet lets you pick your own points, but you cannot start and stop the simulation. Also, the steps are discrete: [link].

  • By Arnab Bose: this doesn't simulate Fortune's algorithm, but shows you how a point's location affects the Voronoi diagram. You can click to add points and drag existing points around. The Voronoi diagram is updated interactively: [link].

• [Thu May 01 08:35 2008]
  Homework 13 posted.

• [Thu May 01 08:35 2008]
  We will use Dave Mount's (UMCP) lecture notes on Computational Geometry when we discuss Voronoi diagrams: link. The discussion on Voronoi diagrams begins on page 67.

• [Fri Apr 25 12:15 2008]
  Here's the paper for next week's lecture on parallel merge sort in O(log n) time.

  • Richard Cole, "Parallel Merge Sort," SIAM Journal on Computing, 17(4):770–785, 1988.
    DOI="10.1137/0217049" [link]

• [Thu Apr 24 09:45 2008]
  These are the papers describing an O(log n) depth sorting network. The full-text PDF file is available for download if you are logged in through UMBC.

  • M. S. Paterson, "Improved Sorting Networks with O(log n) Depth," Algorithmica, 5:75–92, 1990.
    DOI="10.1145/800061.808726" [link]

  • M. Ajtai, J. Komlós and E. Szemerédi, "An O(log n) Sorting Network," 15th Annual ACM Symposium on the Theory of Computing (STOC), 1–9, 1983.
    DOI="10.1007/BF01840378" [link]

• [Thu Apr 24 09:45 2008]
  Homework 12 posted.

• [Wed Apr 23 11:17 2008]
  Correction: the hint is for Question 2 of Homework 11, not Question 3.

• [Sun Apr 20 14:40 2008]
  Additional hint and explanation provided for Question 3 of Homework 11.

• [Thu Apr 17 00:44 2008]
  Homework 11 posted.

• [Thu Apr 10 09:05 2008]
  Here is a link to the paper "A simple on-line bin-packing algorithm" by C. C. Lee and D. T. Lee from the Journal of the ACM: link. The Big-Medium-Small approximation algorithm for Bin Packing is a simplified version of the algorithm in this paper. You should be able to download the full text of this paper when you are connected thru the UMBC network.

• [Thu Apr 10 09:00 2008]
  Homework 10 posted.

• [Thu Apr 03 00:35 2008]
  Homework 9 posted.

• [Fri Mar 28 20:20 2008]
  Grades have been posted to the Blackboard site. You should be able to see your scores when you log into myUMBC and hop over to Blackboard. (We will only use Blackboard for grades.) Please look over your scores. If there are any discrepancies, please inform the instructor ASAP.

  So far, there have been 6 graded homework assignments (=18 points) and 2 quizzes (=14 points) for a total of 32 points. FYI, the class average is 26.20/32 = 81.9%.

• [Wed Mar 26 16:00 2008]
  Homework 8 posted.

• [Wed Mar 12 17:17 2008]
  Homework 7 posted.

• [Wed Mar 05 23:09 2008]
  Homework 6 posted.

• [Mon Mar 03 11:53 2008]
  Suresh Purini's office hours:
  • Additional office hours Monday, March 3, 5pm-7pm.
  • Office hours on Thursday, March 6th moved to Tuesday, March 11th 3:45 - 4:45.

• [Sun Mar 02 15:35 2008]
  Syllabus updated to reflect slippage in the schedule. The original syllabus is still available here.

• [Thu Feb 28 08:45 2008]
  The second quiz is on Tuesday, March 4. The topic will be dynamic programming.

• [Thu Feb 28 08:40 2008]
  Homework 5 posted.

• [Thu Feb 21 09:25 2008]
  Homework 4 posted.

• [Thu Feb 14 12:17 2008]
  Here are two Java applets that help you play with and visualize Binomial Heaps and Fibonacci Heaps:
  • by David Galles, Computer Science Dept, University of San Francisco: [link]
    (This one has Binomial Heaps and many other data structures.)
  • by someone in the Computer Engineering Dept, Chulalongkorn University, Thailand: [link]
    (This is one of few Java applets on line that does Fibonacci Heaps. The instructions are in Thai.)

• [Thu Feb 14 08:10 2008]
  Homework 3 posted.

• [Sun Feb 10 09:46 2008]
  I posted notes on the amortized analysis of the Disjoint Set data structure: dsu.pdf. I will not in general write up notes from lecture. This one took me about 6 hours. I'm making an exception here because this analysis is much simpler than the one in the textbook.

• [Wed Feb 06 20:30 2008]
  Homework 2 posted.

• [Tue Feb 05 10:36 2008]
  Our TA Suresh Purini's office hours are posted on the contacts page. He will be available in ITE 230 on Wednesdays from 3:30pm to 4:30pm and on Thursdays from 3:45pm to 4:45pm.

• [Fri Feb 01 14:20 2008]
  Fixed a typo in "Note 3" of the first question in Homework 1.

• [Thu Jan 31 11:15 2008]
  Homework 1 posted.

• [Thu Jan 24 22:40 2008]
  The course description and syllabus are available in PDF: description.pdf, syllabus.pdf. Hard copies will be distributed on the first day of class.

• [Thu Jan 24 22:40 2008]
  The first quiz is on Tuesday, February 19. Mark your calendars with the dates of the in-class quizzes from the syllabus!

• [Thu Jan 24 22:37 2008]
  Web page up.