CMPSCI 611 : Advanced Algorithms Spring 2023

Last Updated: January 31 2023.

Credit Hours: 3

Prerequisites: Students are expected to have mathematical maturity and knowledge of COMPSCI 311 or equivalence.

Teaching Staffs:

• Instructor: Hung Le.
  • Email: hungle@cs.umss.du
  • Office: 332 CS Building
  • Office hours: TBA
• TAs: TBA

Class Meetings: Tue/Thu 10:00 AM - 11:15 AM from Feb 06 - May 17

Objectives: This course provides students with skills in designing efficient algorithms. We will go through a variety of algorithm design techniques, including greedy, divide and conquer, dynamic programming, network flow, linear programming, randomized algorithms, and approximation algorithms. We will illustrate these design techniques in solving different algorithmic problems. The emphasis of this course is on the mathematical aspects of designing algorithms.

Learning Outcomes: After completing this course, students are expected to be able to formulate an algorithmic problem, design an algorithm for the problem, prove the correctness, and analyze the running time.

Location: Hasbrouck Lab Room 124

Required Textbook: Lectures will be based on Jeff Erickson notes. Slides will be posted on Moodle.

Optional Textbook:

• Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
• Algorithm Design by Kleinberg and Tardos (KT).
• Algorithms by Dasgupta, Papadimitriou, Vazirani (DPV).
• Randomized Algorithms by Motwani and Raghavan (MR).
• Probability and Computing by Mitzenmacher and Upfal (MU).
• Approximation Algorithms by Vazirani.

Tentative topics:

• Divide and Conquer (2 lectures)
• Dynamic Programming (2 lectures)
• Greedy Algorithms (3 lectures)
• Randomized Algorithms (3 lectures)
• Network Flow (3 lectures)
• Linear Programming (2 lectures)
• NP-Completeness (2 lectures)
• Approximation Algorsithms (3 lectures)

Schedule:

Grading

• Homework (40%): Homework is bi-weekly and includes 5 assignments and 1 bonus assignment. The grade of the bonus assignment could be used to replace the lowest grade of any 5 regular assignments.
• Weekly Quizzes (8%): We will have 4 quizzes, and two bonus quizzes. The grades of two bonus quizzes could be used to replace the lowest grade of any two other quizzes.
• Attendance (2%)
• Midterm 1 (15%)
• Midterm 2 (15%)
• Final (20%): Scheduled by the university and will be comprehensive.

Grading Scale: A (100-90), A- (89-84), B+ (83-78), B (77-72), B- (71-66), C+ (65-60), C (59-54), F (53-0)

Late Policy: You have one late day on any HW of your choice, and you have to decide applying the late day to a homework before the deadline. For other HWs, each one hour late within 24 hours incurs 2 points of penalty. Submission of more than 24 hours late will not be graded unless you have a good medical reason. Try your best to honor the deadlines.

Exam Make-up Policies: If you have a conflict exam with another class, you should contact University Registrar’s Office. If you cannot attend the exam for a medical reason, please notify the instructor at least one week before the exam. If you have a medical emergency, contact the instructor as soon as possible. You need to provide a document for the medical reason.

SAT/UNSAT: Any request for SAT/UNSAT must be made before the final exam. SAT/UNSAT option will not be given to anyone committing academic dishonesty.

Platforms: We will use Moodle for general logistics, Campuswire for discussion and Gradescopes for homework assignments.

Communication Policy: Questions regarding homework assignments/class materials should be posted on Campuswire. All questions will be answered within 24 hours, except over weekends. Other questions should be sent by email to the instructor and/or TAs.

Posting Policy: You are not allowed to post any material in this course to public websites without the permission of the instructor.

Academic Honesty and Collaboration Policy:

• You must do exams and quizzes on your own. No collaboration is allowed.
• You might collaborate with at most 2 other students on homework. You must specify anyone you collaborated with in your submissions. The collaboration is verbal only. The write-up must be your own. You are NOT allowed to talk about the homework with anyone else outside your group (except TAs and the instructor). You are NOT allowed to consult any material on the Internet to do your homework.
• You are allowed to bring at most 2 pages of A4 cheatsheets to the exams. NO other materials are allowed.
• DO ask if you have any questions regarding academic honesty.

