UMBC CMSC641, Design & Analysis of Algorithms, Fall 2020

News Archive

• [Mon Dec 14 14:25 2020]   Makeup Quiz E&F will be held tomorrow Tuesday December 15, 3:30pm - 5:30pm. That's 30 minutes earlier than the usual class meeting time.
  • Makeup Quiz E: Tuesday December 15, 3:30pm - 4:27pm
    Topics: 1, 2, 3, 6
    
  • Makeup Quiz F: Tuesday December 15, 4:33pm - 5:30pm
    Topics: 2, 3, 4, 5
  Notice that not all topics are offered for both quizzes. If you requested Topic 6 (Approximation Algorithms), you must be present for Quiz E. If you requested Topic 5 (NP-completeness), you must be present for Quiz F.

  Students who signed up for two quizzes will receive one quiz at a time. For example, if you requested Topics 3 & 5, you will receive Topic 3 for Quiz E and Topic 5 for Quiz F. You must finish Topic 3 in the time allotted for Quiz E. (You have to show your responses to the camera by 4:30, but you may scan in both quizzes after Quiz F is over.)

  The astute observer will also note that it is not possible to take both Topic 1 and 6. That's OK because no one requested that combination.

  We will use the same Google Meet link that we have been using for classes.

• [Wed Dec 02 15:20 2020]   Prof. Chang's office hours on Monday December 7th has moved to 12noon.

• [Tue Dec 01 00:45 2020]   Exercise 20 (Chernoff Bounds) due Monday December 7 11:59pm. [Submit]

• [Mon Nov 30 22:45 2020]   Homework 12 posted. Due Tue 12/08/20 11:59pm.

• [Tue Nov 24 10:00 2020]   Updated schedule for the remainder of the semester.

• [Mon Nov 23 15:40 2020]   Exercise 19 (randomized shopping) due Monday November 30 11:59pm. [Submit]

• [Mon Nov 16 10:05 2020]   Homework 11 posted. Due Tue 11/24/20 11:59pm.

• [Mon Nov 09 17:35 2020]   Homework 10 posted. Due Tue 11/17/20 11:59pm

• [Mon Nov 09 12:35 2020]   Office hours changes for Prof. Chang:
  • Monday Nov 16 1-2pm
  • Monday Nov 23 4:30pm - 5:30pm

• [Thu Nov 05 08:25 2020]   Exercise 18 (Set Cover example) due Monday November 9 11:59pm. [Submit]

• [Tue Nov 03 02:55 2020]   Exercise 17 (approximate vertex cover) due Wednesday November 4 11:59pm. [Submit]

• [Tue Nov 03 01:55 2020]   Replaced Question 1 in Homework 9.

• [Mon Nov 02 22:00 2020]   Homework 9 posted. Due Tue 11/10/20 11:59pm

• [Sun Nov 01 21:53 2020]   Please use this Google form to request a topic for Quiz B. If you do not need a make-up quiz, it is also helpful to indicate that.

• [Thu Oct 29 10:30 2020]   Exercise 16 (conjunctive normal form) due Monday November 2 11:59pm. [Submit]

• [Tue Oct 27 00:45 2020]   Exercise 15 (still more NP-completeness practice) due Wednesday October 28 11:59pm. [Submit]

• [Tue Oct 27 00:20 2020]   Homework 8 posted. Due Tue 11/03/20 11:59pm.

• [Thu Oct 22 09:55 2020]   Exercise 14 (even more NP-completeness practice) due Monday October 26 11:59pm. [Submit]

• [Tue Oct 20 15:25 2020]   Exercise 13 (more NP-completeness practice) due Wednesday October 21 11:59pm. [Submit]

• [Tue Oct 20 10:30 2020]   Homework 7 posted. Due Tue 10/27/20 11:59pm.

• [Tue Oct 20 09:53 2020]   Please use this Google form to request a topic for Quiz B. If you do not need a make-up quiz, it is also helpful to indicate that.

• [Wed Oct 14 11:00 2020]   Exercise 12 postponed until Monday, Oct 19.

• [Tue Oct 13 08:45 2020]   Exercise 12 posted. (practice NP-compeleteness construction) due Wednesday October 14 11:59pm [Submit]

