CMPSCI 611 : Advanced Algorithms

Objectives: This course provides students with skills in designing efficient algorithms. 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. This course will illustrate these skills through various algorithmic problems and important design techniques.

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

Location: Agricultural Engineering Building, Room 119.

Teaching Staffs:

• Instructor: Hung Le.
  • Email: hungle@cs.umss.du
  • Office: 332 CS Building
  • Weekly Office Hours: Monday 11am -12 pm, Friday 3pm-4pm.

  If my office hours do not work for you and you want to see me, you could either talk to me right after the class (preferred) or set up an appointment by email.

• TAs:

  • Hamid Mozaffari (hamid@cs.umass.edu), office hours: TBA
• Graders:
  • Fenil Manish Doshi (fdoshi@umass.edu)
  • Shanmukh Swaroop Srinivas (shanmukhswar@umass.edu)
  • Divya Katkam (dkatkam@umass.edu)
  • Mohith Akhilesh Dhulipalla (mdhulipalla@umass.edu)

Grading

• Homework (40%): Homework is bi-weekly and includes 6 assignments. The lowest assignment will be weighted 50% only.
• Weekly Quizzes (10%): We will have 11 quizzes total, and the lowest quiz will be drop.
• Midterm 1 (15%): Thu, Oct 07. Midterm 1 will cover divide and conquer, greedy algorithms, and dynamic programming.
• Midterm 2 (15%): Tue, Nov 16. Midterm 2 will cover randomized algorithms, network flow, and linear programming.
• Final (20%): Scheduled by the university and will be comprehensive.

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.

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.

Late Policy: You have one late day on any HW of your choice. Late submissions otherwise will not be graded unless you have a good medical reason. Try your best to honor the deadlines.

Exam Make-up Policies: f 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.

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

Tentative topics:

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

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.

Schedule:

The following tentative schedule might suffer changes.

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

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!

Accommodations for Disabilities: The University of Massachusetts Amherst is committed to making reasonable, effective and appropriate accommodations to meet the needs of students with disabilities and help create a barrier-free campus. If you have a disability and require accommodations, please register with Disability Services, located in 161 Whitmore Hall, (413) 545-0892, to have an accommodation letter sent to your faculty. Information on services and materials for registering is available on the University of Massachusetts Amherst Disability Services page.