CMSC 441: Design and Analysis of Algorithms

Fall 2023, M/W 2:30-3:45, Interdisciplinary Life Sciences Bldg 233

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

Teaching Assistant: Nilanjana Das
Office Hours: Monday 11:00am-1:00pm, Discord

Grader: Anisha Panjari

Prerequisites: (MATH 142 or MATH 152) and CMSC 341 and one of the following (STAT 355, STAT 451, or CMPE 320) all with a grade of ‘C’ or better.

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.

Discord: There is a discord server for the class, you will receive an invite. Almost all class communication should happen through discord (I miss too many emails). Please use your real name to avoid confusion.

Texts

Official Required Text
Other useful resources

Description

This course studies fundamental algorithms, strategies for designing algorithms, and mathematical tools for analyzing algorithms. Fundamental algorithms studied in this course include algorithms for sorting and searching, hashing, and graph algorithms. Mathematical tools include asymptotic notations and methods for solving recurrences. Algorithm design strategies include the greedy method, divide-and-conquer, dynamic programming, and randomization.

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:
  1. Have acquired the mathematical skills to rigorously analyze the running time, memory usage and correctness of algorithms.
  2. Have gained the problem-solving skills needed to develop algorithms for new problems using several algorithmic paradigms including: iterative improvement, divide and conquer, greedy and dynamic programming.
  3. Be familiar with the performance analysis and proofs of correctness for a broad range of standard algorithms (sorting & searching and basic graph algorithms).

Grades

Grades will be based on 5 in-class "exercises" (50 percent total), 10 homeworks (20 percent total), and a final exam (30 percent). All coursework will be graded on a standard 4-point scale corresponding to letter grades A-E. Grades will be assigned by rounding, specifically using the following cutoffs:
Score Greater Than or Equal to:     3.5  2.5  1.5  0.5 
Grade: A B C D
The instructor may assign higher final grades than indicated by the table (i.e. a 3.45 may receive an 'A' final grade). The instructor will not assign a higher grade to any student that explicitly or implicitly asks for a higher grade.

In-class Exercises

Each in-class exercise will be worth 10 percent of your grade. Responses will receive a single, whole letter grade (no plus/minus grading).
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. There will be an optional group discussion period during each in-class exercise as described in class. Exercise responses that are not legible will not be graded.

Homeworks

There will be 10 homework assignments, each worth 2 percent of your grade. Responses will receive a single grade of 'A', 'C', or 'E'. 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 may be typeset using latex. A suggested template is here this template. You may use any drawing program you like or hand draw figures and embed them in your pdf. Homework that is not legible will not be graded.

Late Homework: Homework is due on Mondays by 11:59pm. If you submit late homework, a deduction will be taken:
  1. 1 day late (by Tuesday 11:59pm) -5%
  2. 2 days late (by Wed 11:59pm) -10%
  3. 3 days late (by Thurs 11:59pm) -20%
  4. 4 days late (by Friday 11:59pm) -40%
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.

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 the test. 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.

Final Exam

There will be a final exam worth 30% of the final grade. The final exam will occur during the University specified final exam slot: Friday 12/15 from 1-3pm.

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 and Grader in determining whether plagiarism should be sanctioned. If the Teaching Assistant or Grader judge 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 zero 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.

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 Aug 30 Introduction 1.1-3.2      
NA Sep 4 Labor Day  
01 Sep 6 Divide and Conquer 4.1-4.5  
02 Sep 11 Heapsort 7 hw01
03 Sep 13 Quicksort 6    
04 Seb 18 More Sorting 8 hw02 hw01
05 Sep 20 Order Statistics 9    
NA Sep 25 In-class Exercise 1   hw03 hw02
06 Sep 27 Dynamic Programming 14  
07 Oct 2 Dynamic Programming 14 hw04 hw03
08 Oct 4 Dynamic Programming 14  
NA Oct 9 In-class Exercise 2 29 hw05 hw04
09 Oct 11 Greedy Algorithms 15  
10 Oct 16 Greedy Algorithms 15 hw06 hw05
11 Oct 18 Greedy Algorithms 15
NA Oct 23 In-class Exercise 3 hw07 hw06
12 Oct 25 Basic Graph Algorithms 20
13 Oct 30 Basic Graph Algorithms 20 hw08 hw07
14 Nov 1 Basic Graph Algorithms 20  
NA Nov 6 In-class Exercise 4 hw09 hw08
15 Nov 8 Minimum Spanning Trees 21
16 Nov 13 Shortest Paths 22 hw10 hw09
17 Nov 15 Flow Networks 24
NA Nov 20 In-class Exercise 5 (Register here)   hw10
NA Nov 22 Thanksgiving (no class)
18 Nov 27 Informed Search Algorithms Russell and Norvig Slides
19 Nov 29 Game Palying (Adverserial Search) Russell and Norvig Slides
20 Dec 4 NP Complete 34   hw11
21 Dec 6 NP Complete 34    
22 Dec 11 Review     hw11
NA Dec 15 Final Exam 1-3pm    

Additional Resources

There is a class web page, http://www.csee.umbc.edu/~adamb/441, 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 (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 titleixcoordinator@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 Responsible Employees with Mandatory Reporting Obligations

All faculty members and teaching assistants are considered Responsible Employees, per UMBC’s Policy on Sexual Misconduct, Sexual Harassment, and Gender Discrimination . 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.

Other Resources

Women’s 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.

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

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 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.