Professor: Ivan Avramovic
Email NetID: iavramo2
Hours: 1:30pm-2:30pm Mon; 11:30am-12:30pm Wed
Phone/Office: (703) 993-5426 / D215K Buchanan Hall

Assistants: (see Piazza for hours and contact info)

Yuman Wu
Yanlin Zhou

Prerequisites: CS310, CS330, and MATH125 (C or better in all)
Textbook: Tim Roughgarden, Algorithms Illuminated, Omnibus Edition
Other requirements:
Access to a modern computer capable of running compiler tools (i.e. Java).

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.
Canvas to view grades and course materials, and to take online assessments.
GradeScope for feedback on exams and in-class assignments.

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 identify and solve classical problems in Computer Science.
2. Students will recognize and apply classical algorithm design techniques.
3. Students will assess solutions using classical algorithm analysis strategies.
4. Students will design and analyze new algorithms to solve computational problems.
5. Students will demonstrate an ability to reason algorithmically.

Topics

• Analysis Basics
  • Asymptotic Runtime (Big-O notation)
• Graph Algorithms
  • Shortest-Path Algorithms
  • Network Flow Algorithms
• Algorithmic Techniques
  • Greedy Algorithms
  • Divide-and-Conquer Algorithms
  • Dynamic Programming
• Hard Problems (P vs NP problem classes)

Grades

• Assessments: 20%
  • Assessments will be given in-class, weekly, a week after the material has been reviewed.
  • Assessments must be done individually.
  • Lowest two assessement scores are dropped.
• Quizzes: 10%
  • Quizzes will be assigned weekly and take place via Canvas.
  • Open Monday through Tuesday each week and can be started any time during that window.
  • 30 minutes long from the moment they are started.
  • Quizzes are auto-graded.
  • Lowest quiz grade is dropped.
• Code: 10%
  • Coding assignments are individual unless otherwise specified on the assignment.
  • Coding is done using the Java language (version 17 or above).
  • Coding assignments are auto-graded and must compile to receive credit.
• Exams (midterm + final): 25% + 35%
  • In-class, unless otherwise dictated by circumstances.
  • The better exam receives a higher weight.
  • Final exam may revisit topics, but is not strongly cumulative.
  • Closed book; one letter-sized, double-sided sheet of handwritten notes is permitted.
  • Be prepared to show your GMU ID on exam days.

Grading Scale

Grade	A+	A	A-	B+	B	B-	C+	C	C-	D	F
lower bound	98	92	90	88	82	80	78	72	70	60	↓

Policies

• Challenging of grades (GTAs for in-class assignments; Professor for exams or any assignment with automated grading) must occur within a week of the grade being posted to Canvas.
• Use email when asking about grading or logistical issues; use the Piazza board when asking course content or assignment-related questions.
• Make-up exams are only offered in response to university-accepted exceptional circumstances.
• Late work is not accepted without prior arrangement or university-accepted emergency situation; computer failure is not considered an excuse for lost code, so please take steps to make backups.
• Classwork (assignments and exams) is individual unless otherwise specified; sharing of work will be considered a violation of Academic Standards and will be reported as such (see below).