As members of the College of Information and Computer Sciences at UMass Amherst, we expect everyone to behave responsibly and honorably. In particular, we expect each of you not to give, receive, or use aid in examinations, nor to give, receive, or use unpermitted aid in any academic work. Doing your part in observing this code, and ensuring that others do likewise is essential for having a community of respect, integrity, fairness, and trust. If you cheat in a course, you are taking away from your own opportunity to learn and develop as a professional. You also hurt your colleagues, and this will hurt people you will work with in the future, who expect an honest and responsible professional.

As faculty, we pledge to use academic policies designed for fairness, avoiding situations that are conducive to violating academic honesty, as well as unreasonable or unusual procedures that assume dishonesty. We will follow the university’s Academic Honesty Policy and Procedures. This means we will report instances of dishonesty, which may lead to formal sanction and/or failing the course.

Attendance Policies: Attendance is not optional. If you do not attend a lecture, you are responsible for learning the materials covered in the leccture yourself. A small percentage point will be given to those who attend the lectures.

Accommodations for Disabilities: The University of Massachusetts Amherst is committed to providing an equal educational opportunity for all students. If you have a documented physical, psychological, or learning disability on file with Disability Services (DS), you may be eligible for reasonable academic accommodations to help you succeed in this course. If you have a documented disability that requires an accommodation, please notify the instructor within the first two weeks of the semester so that we can make appropriate arrangements. For more information, consult the Disability Services website at https://www.umass.edu/disability/.

Equity and Inclusion Statement: We are committed to fostering a culture of diversity and inclusion, where everyone is treated with dignity and respect. This course is for everyone. This course is for you, regardless of your age, background, citizenship, disability, sex, education, ethnicity, family status, gender, gender identity, geographical origin, language, military experience, political views, race, religion, sexual orientation, socioeconomic status, or work experience. Because of that, we should realize that we will be bringing different skills to the course, and we will all be learning from and with each other. We may have different backgrounds and skills in courses taken, mathematical, algorithmic, coding or testing background, ways to communicate orally and in writing, working alone or in groups, or plans for professional careers.

Please be kind and courteous. There’s no need to be mean or rude. Respect that people have differences of opinion, and work and approach problems differently. There is seldom a single right answer to complicated questions. Please keep unstructured critique to a minimum; any criticism should be constructive.

Disruptive behavior is not welcome, and insulting, demeaning, or harassing anyone is unacceptable. In particular, we don’t tolerate behavior that excludes people in socially marginalized groups. If you feel you have been or are being harassed or made uncomfortable by someone in this class, please contact a member of the course staff immediately, or if you feel uncomfortable doing so, contact the Dean of Students office.

This course is for all of us. We will all learn from each other. Welcome!

Names & Pronouns: Everyone has the right to be addressed by the name and pronouns that they use for themselves. You can indicate your preferred/chosen first name and pronouns on SPIRE, which appear on class rosters. I am committed to ensuring that I address you with your chosen name and pronouns. Please let me know what name and pronouns I should use for you if they are not on the roster. Please remember: A student’s chosen name and pronouns are to be respected at all times in the classroom.

Title IX Statement: UMass is committed to fostering a safe learning environment by responding promptly and effectively to complaints of all kinds of sexual misconduct. If you have been the victim of sexual violence, gender discrimination, or sexual harassment, the university can provide you with a variety of support resources and accommodations If you experience or witness sexual misconduct and wish to report the incident, please contact the UMass Amherst Equal Opportunity (EO) Office (413-545-3464, equalopportunity@admin.umass.edu) to request an intake meeting with EO staff. Members of the CICS community can also contact Erika Lynn Dawson Head, director of diversity and inclusive community development (erikahead@cics.umass.edu, 860-770-4770).