CS 6161: Design and Analysis of Algorithms (Grad), Fall 2020

A PDF version of the following syllabus can be found here: Syllabus

Basic Information

Class Format: Online Synchronous
Class Time: Tuesdays and Thursdays, 5:00 pm to 6:15pm
Instructor: Haifeng Xu
TAs: Additionally, discussions (homework-related, material-related and anything else) are strongly encouraged on Piazza: https://piazza.com/virginia/fall2020/cs6161. Please definitely make sure you join the course website on Piazza!

Course Overview

Overall Description: (1) Introduce major techniques for algorithm design; (2) Rigorously analyze their performances; (3) Understand possibilities and limitations of algorithms --- e.g., what is the best efficiency you can achieve with algorithms? are there problems that cannot be efficiently solved by algorithms?

Covered Topics: Various classic algorithmic problems such as sorting and searching, graph algorithms, geometric algorithms, optimization techniques, intractability and NP-completeness, randomized algorithms, and approximation algorithms.

Learning Objective: After successfully completing this course, you should be able to use the right mathematical tools, notions, and ideas to design provably efficient algorithms for algorithmic questions. This is also what the exams will aim to evaluate.

Course Format: This is a theory course. This means the entire course --- lectures, homework and exams --- will be based on rigorous mathematical tools and will be proof-based. There will be no coding/programming involved in this course, though you are welcome, and encouraged, to implement the learned algorithms after class as your own practice.

Text books (recommended but not required): Prerequisites: Since this is a graduate course, we do not enforce strict requirements. However, the course has substantial elements of derivations and logic reasoning. You should be familiar with the following materials or their equivalence:

Tentative schedule:

The following is a tentative schedule. We will likely deviate from the schedule slightly, but overall these are the topics that we will go over. At a high level, the first half of the course will cover the more standard algorithmic techniques and the second half will cover more advanced topics. Though the schedule is organized by the major algorithmic technique we discuss at each lecture, it is important to note that problems are typically solved by a combination of multiple algorithmic techniques.

Grading and Requirements

Due to the pandemic, we have tried our best to make the course evaluation as flexible as we can. The following is the grading policy and requirements. Any comments and suggestions are warmly welcome.

In cases of medical or other emergencies which interfere with your work, do not worry --- simply have your Resident Dean contact the instructor and we will try our best to accommodate any urgency.

Overall, the evaluation has two components:

Final grades take into account each component. You must achieve a passing grade in all components to pass this course. Although we will not publish hard letter grade cutoffs, just note that to receive an “A” you must have high performance is all categories.

Problem Sets   The problem sets will be managed --- publishing and submission --- through UVA Collab. All problem sets will be written and will be submitted in the format of PDF. Any grading disputes on assignments must be submitted directly through Gradescope within one week of the grades being posted after which the grade is final. The assignments will be graded based on correctness, depth of analysis, and clarity.

Collaboration Policy   The HW will be challenging. You are encouraged to consult with your classmates as you work on the problems. However, you should not share answers. After discussions with your peers, make sure that you can work through the problem yourself and ensure that any answers you submit for evaluation are the result of your own efforts. Cite any books, articles, websites, lectures, etc. that have helped you with your work and list the names of students with whom you have discussed with. Note that understanding the HW problems is important for you to excel in the exams, during which no collaboration is allowed at all.

Late days   Each student is allotted a total of five late days for use on problem sets. A late day extends the due date by 24 hours and a maximum of 2 late days can be used towards any individual assignment. Weekends and holidays are NOT counted as late days. If you have used up your 5 late days, you will be penalized 25% per day, up to two days max, with no credit after two days.

Exams   There are two take-home open-book midterm exams, one covering the first half of the course material (divide and conquer, greedy, dynamic programming and part of linear programming) and the second covering the remaining half of the course material. To allow some flexibility, you will have 24 hours to complete each exam, though it will be designed to take you about 2~3 hours.


Other Related Statements

Honor code (Adapted from Honor Syllabus Example Statement of UVa)

I trust every student in this course to fully comply with all of the provisions of the University’s Honor Code. By enrolling in this course, you have agreed to abide by and uphold the Honor System of the University of Virginia, as well as the policies specific to this course. All suspected violations will be forwarded to the Honor Committee, and you may, at my discretion, receive an immediate zero on that assignment regardless of any action taken by the Honor Committee.

Please let me know if you have any questions regarding the course honor policy. If you believe you may have committed an Honor Offense, you may wish to file a Conscientious Retraction by calling the Honor Offices at (434) 924-7602. For your retraction to be considered valid, it must, among other things, be filed with the Honor Committee before you are aware that the act in question has come under suspicion by anyone. More information can be found at here.

Students with disabilities or learning needs

We thrive to create a learning experience that is as accessible as possible. If you anticipate any issues related to the format, materials, or requirements of this course, please meet with me outside of class so we can explore potential options. Students with disabilities may also wish to work with the Student Disability Access Center to discuss a range of options to removing barriers in this course, including official accommodations. Please visit their website for information on this process and to apply for services online: sdac.studenthealth.virginia.edu. If you have already been approved for accommodations through SDAC, please send me your accommodation letter and meet with me so we can develop an implementation plan together.

Discrimination and power-based violence

The University of Virginia is dedicated to providing a safe and equitable learning environment for all students. To that end, it is vital that you know two values that I and the University hold as critically important:

If you or someone you know has been affected by power-based personal violence, more information can be found on the UVA Sexual Violence website that describes reporting options and resources available - https://eocr.virginia.edu/

As your professor and as a human, I care about you and your well-being and stand ready to provide support and resources as I can. As a faculty member, I am required by University policy and federal law to report what you tell me to the University’s Title IX Coordinator. The Title IX Coordinator’s job is to ensure that the reporting student receives the resources and support that they need, while also reviewing the information presented to determine whether further action is necessary to ensure survivor safety and the safety of the University community. If you wish to report something that you have seen, you can do so at the Just Report It portal. The worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.

Religious accommodations

It is the University’s long-standing policy and practice to reasonably accommodate students so that they do not experience an adverse academic consequence when sincerely held religious beliefs or observances conflict with academic requirements.

Students who wish to request academic accommodation for a religious observance should submit their request in writing directly to me via Email as far in advance as possible. Students who have questions or concerns about academic accommodations for religious observance or religious beliefs may contact the University’s Office for Equal Opportunity and Civil Rights (EOCR) at UVAEOCR@virginia.edu or 434-924-3200.

Section 5.2 - 5.4 are adapted from a SEAS-wide example