CMSC 641: Design and Analysis of Algorithms

Spring 2026, M/W 1:00-2:15, Engineering 231

Instructor: Dr. Adam Bargteil <adamb-at-umbc.edu> (Avoid sending email)
Office Hours: M/W 2:30-3:30pm, ITE 341

Teaching Assistant: Duo Zhong
Office Hours: By appointment;

Prerequisite: CMSC-441 (Design and Analysis of Algorithms) or equivalent or consent of instructor.
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.

Discord: There is a discord server for the class, you will receive an invite after the drop date. Almost all class communication should happen through discord (I miss too many emails). You are responsible for announcements and other information posted to discord. Please use your real name to avoid confusion. Please conduct yourself professionally on the class discord.

Texts

Official Required Text

Introduction to Algorithms, 4th edition edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press Publisher's Site Amazon

Other useful resources

Algorithms, Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani.
Algorithms, Jeff Erickson
Algorithm Design, Jon Kleinberg and Eva Tardos

Description

A study of advanced topics and techniques in discrete algorithms. Assumes student has a solid preparation in undergraduate algorithms (including asymptotic notations, recurrences, divide-and-conquer, greedy algorithms, dynamic programming, and fundamental graph algorithms). Core topics include probabilistic and amortized analysis, network flow, NP-completeness, and parallel algorithms. Selected topics might include: linear programming, computational geometry, randomized algorithms, cryptographic algorithms, and approximation algorithms.

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:

Master advanced algorithm analysis techniques
Practice designing "new" algorithms
Accumulate the background knowledge needed to read and understand algorithms published in research journals
Develop the writing skills for clear and logical presentation of algorithms

A secondary goal of this course is to familiarize students with a range of fundamental algorithms.

Grades

Grades will be based on 8 in-class team exercises (50%), 8 homeworks (20%), and a final exam (30%). Grades will be assigned using letter grades corresponding to a 4-point scale:

Score Greater Than or Equal to:	3.83	3.5	3.16	2.83	2.5	2.16	1.83	1.5	1.16	0.83	0.5	0.0
Grade:	A	A-	B+	B	B-	C+	C	C-	D+	D	D-	F

Homeworks
There will be 8 homework assignments, we will drop the lowest score when calculating your final grade. Responses will receive a single whole letter grade (no plus/minus grading). Responses will be graded on clarity as well as correctness; lengthy, meandering responses will receive lower grades than succinct, clear responses.

Homework Submission: Homework must be submitted online in PDF format. Homework must be typeset using latex using this template. You may use any drawing program you like or hand draw figures and embed them in your pdf. Homework that is not typeset with latex will not be graded.

Late Homework: Homework is due and should be submitted before class; however, tthere will be a grace period until midnight of the day the homework is due to submit. Homework submitted after midnight will not be graded.

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 exercises and exams. The primary purpose of doing homework isn't to obtain the correct solution — it is to practice thinking. I expect a very strong correlation between students who do not understand the homework assignments and students who do not pass the class.
A Note on Plagiarism: Most instances of plagiarism fall into a gray area where reasonable people can disagree (just ask Ed Sheeran). In this course, we will rely on the judgement of the Teaching Assistant in determining whether plagiarism should be sanctioned. If the Teaching Assistant judges that submitted work too closely resembles the work of other students and/or material on the internet the following sanctions will be imposed. For the first such occurrence, a grade of P, corresponding to a zero (0) on the 4-point scale, will be awarded as a warning. The second occurrence will be treated as academic dishonesty, the student will meet with the instructor and the incident will be reported to the University; additionally, a grade of zero will be awarded and the students final grade will be reduced by half a letter grade (.5 "points" on the 4-point scale). A third occurrence will result in a failing grade for the course.
In-class Team Exercises
There will be 8 in-class exercises, we will drop the lowest score when calculating your final grade. Responses will receive a single, letter grade (including plus/minus grading). Students may work in teams of up to four. Exercise questions will require students to solve new problems (i.e., not simply regurgitate facts). Responses will be graded on clarity as well as correctness; lengthy, meandering responses will receive lower grades than succinct, clear responses. Exercises will take place in-person during class. Exercises will be closed-book and closed notes. Exercise responses that are not legible will not be graded.
Final Exam
For the final exam you will respond individually to a multi-part prompt based on one of the eight (8) in-class exercises. The exam will be closed notes and closed book. The instructor will prepare eight (8) prompts and distribute them randomly to students. You should prepare for all eight (8).

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.

