CMSC 641: Design and Analysis of Algorithms

Fall 2022, M/W 2:30-3:45, ILSB 116A

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

Teaching Assistant: Aditya Khursale
Office Hours: Tu 5-7pm, F 5-7pm; Webex

Grader: Ujjwal Prazapati

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). Please use your real name or you will be removed.

Texts

Official Required Text

• Introduction to Algorithms, 3rd edition edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press Publisher's Site Amazon
(Note that a fourth edition is due out this spring.)

Other useful resources

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

Description

Objectives

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

Grades

Tests

Homeworks

1. 1 day late (by Saturday 11:59pm) -5%
2. 2 days late (by Sunday 11:59pm) -10%
3. 3 days late (by Monday 11:59pm) -20%
4. 4 days late (by Tuesday 11:59pm) -40%

Final Project

A Note on Plagiarism:

Lectures

Tentative Schedule

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

Additional Resources

There is a class web page, http://www.csee.umbc.edu/~adamb/641, where you will find this syllabus online. Important announcements and updates will be made to this class web page throughout the semester. I will announce at the beginning of class if I make a significant change or addition.

There is a class discord channel for this class. Everyone will be added to this channel. Announcements will be made there, and you can also use it for public communication with your classmates, the TA and instructor. You should either check this channel periodically, or make sure it is set to send you messages by email. Please only post messages appropriate for the entire class to see. Be sure to send messages about grades or other private matters directly to the instructor or TA.

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 you need help with a project or assignments, see a TA or your instructor. You are encouraged to make full use of textbooks and the course web pages.

Academic Integrity policies for projects can be found on the Projects and Support site.

Your homework submissions will be checked for similarities with all other student work. If your work is found to be “substantially similar” to that of another student, or if it is determined that someone else wrote the solutions for you, then, at a minimum, you and the other student (if applicable) will receive a grade of zero for that assignment. Furthermore, all parties concerned will have their prior homeworks re-checked for cheating. Be aware, we use an automated tool to compare projects.

If it is determined that you cheated on an exam, you will, at a minimum, receive a grade of zero for the exam.

Any second Academic Integrity incident, whether on a project, homework assignment, or exam, will result in a grade of ‘F’ for the semester.

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.

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 and Federal law (Title IX) prohibit 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 retaliation should contact the University’s Title IX Coordinator to make a report and/or access support and resources:

Mikhel A. Kushner, Title IX Coordinator (she/they)

410-455-1250 (direct line), kushner@umbc.edu

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 or thinking about 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.

N otice that Faculty are Responsible Employees with Mandatory Reporting Obligations:

All faculty members are considered Responsible Employees , per UMBC’s Policy on Sexual Misconduct, Sexual Harassment, and Gender Discrimination. Faculty are therefore required to report any/ all available information regarding conduct falling under the Policy and violations 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 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 assault, domestic and interpersonal 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:

• The Counseling Center (Main Campus): 410-455-2472 / After-Hours 410-455-3230 [Monday – Friday; 8:30 a.m. – 5 p.m.]
• Center for Counseling and Consultation (Shady Grove Campus): 301-738-6273 (Messages checked hourly)  Online Appointment Request Form
• University Health Services : 410-455-2542 [Monday – Friday 8:30 a.m. – 5 p.m.]
• Pastoral Counseling via Interfaith Center : 410-455-3657; interfaith@umbc.edu [7 days a week; Fall and Spring 7 a.m. – 11 p.m.; Summer and Winter 8 a.m. – 8 p.m.]

Other Resources:

• Women’s Center (for students of all genders): 410-455-2714; womenscenter@umbc.edu . [Monday – Thursday 9:30am-6pm and Friday 9:30am-4pm]
• 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.

Pregnant and Parenting Students

UMBC’s Policy on Sexual Misconduct, Sexual Harassment and Gender Discrimination 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 Inclusion.  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 or return following leave related to pregnancy, delivery, adoption, breastfeeding and/or the early months of parenting.

Pregnant students and students in the early months of parenting may be entitled to accommodations under Title IX through the Office of Equity and Inclusion.

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 Student Disability Service Office .

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 observance accommodations  please contact the Office of Equity and Inclusion at oei@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 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 will be limited.

Additional Policies and Resources

Please see this Google doc for UMBC Policies and Resources during COVID-19.