CS 483: Analysis of Algorithms
George Mason University Department of Computer Science
Section 003: Fall 2022 - 1:30-2:45pm Mon/Wed - East 201
Section 004: Fall 2022 - 3:00-4:15pm Mon/Wed - Planetary Hall 131

Professor: Ivan Avramovic
Email NetID: iavramo2
Hours: 12:00-1:00pm Monday; 10:30-11:30am Thursday
Phone/Office: (703) 993-5426 / D215K Buchanan Hall

Assistants: (see Piazza for hours)

GTA: Shiva Shukla (sshukla7)
GTA: Utkrist Thapa (uthapa2)
UTA: Benjamin Wall

Prerequisites: CS310, CS330, and MATH125 (C or better in all)
Textbook: Kleinberg and Tardos, Algorithm Design, 1st Edition
Other requirements:
Access to a modern computer capable of running compiler tools (e.g. Java or C).
A scanner, camera, or digital drawing tool to use to prepare digital uploads of homework.
Be prepared to move online at any moment, which would require a computer with reliable Internet, web browser, and audio for use with Blackboard Collaborate Ultra videoconferencing

Lectures: Lectures will be held in-person.
Course resources:
Piazza for questions and discussion. Please note that while Piazza now requests donations, it is due to a change in Piazza's business model independent from any input from the university; students should not feel obligated to provide donations.
Blackboard to view grades and course materials.
GradeScope to for homework and exam grades

Schedule: see below for schedule

Description

Analyzes computational resources for important problem types by alternative algorithms and their associated data structures, using mathematically rigorous techniques. Specific algorithms analyzed and improved.

Outcomes

  1. Students will understand classical problems in Computer Science.
  2. Students will understand classical algorithm design and analysis strategies.
  3. Students will analyze the computability of a problem.
  4. Students will design and analyze new algorithms to solve a computational problem.
  5. Students will reason algorithmically.
Topics

Grades

Grading Scale

Grade A+AA- B+BB- C+CC- DF
max 9791 898781 797771 6959
min 989290 888280 787270 60

Policies

Honor Code

Graded work in this class is individual unless otherwise specified on an assignment. Any direct contribution on an exam or assignment will be treated as a violation of George Mason's Honor Code and the CS Department Honor Code, and will typically result in failing the class.

Some kinds of participation in third-party online study sites violate the GMU Honor code: these include accessing exam questions for this class which have been uploaded by others; accessing exam or assignment answers for this class; uploading of any of the instructor's materials or exams; and uploading any of your own answers or finished work. It is your resposibility to protect your work, including protecting your computer with a password and avoiding sites which make your work publicly visible. Always consult with the professor before using these sites.

Please respect the importance of upholding the Honor Code, since it affects the meaningfulness of your degree and the degrees of other students. As a practical matter, an understanding of algorithms has a strong potential to impact your ability to land a job and perform well in your future careers; you put yourself in the best position to gain that understanding when you rely on your own work.

Privacy statment

All course materials posted to Blackboard or other course site are private to this class; by federal law, any materials that identify specific students (via their name, voice, or image) must not be shared with anyone not enrolled in this class. In the event that any class meetings need to be held synchronously online, those classes will be recorded to provide necessary information for students in this class. Recordings will be stored on Blackboard and will only be accessible to students taking this course during this semester.

Disability accomodations

Disability Services at George Mason University is committed to providing equitable access to learning opportunities for all students by upholding the laws that ensure equal treatment of people with disabilities. Students seeking accommodations for this class, please first visit Disability Services (ods@gmu.edu; 703-993-2474) for detailed information about the Disability Services registration process. Then please discuss the approved accommodations with the instructor. The Disability Services office can be found in Student Union Building I (SUB I), Suite 2500.

Diversity and inclusion

George Mason University promotes a diverse, inclusive, and anti-racist environment, under the belief that a just and equitable learning environment is a strong learning environment. Students are valued as individuals, irrespective of differences in race, ethnicity, national origin, first language, economic status, gender, gender expression and identity, sexual orientation, religion, disability, or age. As an important member of the GMU community, the Department of Computer Science is integral to the goal of cultivating an environemnt which is committed to inclusion and anti-racism.

Students who prefer to be addressed by a specific name or gender pronouns should share this information with the instructor (he/him). Additionally, name and pronouns can be changed in the GMU records.

Title IX

As a faculty member and designated "Responsible Employee," the instructor is required to report all disclosures of sexual assault, interpersonal violence, and stalking to Mason's Title IX Coordinator, per university policy 1412. Students who wish to speak with someone confidentially, should contact the Student Support and Advocacy Center (ssac@gmu.edu; 703-993-3686) or Counseling and Psychological Services (caps@gmu.edu; 703-993-2380). Assistance may also be sought from GMU's Title IX Coordinator (titleix@gmu.edu; 703-993-8730).

COVID-19

This class is in person during the Fall semester, but circustances have the potential to change due to the ongoing pandemic. For current information regarding the virus and university policy regarding the virus, consult the Safe Return to Campus page.

Schedule (subject to change)

Week Date Topic Assignments/Notes
week 1 Aug 22 Introduction, Sections 1.0-1.2
Aug 24 Analysis Basics, Sections 2.0-2.1 🅐 HW 1 assigned
week 2 Aug 29 Asymptotic Analysis, Sections 2.2-2.6 🅐
Aug 31 Amortized Analysis 🅐 HW 1 due; HW 2 assigned
week 3 Sep 5 No class Labor Day
Sep 7 Graph Algorithms, Sections 3.0-3.6 🅟 HW 2 due; HW 3 assigned
week 4 Sep 12 cont. 🅟
Sep 14 Greedy Algorithms, Sections 4.0-4.4 🅣 HW 3 due; HW 4 assigned
week 5 Sep 19 cont. 🅣
Sep 21 cont., Sections 4.5-4.8 🅣 HW 4 due; Coding 1 assigned
week 6 Sep 26 cont. 🅣
Sep 28 Divide and Conquer, Sections 5.0-5.6 🅣 HW 6 assigned
week 7 Oct 3 cont. 🅣
Oct 5 Midterm Review Coding 1 due
week 8 Oct 11 Midterm Exam Class meets Tuesday due to Fall Break
Oct 12 Sorting 🅟
week 9 Oct 17 Dynamic Programming, Sections 6.0-6.7 🅣
Oct 19 cont. 🅣 HW 6 due; HW 9 assigned
week 10 Oct 24 Shortest Path, Sections 6.8-6.10 🅟
Oct 26 cont. 🅟 HW 9 due; HW 10 assigned
week 11 Oct 31 Max Flow, Sections 7.0-7.3 🅟
Nov 2 cont. 🅟 HW 10 due; HW 11 assigned
week 12 Nov 7 Network Flow, Sections 7.5-7.6, 7.10 🅣
Nov 9 cont. 🅣 HW 11 due; HW 12 assigned
week 13 Nov 14 Hard Problems (P vs NP), Sections 8.0-8.7, 8.10 🅟
Nov 16 cont. 🅐 HW 12 due; Coding 2 assigned
week 14 Nov 21 Randomized Algorithms 🅣
Nov 23 No class Thanksgiving Recess
week 15 Nov 28 Special Topics
Nov 30 Final Review Coding 2 due; Last day of class
exam week Dec 7 Final Exam Section 003 1:30-4:15pm (Wednesday)
Dec 12 Final Exam Section 004 1:30-4:15pm (Monday)

🅐 Focuses on techniques for analyzing and evaluating algorithms.
🅟 Focuses on solutions to significant algorithmic problems.
🅣 Focuses on a general algorithmic techniques applicable to a wide range of problems.