It is assumed that students read the scheduled sections prior to each lecture.
1.3 Software Requirements (click to expand)
For All Classes:
You will need a computer for this class with some modern operating system
capable of running a Java compiler (for Java 1.9 or higher, the latest
stable version of OpenJDK is preferred). Remember that lab computers are
also available on campus, see campus resources below.
Be prepared to move online if the semester requires it for any reason
(see online class requirements below).
You are required to have regular, reliable access to a computer
with an updated operating system (recommended: Windows 10 or Mac
OSX 10.13 or higher) and a stable broadband Internet connection
(cable modem, DSL, satellite broadband, etc., with a consistent
1.5 Mbps [megabits per second] download speed or higher.
You are required to have a device with a functional camera
1.4 Course Communication(click to expand)
The majority of course information and material will be available on
(access code is "banana"), including TA contacts information
and office hours. Grades and other private information will be on
You MUST read Piazza for clarifications and homework information/updates.
Most questions should be answerable in and before/after class,
however instructors and GTAs for this course will have some
additional office hours for questions and course help.
Announcements will often be made at the beginning of class.
If you miss the start of class, make sure to get the
information from a friend or colleague in the class.
No sharing answers or course material unless you've been
authorized to do so by your instructor. See section on
the Honor Code below.
Please email course staff only for personal issues
such as grading disputes, medical situations, etc.
Please do not e-mail course staff about homework
problems, use office hours and the before/after class time.
2. Course Description
2.1 Course Topics (click to expand)
Analyzes computational resources for important problem types by alternative
algorithms and their associated data structures, using mathematically rigorous
techniques. Specific algorithms analyzed and improved.
Tentative topics to be covered include:
Introductory and Review Material (ch 1-3)
Algorithm Design and Advanced Analysis Techniques (thoughout, but esp. in ch 2 and 4-6)
Basic and Advanced Graph Algorithms (thoughout, but esp. in ch 3, 6, and 7)
NP-completeness and Computational Intractability (ch 8-9)
Advanced Topics (Time Permitting): Randomized Algorithms, Approximation Algorithms, PSPACE, etc.
See the schedule (on Piazza) for a more detailed topics list.
2.2 Prerequisites (click to expand)
Formal Prerequisites: C or better in: CS310, CS330, and Math 125.
More generally, you will be using knowledge introduced in a Formal Methods and Models course (such as CS 330) and by entension Discrete Mathematics (in Math 125). You also need knowledge gained from a Data Structures course (such as CS 310) and by extension multiple programming courses (such as CS 112 and CS 211).
Below is a more detailed (but not exhaustive) list of topics which may "come back to haunt you":
Formal Methods and Models - Logic, Proofs, Mathematical Induction, Program Verification, Computability
Data Structures - Big-O Analysis, Lists, Stacks, Queues, Sets and Maps, Hash Tables, Trees, Search Trees, Priority Queues, Heaps, Graphs
2.3 Course Outcomes (click to expand)
At the end of the course, students will be able to:
Understand classical problems in Computer Science
Understand classical algorithm design and analysis strategies
Analyze the computability of a problem
Design and analyze new algorithms to solve a computational problem
3.1 Assessment and Grades (click to expand)
Extra Credit Opportunities
EC HW 12
EC on Exams
The following will be applied without rounding:
A+ (>= 98.0%) A (>= 92.0%) A– (>= 90.0%)
B+ (>= 88.0%) B (>= 82.0%) B– (>= 80.0%)
C+ (>= 78.0%) C (>= 72.0%) C– (>= 70.0%)
D (>= 60.0%)
F (< 60.0%)
There will be no make-up assignments or unannounced
extra-credit opportunities at the end of the semester;
your grade should be a measure of your semester-long progress.
3.2 Homework(click to expand)
Homework will be submitted to Blackboard. Turning in the wrong
files will result in a zero (no exceptions). Any code for programming
projects that does not compile, specifically on Java 1.9,
will receive a zero (no exceptions, even if it is a
"small fix"). It is your responsibility to verify your submissions.
Blackboard being unavailable is not an excuse for turning in a
late assignment; in the rare situation that the website is somehow
unavailable or giving an error, you MUST email your submission to
your TA (and CC your professor) before the deadline, otherwise
it will be considered late. Catastrophic computer failure will not
be cause for an extension. Use a backup service to back up your work!
Homework is considered individual unless otherwise
authorized by your instructor. Therefore no sharing of code
or solutons, and no discussion of problem solutions is
allowed with anyone except the TAs or the instructor. You may
not use the internet to find, develop, or solicit help for
code, assignments, or any other individual work.
It is your responsibility to lock your computers with
a password, to not post your work to websites like Pastebin
that are publicly accessible, to guard your USB drives and
computers, to not upload your files to someone else's
computer, etc. You will be liable for any access gained to
Homework must be submitted on time and extensions require
exceptional circumstances (as judged by the instructor) and must be
arranged in advance. Extensions are never given on or after
the due day unless you have a university-accepted emergency.
GTAs cannot approve late submissions or extensions. Normal obligations
such as family or friend events, vacations, or other classes are not
exceptional circumstances (unless hospitals are involved).
If you need an extension or miss a due date because of a
university-accepted emergency (such as being taken to the
hospital), you must notify your instructor within 24 hours
to make arrangements. You will be asked to provide documentation
of the emergency and your involvement. Failure to follow these
policies will result in a zero.
Instructors may elect to "exempt" a missed homework
rather than give an extension under certain circumstances. In this case, the
other homework in the same sub-category will gain more weight.
Missing a homework due date for any non-university-accepted reason (such as
not paying attention to when the due date is), will result in a zero.
3.3 Exams (click to expand)
Exams are closed book/notes unless otherwise specified by
All tests and exams are considered individual
efforts. Resources available during exams will be specified by
the instructor on a exam-by-exam basis. Student exams will be
manually and automatically assessed for cheating.
All students must have their GMU identification available on
testing days (and will be required to show a photo ID as part
of the exam process). Alternative photo IDs options
may be required if your GMU ID is unavailable or unreadable.
Early or late/makeup exams require exceptional circumstances
(as judged by the instructor) and must be arranged in advance.
Vacation plans are not exceptional circumstances.
If you miss an exam due to a university-accepted excused
absence (such as an illness or car accident the day and time of
the exam), notify your instructor within 24 hours of your absence
to make arrangements for a makeup, and bring approved documentation
with you when you take the make-up exam.
Failure to follow these policies will result in a zero. Instructors may
elect to replace a missed midterm with some (or all) of the final
exam grade rather than offering a makeup exam under certain circumstances.
Missing an exam due for any non-university-accepted reason (such as
not paying attention to when the exam is), will result in a zero.
3.4 Contesting Grades (click to expand)
If you feel points have been incorrectly deducted, contact the
grader. For homework, that is your GTA. For exams, that is your
Contesting of grades on any/all submissions must be requested
within one week of receiving the grade (on BlackBoard). No grade
changes will be considered subsequent to that deadline or
subsequent to the final exam (whichever comes first).
4. University and Departmental Policies
4.1 Honor Code (click to expand)
All students are expected to abide by the GMU Honor Code.
This policy is rigorously enforced. Cheating will be prosecuted
and result in a notification of the Honor Committee as outlined
in the GMU Honor Code. Sharing,
collaboration, or looking at any code or algorithm for the
homework that is not your own, including resources
from Internet, is considered cheating.
The computer science department has an CS Honor Code
Policies that you are subject to particularly for our
course. The document helps you to understand how GMU honor code
applies to programming and CS, what constitutes cheating in the
CS setting. It clarifies some scenarios that are unique to our
sorts of assignments. Make sure you read and familiarize
yourself with these rules.
The CS Department take the honor code quite seriously. Any attempts at
copying or sharing code, solutions, algorithms, or other violations of the
honor code simply will not be tolerated. We use automated
software to flag suspicious cases, and then review them to find
the cases that must be submitted to the Office of Academic
Integrity. The penalty for cheating will always be far worse
than a zero grade, to ensure it's not worth taking the chance.
Confirmed cases of cheating almost always translate into course
4.2 Privacy (click to expand)
All course materials posted to Blackboard or other course sites
are private; 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.
Video recordings of class meetings that include audio or visual
information from other students are private and must not be shared.
Live Video Conference Meetings (e.g. Collaborate or Zoom) that
include audio or visual information from other students must be
viewed privately and not shared with others.
4.3 Non-Discrimination and Inclusiveness (click to expand)
We are committed to providing an educational environment free from any discrimination
on the basis of race, color, religion, national origin, sex, disability,
veteran status, sexual orientation, gender identity, gender expression,
age, marital status, pregnancy status, or genetic information. If you
feel there has been a violation of the University's policies on this,
please contact GMU's Office of Compliance, Diversity, and Ethics
Gender identity and pronoun use: If you wish, please share your name and gender
pronouns with us and we will attempt use them to address you in class and via email.
You can address any instructor as "Prof. [LAST NAME]" in email and verbally if you
aren't sure of their personal preferences.
4.4 Sexual Harassment, Sexual Misconduct, and Interpersonal Violence (click to expand)
All faculty members are designated "Responsible Employees", and are required
to report all disclosures of sexual assault, interpersonal violence, and
stalking to Mason’s Title IX Coordinator per university policy 1412.
If you wish to speak with someone confidentially, please contact the Student
Support and Advocacy Center (703-380-1434) or Counseling and Psychological
Services (703-993-2380). You may also seek assistance from Mason’s Title IX
Coordinator (703-993-8730; firstname.lastname@example.org).
5. Campus Resources
5.1 Disability Services (click to expand)
Due to the size of the class, individual instructors and graders cannot
support students with injuries or disabilities on an ad-hoc basis.
We ask that all accommodations for such conditions be arranged through
GMU's Office of Disability Services.
Students with a physical or learning disability which is already
documented with the Office of Disability
Services) should speak with the instructor ASAP to discuss
their approved accommodations. Even if you don't know whether you plan
on utilizing the accommodations for any assignment/test, you need to
make sure you and your instructor are working together from the beginning
of the semester to ensure your success in the class.
Students with a physical or learning disability who have not yet registered
with the Office of Disability Services
should register with that office as soon as possible. Even if you don't
know whether you'll need to utilize the accommodations, it's in your
best interest to prepare ahead of time and get your condition documented
as accommodations are not retroactive. They have a quick and easy registration
process. All you need is documentation for your condition.
The Office of Disability Services
also handles services for many temporary disabilities (for example,
if you break your arm, they can arrange note taking services).
Please contact them if you discover any sudden impairment that affects
your ability to function in class and/or on your projects. They have
a quick and easy registration process. All you need is documentation
for your condition.