Syllabus
Course Description
This course studies advanced topics and techniques in algorithms, strategies for designing algorithms, and mathematical tools for analyzing algorithms. Algorithm design strategies include amortized analysis, parallel computation, randomization, greedy algorithms, and dynamic programming. Students will learn to design new algorithms, to analyze the time and space usage and correctness of algorithms, to apply and adapt fundamental algorithms to new problems, and to solve problems and to express their solutions using the language and concepts of algorithms and related mathematical tools.
An undergraduate algorithms course is a prerequisite for this course. Topics that you should already be familiar with include asymptotic notation, recurrences, summations, Heapsort, Quicksort, linear-time sorting, linear-time medians, dynamic programming, greedy algorithms, and graph search algorithms. These topics are covered in the textbook, Chapters 1 – 4, 6 – 9, 15, 16, 22 – 25, and Appendix A. If you are not familiar with some of these topics, you may need to learn the material on your own.
Textbook
The textbook Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, and Stein is strongly recommended. Homework exercises will be assigned directly from the textbook. Also, you will find it very helpful for filling in any material you missed during lecture.
Other References
There are a number of other books that I use while preparing lectures and which you may find useful. Optional references to some of these books are included in the course schedule.
- John Kleinberg and Eva Tardos, Algorithm Design, Pearson Education, Inc. (2006).
- Dexter Kozen, The Design and Analysis of Algorithms, Springer-Verlag (1992).
- Ryan O'Donnell, Analysis of Boolean Functions, Cambridge University Press (2014).
- Christos Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Inc. (1994).
Lectures and Readings
You are expected to attend all lectures for this course and are responsible for all material covered in class. If you should happen to miss a lecture or a lab, you are responsible for getting any missed notes or announcements from a classmate.
Schedule
The course schedule includes lecture topics, quiz dates, and due dates for homeworks.
Grading Criteria
Your grade in this course is based on homeworks, quizzes, and a final exam as follows:
| Item | Weight |
|---|---|
| Homework Average (best 10 scores) | 25% |
| Quiz Average (best 5 scores) | 50% |
| Final Exam | 25% |
Letter grades will follow the standard scale: A ≥ 90, 90 > B ≥ 80, 80 > C ≥ 70, 70 > D ≥ 60, 60 > F.
Please note that I do not give +/- grades.
All grades will be posted on Blackboard.
Your grade is based on timely work accomplished during the semester. Late assignments will not be accepted unless authorized in advance. Make-up exams will only be given for documented medical illness, family emergency, or other dire circumstances.
Homework
There will be 12 homework assignments; your best 10 scores will be used to compute your final homework average. Homework assignments will be posted on the course website; homework is due at the start of class on the days indicated on the course schedule. There are no make-ups for homework assignments.
Quizzes
There will be six quizzes during the semester; your best five scores will be used to compute your final quiz average. There are no make-ups for quizzes except in the case of documented illness or personal emergency. Quiz problems will be similar to problems from completed homeworks.
Final Exam
The exam will be cummulative and will include problems similar to those in the homework and quizzes.
- Wednesday, December 21, 1:00 – 3:00
Blackboard
All grades will be posted on Blackboard. Also, I will use Bb for all course announcements. Please contact me if you have difficulty accessing the CMSC 641 Bb site.
Academic Conduct Policies
By enrolling in this course, each student assumes the responsibilities of an active participant in UMBC’s scholarly community in which everyone’s academic work and behavior are held to the highest standards of honesty. Cheating, fabrication, plagiarism, and helping others to commit these acts are all forms of academic dishonesty, and they are wrong. Academic misconduct could result in disciplinary action that may include, but is not limited to, suspension or dismissal. To read the full Student Academic Conduct Policy, consult the Academic Integrity Resources for Students page, the Faculty Handbook (Sections 14.2-14.3), or for graduate courses, the Graduate School website.
Your homeworks, quizzes, and final exam will be checked for similarities with all other students' work. If your work is found to be substantially similar to that of another student, or if it is determined that someone else did your work for you, then, at a minimum, you and the other student (if applicable) will receive a grade of zero for that assignment and a 10 point deduction (one letter grade) in your semester average.
Any act of academic misconduct will be reported to the University’s Academic Conduct Committee for further action, which may include, but is not limited to, academic suspension or dismissal from the University.
Email Policy
Please reserve email for topics that cannot wait until class or office hours. Questions about course content will be answered in class unless there is a clear need for a quicker response.