Course Description
Instructor. Prof. Richard Chang <chang@umbc.edu>
Office Hours: Tue&Thu 12:30pm – 1:30pm, Wed 1:30pm – 2:30pm, ITE 326
Teaching Assistants. TBA
Grader. TBA
Course Web Page. http://umbc.edu/~chang/cs441
Time & Place. Tue & Thu 10:00am - 11:15am, ITE 229
Textbook. Introduction to Algorithms, fourth edition, Cormen, Leiserson, Rivest and Stein.
MIT Press (ISBN: 978-0262046305).
Prerequisites. Students taking CMSC 441 should have mastered the material covered in the following courses: CMSC 203 (Discrete Structures), CMSC 341 (Data Structures) and MATH 152 (Calculus and Analytic Geometry II). The material in Appendix B, Chapter 10 and Chapter 12 of the textbook (covering sets, elementary data structures and binary search trees) should be familiar. Some knowledge of probability and counting (Appendix C of the textbook) is also expected. Students must be able to understand and be able to write proofs by induction. In addition, proficiency in the implementation of the elementary data structures (e.g. stacks, queues, linked lists, heaps and balanced binary trees) in C/C++ or Java is assumed.
Objectives. In this course students will
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:
Classwork (16) | 4% |
Homework (13) | 30% |
Quizzes (6) | 42% |
Final Exam | 24% |
The planned schedule has 13 homework assignments and 6 quiz topics. However, if a homework assignment or quiz is canceled and not made up — e.g., UMBC is closed for an extended period — homework will still be worth 30% and quizzes 42%.
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. However, depending upon the distribution of grades in the class, there may be adjustments in the students’ favor, but under no circumstances will the letter grades be lower than in the standard formula. As a guideline, a student receiving an A should be able to solve the homework problems with facility; design and analyze new algorithms in written exams; and demonstrate their understanding in a time-limited quiz.
Grades are given for work done during the semester; incomplete grades will only be given for medical illness or other such dire circumstances. In particular, taking a heavy course load is not a legitimate excuse for receiving an incomplete.
Lectures. The purpose of the lectures is to explain the parts of the reading that are difficult to understand. Lectures do not replace the reading. The ability to read and understand the formal language in an algorithms textbook is a skill that you develop by practice.
Quizzes. Quizzes are scheduled for Tuesday 9/24, 10/8, 10/22, 11/5, 11/19 and 12/03. (See Class Schedule.) Each quiz will consist of one or two questions (possibly with multiple parts) on that topic. The questions will require students to solve new problems (i.e., not simply regurgitate facts). The quizzes are in-person, closed-book and closed-notes.
Exams. The Registrar has scheduled the final exam for Tuesday December 17, 10:30am to 12:30pm.
Classwork. Students will be asked to write down answers to questions posed during lecture. The responses will be collected at the end of class and checked for completion. Classwork will be graded on a scale of 0 to 5. Classwork will not be returned. There will be approximately 16 lectures with classwork. If more classwork is assigned, only the highest 16 scores will be counted.
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.
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 Academic Conduct Committee, 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 quizzes. The primary purpose of doing homework isn't to obtain the correct solution — it is to practice thinking. Once you see a solution without thinking about the problem, you have lost the learning opportunity.
Late Homework. Homework is due on Thursdays by 11:59pm. If you submit late homework, a deduction will be taken:
1 day late (by Friday 11:59pm) | -5% |
2 days late (by Saturday 11:59pm) | -10% |
3 days late (by Sunday 11:59pm) | -20% |
4 days late (by Monday 11:59pm) | -40% |
before next class (by Tuesday 10am) | -100% |
Late homework will not be accepted after 4 days. This allows us to discuss solutions during the next lecture.
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.
University Policies and Resources.
The UMBC academic integrity policy is available at: <https://tinyurl.com/yd26tx2d>
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.