Syllabus
This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. We will discuss a number of topics, including greedy algorithms, divide-and-conquer algorithms, dynamic programming, network-flow algorithms, NP completeness and computational intractability, approximation algorithms, and randomized algorithms.
Prerequisites
CMSC 351. Each student is expected to know the following:
- Basic programming (programming with loops, pointers, structures, recursion)
- Basic calculus (manipulation of logarithms, differentiation, integration)
- Discrete mathematics (proofs by induction, sets, permutations, combinations, and basic probability)
- Algorithm analysis techniques (asymptotic notation, solving summations and recurrences)
- Basic data structures (lists, stacks, queues, heaps, trees)
- Common sorting algorithms (e.g., MergeSort, QuickSort, HeapSort, CountingSort, RadixSort)
- Basic graph concepts (representations, DFS/BFS, minimum spanning trees)
If you are unsure whether you satisfy the course prerequisites, please check with me.
Course Work
Course grades will be based on written homeworks (roughly 5), a midterm exam, and a comprehensive final exam. (There will be no programming assignments.) Tentative weights: Homeworks: 35%, Midterm: 25%, Final exam: 40%. Homework submission will be through Gradescope.
Attendance will be required for the midterm exam and the final exam. The midterm is tentatively scheduled to take place on Thu, Apr 3 (possibly in the evening). The final exam is scheduled for Thu, May 15, 10:30am - 12:30pm.
Normally, late homeworks will not be accepted (because solutions will be discussed in class). If you feel that you have a legitimate excuse for handing in a homework late, contact me at least 48 hours before the due date.
All homework assignments are to be done individually, but discussion with classmates regarding general solution strategies is allowed. See below for information the use of AI technology.
The Other Section of 451?
There are two sections of CMSC 451 taught this semester (the other by Prof. Clyde Kruskal). While there will be considerable overlap of course material, the two courses are entirely independent of each other — different topics, different assignments, different schedules.
Piazza
We will be using Piazza for class discussions and important class announcements. Rather than sending email to the instructor or TA, you are encouraged to post your questions to Piazza, which will allow everyone (instructor, TA, and classmates) to view and respond to your question and the answers posted. (If you have a question of a more private nature, you can send email directly to us.) We will be sending out invitations to the class to join Piazza, but feel free to enroll in the class at any time by going to this Piazza sign-up link.
Topics
The following list is tentative, and the order of topics may be changed.
- Introduction: Review of algorithm design and analysis, review of basic graph theory and graph representations
- Graph Exploration: DFS and BFS, connected components, topological sorting, strong components
- Greedy Algorithms: Interval scheduling and partitioning, scheduling to minimize lateness, greedy graph algorithms (and applications), Huffman coding
- Dynamic Programming: Weighted interval scheduling, longest common subsequences, chain matrix multiplication, shortest paths in graphs (Floyd-Warshall and Bellman-Ford)
- Network Flow: Network flow algorithms, bipartite matching, circulations and applications
- NP and Computational Intractability: Polynomial-time reductions, the definition of NP, NP-complete problems
- Approximation Algorithms: Greedy algorithms and bounds on the optimum. Examples of approximation algorithms (vertex cover, travelling salesman, set cover)
Text and Resources
There is no required text. The books below are suggested reference material. Of course, there is lots of information on the Web.
- Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2005.
- Introduction to Algorithms, (3rd Edition), by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw Hill, 2009.
Lecture Videos
Screen and audio-capture of every lecture will made available via Panopto on the class ELMS page. Videos should be released within 24 hours of each lecture. If a video does not appear, please let me know.
Excused Absences
University policies on excused absences apply. (Click here for the full version.) Here is a summary of key points.
- Notify the instructor in a timely manner (ideally prior, but if not as soon as possible). For religious observances, athletic events, and planned absences, please do this at the beginning of the semester.
- Provide appropriate documentation of the absence. In the case of a minor absence (e.g., lecture or recitation), the first absence may be excused by a self-signed note. Otherwise, verifiable documentation must be provided on request.
Missing an exam for reasons such as illness, religious observance, participation in required university activities, or family or personal emergency (such as a serious automobile accident or close relative's funeral) will be excused so long as the absence is requested in writing at least 2 days in advance of the exam date and the student includes documentation that shows the absence qualifies as excused. A self-signed note is not sufficient, as exams are major scheduled grading events.
It is the University's policy to provide accommodations for students with religious observances conflicting with exams, but it is the your responsibility to inform the instructor in advance of intended religious observances. If you have a conflict with one of the planned exams, you must inform the instructor prior to the end of the first two weeks of the class.
For missed exams due to excused absences, the instructor will arrange a makeup exam. If you might miss an exam for any other reason other than those above, you must contact the instructor in advance to discuss the circumstances.
Besides the policies in this syllabus, the University's policies apply during the semester. Various policies that may be relevant appear in the Undergraduate Catalog.
If you experience difficulty during the semester keeping up with the academic demands of your courses, you may consider contacting the Learning Assistance Service. Their educational counselors can help with time management issues, reading, note-taking, and exam preparation skills.
Students with Disabilities
Students with disabilities who have been certified by University's Accessibility & Disability Service as needing any type of special accommodations should see the instructor as soon as possible during the schedule adjustment period (the first two weeks of class). Please provide ADS's letter of accommodation to the instructor at that time.
All arrangements for exam accommodations as a result of disability must be made and arranged with the instructor at least three business days prior to the exam date; later requests (including retroactive ones) will be refused.
UMD Policies for Undergraduate Students
Please refer to the University's guide on Course Related Policies, which provides you with resources and information relevant to your participation in a UMD course.
Use of AI Tools:
You are permitted to use artificial intelligence (AI) tools, such as chatbots, text generators, paraphrasers, summarizers, or solvers, to get guidance on assignments, as long as you do so in an ethical and responsible manner. Essentially, you can think of these tools as ways to help you learn but not to entirely create work for assignments like discussion board posts, essays, presentation slides, and so on. AI is more like your tutor or TA, not a replacement for your independent thinking. This means that you must:
- Not use AI tools to replace your own thinking or analysis
- Cite or explain any AI tools you use
- Be transparent and honest about how you used AI tools
- Be accountable for any mistakes or errors made by the AI tool
If you have any questions about what constitutes ethical and responsible use of AI tools, please consult with the instructor before submitting your work.
Academic Integrity
University policies on academic integrity apply. (Click here for the full version.) Here is a summary of key points.
Assignments and projects are to be completed individually. Therefore, cooperation with others or use of unauthorized materials or services (including both human and AI tools) on assignment or projects is a violation of the University's Code of Academic Integrity. Both the person receiving assistance and the person providing assistance are in violation of the honor code. Any evidence of this, or of unacceptable use of computer accounts, use of unauthorized materials or cooperation on exams or quizzes, or other possible violations of the Honor Code, will be submitted to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion.
- For learning the course concepts, students are welcome to study together or to receive help from anyone else. You may discuss with others the assignment or project requirements, the features of the programming languages used, what was discussed in class and in the class web forum, and general syntax errors.
- When it comes to actually writing an assignment, other than help from the instructional staff, assignments must solely and entirely be your own work. Working with another student or individual, or using anyone else's work in any way except as noted in this paragraph, is a violation of the code of academic integrity and will be reported to the Honor Council.
If you have any question about a particular situation or source then consult with the instructors in advance. Should you have difficulty with a programming assignment you should see the instructional staff in office hours, and not solicit help from anyone else in violation of these rules.
It is the responsibility, under the honor policy, of anyone who suspects an incident of academic dishonesty has occurred to report it to their instructor, or directly to the Honor Council.
Right to Change Information
Although every effort has been made to be complete and accurate, unforeseen circumstances arising during the semester could require the adjustment of any material given here. Consequently, given due notice to students, the instructors reserve the right to change any information on this syllabus or in other course materials. Such changes will be announced and prominently displayed at the top of the syllabus.