• [Tue Oct 06 08:45 2020]   Exercise 11 (matching) due Wednesday 10/7/2020 11:59pm. [Submit]

• [Tue Oct 06 08:45 2020]   Homework 6 posted. Due Tue 10/13/20 11:59pm

• [Mon Oct 05 10:00 2020]   Please use this Google form to request a topic for Quiz A. If you do not need a make-up quiz, it is also helpful to indicate that.

• [Thu Oct 01 01:45 2020]   Exercise 10 (minimum cut, again) due Monday October 5 11:59pm. [Submit]

• [Wed Sep 30 09:45 2020]   Updated course description (long overdue) to reflect removal of self-check questions and participation from grading.

• [Mon Sep 28 23:10 2020]   Homework 5 posted. Due Tue 10/06/20 11:59pm.

• [Mon Sep 28 22:50 2020]   Exercise 09 (minimum cut) due Wednesday September 30 11:59pm. [Submit]

• [Tue Sep 22 08:15 2020]   Homework 4 posted. Due Tue 09/29/20 11:59pm

• [Thu Sep 17 08:14 2020]   Exercise 08 (Fibonacci Heap example) due Wednesday September 23 11:59pm. [Submit]

• [Thu Sep 17 09:00 2020]   Exercise 07 (alternate splay tree insertion) due Monday September 21 11:59pm [Submit]

• [Mon Sep 14 13:20 2020]   Exercise 06 (more practice accounting method for amortized analysis) due Wednesday September 16 11:59pm [Submit]

• [Mon Sep 14 12:15 2020]   Homework 3 posted. Due Tue 09/22/19 11:59pm.

• [Sat Sep 12 14:25 2020]   Link for the original paper on Splay Trees: D. Sleator & R. Tarjan, "Self-adjusting binary search trees", JACM, 32(3):652-686, 1985.
  (Log in to UMBC for full access through the AOK Library.)

• [Sat Sep 12 14:25 2020]   Link for the original paper on Skew Heaps: D. Sleator & R. Tarjan, "Self-adjusting heaps", SIAM Journal on Computing, 15(1):52-69, 1986.

• [Sat Sep 12 12:50 2020]   Posted optional recorded lecture on Longest Common Subsequence.

• [Thu Sep 10 09:00 2020]   Exercise 05 (practice accounting method for amortized analysis) due: Monday September 14 11:59pm [Submit]

• [Mon Sep 07 17:25 2020]   Exercise 04 (practice defining dynamic programming subproblem) due Wednesday September 9 11:59pm [Submit]

• [Mon Sep 07 16:30 2020]   Homework 2 posted.

• [Fri Sep 04 12:00 2020]   Exercise 03 (dynamic programming table for 0-1 Knapsack) due Monday September 7 11:59pm [Submit]

• [Wed Sep 02 13:00 2020]   Added separate web pages that list the self-check questions and the peer-graded exercises.

• [Wed Sep 02 12:00 2020]   Self-check Questions 02 posted. Due: Friday, September 11, 11:59pm

• [Mon Aug 31 23:25 2020]   Fixed the wording of Claim 1 in Exercise 2.

• [Mon Aug 31 23:25 2020]   Exercise 2 posted. Due: Wednesday Sep 2, 11:59pm.

• [Mon Aug 31 21:45 2020]   Homework 1 posted.

• [Thu Aug 27 10:45 2020]   To-do items:
  • Lecture for the Shoemaker & Elves greedy algorithm.
  • Self-check Questions 01. Due: Friday, September 4, 11:59pm
  • Exercise 01 Due: Monday, August 31, 11:59pm.     [Submit]

• [Thu Aug 27 10:45 2020]   Addendum to the quiz retake policy: students who choose to retake two quizzes during the final exam's time slot must pick two different topics.

• [Wed Aug 26 10:45 2020]   If you are added to this class, send email to Prof. Chang at chang@umbc.edu immediately to get access to the course materials. (We are not using Blackboard.)

• [Wed Aug 26 10:05 2020]   Course description and schedule on Google Drive under "Blurbs".

• [Wed Aug 26 10:05 2020]   Be aware of the quizzes listed in the class schedule! Quiz 1 will take place on Thursday September 24.

• [Wed Aug 26 10:05 2020]   Web page up.