Tentative Schedule

Required reading from the book should be completed BEFORE the first date listed below for maximum benefit

#	Date	Topic	CLRS	Additional Resources	Assigned	Due
00	~~Jan 26~~	~~Introduction~~
01	~~Jan 28~~	~~Dynamic Programming~~	14		~~HW 1~~
02	~~Feb 02~~	~~Dynamic Programming~~	14
03	~~Feb 04~~	~~Dynamic Programming Exercise~~	14	~~Exercise Registration~~		~~HW 1~~
04	~~Feb 09~~	~~Greedy Algorithms~~	15		~~HW 2~~
02	Feb 02	Introduction/Dynamic Programming	14		HW 1
03	Feb 04	Dynamic Programming	14
04	Feb 09	Dynamic Programming Exercise	14	Exercise Registration		HW 1
05	Feb 11	Greedy Algorithms	15		HW 2
06	Feb 16	Greedy Algorithms Exercise	15	Exercise Registration		HW 2
07	Feb 18	Amortized Analysis	16		HW 3
08	Feb 23	Amortized Analysis	16
09	Feb 25	Amortized Analysis Exercise	16	Exercise Registration		HW 3
10	Mar 02	Flow Networks	24		HW 4
11	Mar 04	Flow Networks	24
12	Mar 09	Flow Networks	24
13	Mar 11	Flow Networks Exercise	24	Exercise Registration		HW 4
Spring Break
14	Mar 23	Linear Programming	29		HW 5
15	Mar 25	Linear Programming	29
16	Mar 30	Linear Programming Exercise	29	Exercise Registration		HW 5
17	Apr 01	Complexity	34		HW 6
18	Apr 06	Complexity	34
19	Apr 08	Complexity	34
20	Apr 13	Complexity Exercise	34	Exercise Registration		HW 6
21	Apr 15	Approximation Algorithms	35		HW 7
22	Apr 20	Approximation Algorithms	35
23	Apr 22	Approximation Algorithms	35
24	Apr 27	Approximation Algorithms Exercise	35	Exercise Registration		HW 7
25	Apr 29	Parallel Algorithms	26		HW 8
26	May 03	Parallel Algorithms	26
27	May 06	Parallel Algorithms	26
28	May 11	Parallel Algorithms Exercise	26	Exercise Registration		HW 8
	May 20	Final Exam, 1-3pm

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.

If it is determined that you have violated the academic dishonesty policy, the Instructor may impose a penalty up to and including failure of the course and reporting to the appropriate undergraduate or graduate administrative bodies.

Accessibility and Disability Accommodations, Guidance and Resources;
Hate, Bias, Discrimination and Harassment;
Sexual Assault, Sexual Harassment, Gender Based Violence and Discrimination

Accessibility and Disability Accommodations, Guidance and Resources (required)

Accommodations for students with disabilities are provided for all students with a qualified disability under the Americans with Disabilities Act (ADA & ADAAA) and Section 504 of the Rehabilitation Act who request and are eligible for accommodations. The Office of Student Disability Services (SDS) is the UMBC department designated to coordinate accommodations that creates equal access for students when barriers to participation exist in University courses, programs, or activities.

If you have a documented disability and need to request academic accommodations in your courses, please refer to the SDS website at sds.umbc.edu for registration information and office procedures.

SDS email: disAbility@umbc.edu

SDS phone: 410-455-2459

If you will be using SDS approved accommodations in this class, please contact the instructor to discuss implementation of the accommodations. During remote instruction requirements due to COVID, communication and flexibility will be essential for success.

Sexual Assault, Sexual Harassment, and Gender Based Violence and Discrimination (required)

UMBC Policy in addition to federal and state law (to include Title IX) prohibits discrimination and harassment on the basis of sex, sexual orientation, and gender identity in University programs and activities. Any student who is impacted by sexual harassment, sexual assault, domestic violence, dating violence, stalking, sexual exploitation, gender discrimination, pregnancy discrimination, gender-based harassment, or related retaliation should contact the University’s Title IX Coordinator to make a report and/or access support and resources. The Title IX Coordinator can be reached at ecr@umbc.edu or 410-455-1717.

You can access support and resources even if you do not want to take any further action. You will not be forced to file a formal complaint or police report. Please be aware that the University may take action on its own if essential to protect the safety of the community.

