Assistants: (see Piazza for hours and contact info)
GTA: Shiva Ghaemi (sghaemi; 11am-1pm Mon, 4456 Engineering)
GTA: Preksha Shukla (pshukla8; 2-4pm Wed, 4456 Engineering)
UTA: David Godin
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 (e.g. Java).
A scanner, camera, or digital drawing tool to use to prepare digital uploads of homework.
If a class cannot be held in person, be prepared to attend the lecture online, which would require a computer with reliable Internet, web browser, and audio
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 quizzes.
GradeScope to for homework turn-in/feedback and exam feedback
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
| Grade | A+ | A | A- | B+ | B | B- | C+ | C | C- | D | F |
|---|---|---|---|---|---|---|---|---|---|---|---|
| max | ↑ | 97 | 91 | 89 | 87 | 81 | 79 | 77 | 71 | 69 | 59 |
| min | 98 | 92 | 90 | 88 | 82 | 80 | 78 | 72 | 70 | 60 | ↓ |
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.
Generative AIs such as ChatGPT, Copilot, or Gemini should not be used to assist in completing assignments. Any assignment solved with the help of such an AI, or derived from an AI-based solution, would be in violation of the Honor Code. 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 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 Canvas 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 Canvas 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).
Schedule (subject to change)
| Week | Date | Topic | Assignments/Notes |
|---|---|---|---|
| Week 1 | Aug 25-31 | Introduction, Chapter 1 | |
| Analysis Basics, Chapter 1 🅐 | |||
| Week 2 | Sep 1-7 | Asymptotic Analysis, Chapter 2 🅐 | |
| HW 1 assigned (Thursday) | |||
| Week 3 | Sep 8-14 | Divide and Conquer; Master Method, Chapters 3, 4 🅣🅐 | Quiz 1 (open Mon-Tue) |
| Week 4 | Sep 15-21 | Sorting 🅟, Chapter 5 | Quiz 2 (open Mon-Tue) |
| HW 1 latest turn-in; HW 2 assigned (Thursday) | |||
| Week 5 | Sep 22-28 | Graphs; Graph Algorithms, Chapters 7, 8 🅟 | Quiz 3 (open Mon-Tue) |
| Week 6 | Sep 29-Oct 5 | Dijkstra's Algorithm; Greedy Algorithms, Chapters 9, 10, 13 🅟🅣 | Quiz 4 (open Mon-Tue) |
| HW 2 latest turn-in; HW 3 assigned (Thursday) | |||
| Week 7 | Oct 6-12 | Huffman Codes; Minimum Spanning Trees, Chapters 14, 15 🅟 | Quiz 5 (open Mon-Tue) |
| Week 8 | Oct 13-19 | Dynamic Programming, Chapter 16 🅣 | |
| Miterm 1 (Thursday) | Coding 1 assigned (Thursday) | ||
| Week 9 | Oct 20-26 | Dynamic Programming; Shortest Path, Chapters 16-18 🅟 | Quiz 6 (open Mon-Tue) |
| HW 3 latest turn-in; HW 4 assigned (Thursday) | |||
| Week 10 | Oct 27-Nov 2 | Shortest Path; Max Flow, Chapter 18 + Supplementary Materials 🅟 | Quiz 7 (open Mon-Tue) |
| Week 11 | Nov 3-9 | No class Tuesday | Coding 1 latest turn-in (Monday, 11/4); Election Day |
| Max Flow, Supplementary Materials 🅟 | HW 4 latest turn-in; HW 5 assigned (Thursday) | ||
| Week 12 | Nov 10-16 | Quiz 8 (open Mon-Tue) | |
| Nov 10 | Flow Networks, Supplementary Materials 🅣 | ||
| Week 13 | Nov 17-23 | Hard Problems (P vs NP), Chapters 19, 23 🅟🅐 | Quiz 9 (open Mon-Tue) |
| HW 5 latest turn-in; HW 6 assigned; Coding 2 assigned (Thursday) | |||
| Week 14 | Nov 24-30 | Hard Problems (P vs NP), Chapters 22, 23 🅟🅐 | Quiz 10 (open Mon-Tue) |
| No class Thursday | Thanksgiving Recess | ||
| Week 15 | Dec 1-7 | Randomized Algorithms; Special Topics (Internet) 🅣🅟 | Quiz 11 (open Mon-Tue) |
| HW 6 latest turn-in (Thursday); Coding 2 latest turn-in (Monday, 12/9) | |||
| Exam Week | Dec 11-18 | Final Exam Section 003 | 1:30-4:15pm, Thursday, Dec 12 |
| Final Exam Section 002 | 1:30-4:15pm, Tuesday, Dec 17 |
🅐 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.