This is a proof-based course in theoretical computer science.
The course requires the following:
Knowledge of ALGORITHMS at a basic undergraduate level (COMPSCI 330 or equivalent)
Knowledge of DISCRETE MATHEMATICS at a basic undergraduate level (COMPSCI 230 or equivalent)
Knowledge of PROBABILITY and LINEAR ALGEBRA at a basic undergraduate level
Mathematical maturity commensurate with someone who has taken and done well in undergraduate proof-based mathematical courses
There will be 4 homework assignments during the course. Each homework assignment will account for 5% of the course grade. Homework assignments will be submitted on Gradescope, accessed via Canvas. When submitting to Gradescope, you must upload the pdf and match the pages to the problems in the assignment. You are expected to type your answers using LaTeX, although using other typesetting software is also permitted. Only typed pdf submissions will be accepted. (No handwritten scanned submissions, please.)
In general, late submissions will not be accepted. If you need extra time because of a valid reason, please email the instructor for prior permission to submit late.
You are allowed to work in groups for homework with the following caveats:
you must write your own solutions in your own words, i.e., you can discuss with others but not copy from others
you are not allowed to discuss homework problems when explicitly prohibited on the homework assignment
you must state the names of all students that you discussed the homework with on your submission
you are not allowed to consult in groups of more than 3 students (including you)
you need to follow the policies stated here
The use of LLMs such as chatGPT, Gemini, etc. for homework is strictly prohibited.
There will be two in class exams. These will account for 25% of the grade each. Roughly, the first exam will cover the first half of lectures, and the second exam will cover the second half of lectures.
Students have to do a project in groups of 2-4. Some proposed project topics and ideas will be published on the course website during the course.
At the end of the semester, students have to prepare a project report and presentation.
This will account for 25% of the course grade.
Each student is expected to participate in homework grading. Class participation and grading will account for 5% of the course grade.
If you need to ask a question, either administrative or related to the course material, the best place to do so is in the course website on the Ed discussion forum that can be accessed from the course Canvas page. The discussion forum will be monitored and questions will be answered as soon as possible. If you have an urgent question or request, please email the TA and instructor in addition to asking it on Ed.