Course Description
Instructor. Prof. Richard Chang <chang@umbc.edu>
Office Hours: Tu & Th 3pm - 4:30pm ITE 326
Wed 1:30pm - 3:00pm online
Teaching Assistant. Abhishek Chintalapati <abhishc1@umbc.edu>
Office Hours: TBA
Course Web Page. http://umbc.edu/~chang/cs641
Time & Place. Tue & Thu 10:00am – 11:15am, Fine Arts 014
Textbook. Introduction to Algorithms, fourth edition, Cormen, Leiserson, Rivest and Stein.
MIT Press (ISBN: 978-0262046305).
References.
Prerequisites. An undergraduate course on algorithms is a prerequisite for this class. At UMBC, the undergraduate algorithms course (CMSC 441) uses the same textbook and typically covers Chapters 1-4, Appendix A (Big-O notation, recurrences and summations), Chapters 6–9 (Heapsort, Quicksort, “linear-time” sorts and linear-time median algorithms), Chapter 15 (dynamic programming), Chapter 16 (greedy algorithms) and Chapters 22–25 (graph search algorithms, minimum spanning trees and shortest path algorithms). In addition, hash tables and balanced binary trees are covered in CMSC 341 Data Structures. There will be minimal overlap in the material covered in the CMSC 441 and CMSC 641. If you are not familiar with some of these topics, you must have enough preparation to review the material on your own.
Objectives. The objective of this course is to prepare you to learn new algorithms — either from the literature or by designing your own new algorithms. Thus, this class will have you:
A secondary goal of this course is to familiarize students with a range of fundamental algorithms.
Grading. Grades will be based upon the following distribution
Homework | 39% |
Test 0 | 6% |
Tests 1-5 | 55% |
The planned schedule has 13 homework assignments and 6 test topics. However, if a homework assignment or test is canceled and not made up — e.g., UMBC is closed for an extended period — homework will still be worth 39% and tests 61%.
The final letter grade is based on the standard formula:
0 ≤ F < 60, 60 ≤ D < 70, 70 ≤ C < 80, 80 ≤ B < 90, 90 ≤ A ≤ 100
Grades will not be "curved" — that is, the percentages of A’s, B’s and C’s are not fixed.
Lectures & Reading. Lectures provide a unique opportunity for students to ask questions while we are all physically gathered in one location at the same time. The purpose of the lectures is to explain the parts of the reading that are difficult to understand. Lectures do not replace reading. The ability to read and understand the formal language in an algorithms textbook is a skill that you develop by practice.
Tests. There are six test topics:
Each test will consist of one question (possibly with multiple parts) on that topic. Test questions will require students to solve new problems (i.e., not simply regurgitate facts). The tests are in-person, closed-book and closed-notes.
Final Exam. The final exam is scheduled for Tuesday May 23, 10:30am - 12:30pm. There will not be an option to take the final exam early, so make your travel plans accordingly.
The final exam is optional and provides an opportunity for you to improve your test scores. The final exam will have one question on each of the 6 test topics. You may choose to answer any number of topics (including none). However, in a two-hour exam period you will realistically only have time to do 3 or 4 questions.
If you skip a topic on the final exam, then your score for that topic will be your score from the original test. Otherwise, your score for a test topic will be a weighted average of the score on the original test and the score on that topic on the final exam. The original score has a 25% weight and the final exam score for that topic has a 75% weight. For example, if you score 80% on the Test 1 on dynamic programming and 95% on the dynamic programming question on the final exam, then your score for Topic 1 would be:
25% x 80% + 75% x 95% = 20.00% + 71.25% = 91.25%
Note that if you do worse on the final exam than the original test, then your score for that topic will decrease.
Homework Submission. Homework will be submitted online in PDF. You have several options for preparing your responses. You can write on paper and convert to PDF using a smartphone app. This is the recommended method. Please do not just use your phone's camera app and take a picture of your work. Use one of many free scanner apps and adjust the settings so that your submission is legible.
You could also use LaTeX (or equivalent) to prepare a document. (Although drawing diagrams could be quite challenging.) If you have a tablet or a 2-in-1 laptop and you have some skill with a stylus, you can use one of those. Microsoft Word and Powerpoint are not recommended since they are terrible with math notation.
In any case, please use letter size paper (8.5x11 inches) and leave a good margin.
Late Homework. Homework is due on Tuesday by 11:59pm. If you submit late homework, a deduction will be taken:
before next class (by Thu 10am) | -5% |
by end of the week (by Sun 11:59pm) | -15% |
before second class (by next Tue 10am) | -25% |
Late homework will not be accepted after the start of the next Tuesday lecture. This allows for timely grading and discussion.
Three times during the semester, you may use a late homework pass to rescind the penalty for late homework. One pass may be used for Homework 1-5, one for Homework 6-9 and one for Homework 10-13. Late passes do not carry over and do not accrue. E.g., if you submit all four of Homework 1-5 on time, you do not have an extra late pass for the remaining homework.
Homework Policy. You are allowed to, and even encouraged to, collaborate on homework problems. Collaborators and reference materials must be acknowledged at the top of each homework assignment. However, homework solutions must be written up independently. A student who is looking at someone else’s solution or notes, whether in print or in electronic form, while writing up his or her own solution is considered to be cheating. All cases of cheating will be reported to the university, this is standard practice.
Finally, looking up the solutions to homework problems completely defeats the purpose of homework assignments, which is to train a student’s mind to think. Students who bypass this training will do poorly on the test. The primary purpose of doing homework isn't to obtain the correct solution — it is to practice thinking.
University Policies & Resources
The UMBC Graduate School's academic integrity policy is available from the Graduate Catalog.
UMBC Policies on Accessibility & Disability Accommodations; Sexual Assault, Sexual Harassment, Gender Based Violence & Discrimination; Pregnancy and Parenting; Religious Observances & Accommodations; and Hate, Bias Discrimination & Harassment are described at the Office of Equity & Inclusion's website.
Retriever Essentials is a faculty, staff, and student-led partnership that addresses food insecurity in the UMBC community. They offer free groceries, toiletries, baby items, and meal swipes, and have opportunities to engage and volunteer. Pick up items from their pantry, The Essential Space, located in RAC 235 or get a pre-assembled bag of non-perishable food items and personal care products at one of their Food Zones. Email retrieveressentials@umbc.edu about their meal swipe program or to find out how to volunteer with them.