Academic Standards (formerly 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 Academic Standards Code and the CS Department Honor Code, and will typically result in failing the class.

Generative AIs (including but not limited to ChatGPT, Copilot, or Gemini) should not be used to assist in completing any assignments or assessments. Any assignment solved with the help of such an AI, or derived from an AI-based solution, would be in violation of the Academic Standards Code. If using an IDE which enables generative AI by default, the AI must be disabled while working on assignments for this class. Much like using calculators to perform arithmetic, you would not learn the skill if you used a tool to solve a problem for you, and you should not present work as your own unless you have done it yourself. AIs add an additional concern, which is that they may very confidently present incorrect answers as true, which is not helpful to your learning experience.

Some kinds of participation in third-party online study sites violate the GMU Academic Standards 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.

GMU upholds the Academic Standards of honesty, acknowledgement, and uniqueness of work. Please respect the importance of upholding the Academic Standards 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.

Student responsibility: Students are responsible for understanding how these general expectations regarding academic standards apply to this course and any assignment or exam they participate in; students should ask their instructor for clarification on any aspect that is not clear to them.

Privacy statement

All course materials posted to Canvas or other course site are private to this class. By the Family Educational Rights and Privacy Act (FERPA), a federal law which governs the disclosure of educational records for eligible students, the professor and TAs cannot share academic documents with a different student, and any materials that identify specific students (via their name, voice, or image) must not be shared with anyone not enrolled in this class. Students must use their GMU email account to receive communications related to this class.

Student responsibility: Students are responsible for checking their GMU email regularly for course-related information, and/or ensuring that GMU email messages are forwarded to an account they do check.

Disability accomodations

Disability Services at George Mason University is committed to providing 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.

Student responsibility: Students are responsible for registering with Disability Services and communicating about their approved accommodations with their instructor in advance of any relevant class meeting, assignment, or exam.

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

Student opportunity: If you prefer to speak to someone confidentially, please contact one of Mason’s confidential employees in Student Support and Advocacy (SSAC), Counseling and Psychological Services (CAPS), Student Health Services (SHS), and/or the Office of the University Ombudsperson.

Schedule (subject to change)

Week	Date	Topic	Assignments/Notes
Week 1	Aug 24-30	Introduction, Chapter 1
		Analysis Basics, Chapter 1 🅐
Week 2	Aug 31-Sep 6	No Class (Monday)	Labor Day
		Asymptotic Analysis, Chapter 2 🅐
Week 3	Sep 7-13		Quiz 1 (open Mon-Tue)
		Divide and Conquer; Master Method, Chapters 3, 4 🅣🅐	Coding 1 assigned (Friday)
Week 4	Sep 14-20		Assessment 1 (Analysis); Quiz 2 (open Mon-Tue)
		Sorting, Chapter 5 🅟
Week 5	Sep 21-27		Assessment 2 (D & C Algs); Quiz 3 (open Mon-Tue)
		Graphs; Graph Algorithms, Chapters 7, 8 🅟	Coding 1 due (Friday)
Week 6	Sep 28-Oct 4		Assessment 3 (Sorting); Quiz 4 (open Mon-Tue)
		Dijkstra's Algorithm; Greedy Algorithms, Chapters 9, 10, 13 🅟🅣	Coding 2 assigned (Friday)
Week 7	Oct 5-11		Assessment 4 (Graph Algs); Quiz 5 (open Mon-Tue)
		Minimum Spanning Trees, Chapter 15 🅟
Week 8	Oct 12-18		Assessment 5 (Greedy Algs); Quiz 6 (open Mon-Tue)
		Huffman Codes, Chapter 14 🅟	Coding 2 due (Friday)
Week 9	Oct 19-25	Miterm (Monday)
		Dynamic Programming, Chapters 16, 17 🅟🅣	Coding 3 assigned (Friday)
Week 10	Oct 26-Nov 1		Quiz 7 (open Mon-Tue)
		Shortest Path, Chapter 18 🅟
Week 11	Nov 2-8		Assessment 6 (DP Algs); Quiz 8 (open Mon-Tue)
		Max Flow, Supplementary Materials 🅟	Coding 3 due (Friday); Coding 4 assigned (Friday)
Week 12	Nov 9-15		Assessment 7 (Shortest Path); Quiz 9 (open Mon-Tue)
		Flow Networks, Supplementary Materials 🅣🅟
Week 13	Nov 16-22		Assessment 8 (Max Flow); Quiz 10 (open Mon-Tue)
		Hard Problems (P vs NP), Chapters 22, 23 🅟🅐	Coding 4 due (Friday); Coding 5 assigned (Friday)
Week 14	Nov 23-29
		No Class (Wednesday)	Thanksgiving Recess
Week 15	Nov 30-Dec 6		Assessment 9 (Flow Nets); Quiz 11 (open Mon-Tue)
		Randomized Algorithms 🅣	Coding 5 due (Friday)
Week 16	Dec 7-13	Last day of class (Monday)	Assessment 10 (Hard Probs)
Exam Week	Dec 10-16	Final Exam Section 004	1:30pm-4:15pm, Monday, Dec 15

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