CMSC 641: Design and Analysis of Algorithms

Spring 2021, Tu/Th 1:00-2:15, ENG 231

Instructor: Dr. Adam Bargteil <adamb-at-umbc.edu> (Avoid sending email)
Office Hours: M 2-3pm, Th 4-5pm; Zoom

Teaching Assistant: Aditya Khursale
Office Hours: W 2-4pm, F 4-6pm; Webex


Grader: Ujjwal Prazapati

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). If class goes virtual, info will be announced on discord. Please use your real name or you will be removed.

Texts

Official Required Text
Other useful resources

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:
  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
A secondary goal of this course is to familiarize students with a range of fundamental algorithms.

Grades

Grades will be based on tests (40%), homeworks (30%), and programming projects (30%). More specifically, there will be six (6) tests, twelve (12) homeworks, and two (2) programming projects.

Tests

We will drop your lowest Test score, so each remaining test will be worth 8% of your grade. We will grade them on an 8-point scale with 0 points being awarded to incorrect answers, 2 points being award to "blank" answers (write the word "blank" instead of an answer), 5 points to answers that demonstrate some understanding of the problem and 8 points to mostly correct answers. Tests will typically be a single question and you will be given roughly have of a lecture to complete each. Test questions will require students to solve new problems (i.e., not simply regurgitate facts). Tests will take place in-person during class. Tests will be closed-book and closed notes.
There will be six test topics:
  1. Dynamic Programming
  2. Greedy Algorithms
  3. Amortized Analysis
  4. Network Flow
  5. NP-completeness
  6. Approximation Algorithms

Homeworks

There will be 12 homework assignments, each worth 2.5% of your grade. An incorrect response will earn 0 points, a blank answer (again, write "blank") will earn .5%, an answer that demonstrates some understanding will earn 1.5%, and mostly correct answers will earn full, 2.5% credit.

Homework Submission: Homework will be submitted online in PDF. You have several options for preparing your responses. You can write on paper and convert to PDF using a smartphone app.This is the recommended method. Please do not just use your phone's camera app and take a picture of your work. Use one of many free scanner apps and adjust the settings so that your submission is legible. If we cannot easily read your answer it will be considered "blank."

You may also use LaTeX (or equivalent) to prepare a document. (I would choose this option myself, although drawing diagrams could be quite challenging.) If you have a tablet or a 2-in-1 laptop and you have some skill with a stylus, you can use one of those. Microsoft Word and Powerpoint are not recommended since they are terrible with math notation (though latexit combined with keynote/pages does pretty well).

In any case, please use letter size paper (8.5x11 inches), preferably unlined, and leave a good margin.

Late Homework: Homework is due on Thursdays by 11:59pm. If you submit late homework, a deduction will be taken:
  1. 1 day late (by Friday 11:59pm) -5%
  2. 2 days late (by Saturday 11:59pm) -10%
  3. 3 days late (by Sunday 11:59pm) -20%
  4. 4 days late (by Monday 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. One pass may be used for Homework 1-4, one for Homework 5-8 and one for Homework 9-12. Late passes do not carry over and do not accrue. E.g., if you submit all four of Homework 1-4 on time, you do not have an extra late pass for the remaining 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.

Programming Projects

There will be two programming projects, each worth 15%, ruberics will be shared when the projects are assigned. These will be submitted through git, details TBA. Note: This plan is tentative, the total number of tests and homeworks may change if schedules slip or if, for example, UMBC is closed for an extended period. The relative percentages devoted to tests, homeworks, and projects will not change.

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 Assigned Due
Feb 01 Introduction / Dynamic Programming 15.1-15.4    
Feb 03 Dynamic Programming 15.1-15.4 HW1  
Feb 08 Greedy Algoriths 16.1-16.4    
Feb 10 Greedy Algorithms 16.1-16.4 HW2 HW1
Feb 15 Amortized Analysis 17.1-17.4    
Feb 17 Amortized Analysis 17.1-17.4 HW3 HW2
Feb 22 Network Flow 26.1-26.3    
Feb 24 Test 1: Dynamic Programming / Test 2: Greedy Algorithms   HW4 HW3
Mar 01 Network Flow 26.1-26.3    
Mar 03 Network Flow 26.1-26.3 HW5 HW4
Mar 08 Network Flow 26.1-26.3    
Mar 10 Disjoint-Set Union 21.1-21.4 HW6 HW5
Mar 15 Fibonacci Heaps 19.1-19.4    
Mar 17 Test 3: Amortized Analysis / Test 4: Network Flow   HW6
Mar 22 Spring Break    
Mar 24 Spring Break    
Mar 29 NP Completeness 34.1-34.5    
Mar 31 NP Completeness 34.1-34.5 HW7  
Apr 05 NP Completeness 34.1-34.5  
Apr 07 Approximation Algorithms 35.1-35.5, notes, slides HW8 HW7
Apr 12 Approximation Algorithms 35.1-35.5
Apr 14 Approximation Algorithms 35.1-35.5 HW9 HW8
Apr 19 Linear Programming 29, Slides   Project 1
Apr 21 HW10 HW9
Apr 26    
Apr 28 Test 5: NP-completeness / Test 6: Approximation Algorithms HW11 HW10
May 03    
May 05 HW12 HW11
May 10    
May 10 HW12
May 12    
May 17   Project 2

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.

Covid-19

Obviously, the pandemic is still ongoing. There is a pretty good chance some of our lectures will be virtual because I will exhibit symptoms or be exposed. There is also a good chance you will need to miss some lectures because you exhibit symptoms or otherwise need to quarantine. Virtual lectures, and joining details, will be announced through Discord and email to all registered students. Virtual lectures will take place on zoom. All office hours will be virtual (through zoom). I do not plan to be on campus except during lecture.

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:

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