If you are interested in making a report, please use the Online Reporting/Referral Form. Please note that, if you report anonymously, the University’s ability to respond will be limited.

Notice that Faculty and Teaching Assistants are Mandated Reporters with Mandatory Reporting Obligations

All faculty members and teaching assistants are considered Mandated Reporters, per UMBC’s Interim Policy on Sex Discrimination, Sex-Based Harassment, and Sexual Misconduct. Faculty and teaching assistants therefore required to report all known information regarding alleged conduct that may be a violation of the Policy to the Title IX Coordinator, even if a student discloses an experience that occurred before attending UMBC and/or an incident that only involves people not affiliated with UMBC. Reports are required regardless of the amount of detail provided and even in instances where support has already been offered or received.

While faculty members want to encourage you to share information related to your life experiences through discussion and written work, students should understand that faculty are required to report past and present sexual harassment, sexual assault, domestic and dating violence, stalking, and gender discrimination that is shared with them to the Title IX Coordinator so that the University can inform students of their rights, resources, and support. While you are encouraged to do so, you are not obligated to respond to outreach conducted as a result of a report to the Title IX Coordinator.

If you need to speak with someone in confidence, who does not have an obligation to report to the Title IX Coordinator, UMBC has a number of Confidential Resources available to support you:

Retriever Integrated Health (Main Campus): 410-455-2472; Monday – Friday 8:30 a.m. – 5 p.m.; For After-Hours Support, Call 988.

Center for Counseling and Well-Being (Shady Grove Campus): 301-738-6273; Monday-Thursday 10:00a.m. – 7:00 p.m. and Friday 10:00 a.m. – 2:00 p.m. (virtual) Online Appointment Request Form

Pastoral Counseling via The Gathering Space for Spiritual Well-Being: 410-455-6795; i3b@umbc.edu; Monday – Friday 8:00 a.m. – 10:00 p.m.

Women, Gender, and Equity Center (open to students of all genders): 410-455-2714; womenscenter@umbc.edu; Monday – Thursday 9:30 a.m. – 5:00 p.m. and Friday 10:00 a.m. – 4 p.m.

Other Resources

Shady Grove Student Resources, Maryland Resources, National Resources.

Child Abuse and Neglect

Please note that Maryland law and UMBC policy require that faculty report all disclosures or suspicions of child abuse or neglect to the Department of Social Services and/or the police even if the person who experienced the abuse or neglect is now over 18.

**Pregnant and Parenting Students (NOW REQUIRED)**

UMBC’s Interim Policy on Sex Discrimination, Sex-Based Harassment, and Sexual Misconduct expressly prohibits all forms of discrimination and harassment on the basis of sex, including pregnancy. Resources for pregnant, parenting and breastfeeding students are available through the University’s Office of Equity and Civil Rights. Pregnant and parenting students are encouraged to contact the Title IX Coordinator to discuss plans and ensure ongoing access to their academic program with respect to a leave of absence – returning following leave, or any other accommodation that may be needed related to pregnancy, childbirth, adoption, breastfeeding, and/or the early months of parenting.

In addition, students who are pregnant and have an impairment related to their pregnancy that qualifies as disability under the ADA may be entitled to accommodations through the Office of Student Disability Services.

Religious Observances & Accommodations

UMBC Policy provides that students should not be penalized because of observances of their religious beliefs, and that students shall be given an opportunity, whenever feasible, to make up within a reasonable time any academic assignment that is missed due to individual participation in religious observances. It is the responsibility of the student to inform the instructor of any intended absences or requested modifications for religious observances in advance, and as early as possible. For questions or guidance regarding religious observances and accommodations, please contact the Office of Equity and Civil Rights at ecr@umbc.edu.

Hate, Bias, Discrimination and Harassment

UMBC values safety, cultural and ethnic diversity, social responsibility, lifelong learning, equity, and civic engagement.

Consistent with these principles, UMBC Policy prohibits discrimination and harassment in its educational programs and activities or with respect to employment terms and conditions based on race, creed, color, religion, sex, gender, pregnancy, ancestry, age, gender identity or expression, national origin, veterans status, marital status, sexual orientation, physical or mental disability, or genetic information.

Students (and faculty and staff) who experience discrimination, harassment, hate, or bias based upon a protected status or who have such matters reported to them should use the online reporting/referral form to report discrimination, hate, or bias incidents. You may report incidents that happen to you anonymously. Please note that, if you report anonymously, the University’s ability to respond may be limited.