[Page Status: Draft, not finalized yet]
| Sections | Time | Location | Other info |
|---|---|---|---|
| Lecture | Tue and Thu, 5:00PM-6:20PM | Piazza sign-up: https://piazza.com/buffalo/spring2025/cse396 | |
| Recitation 1 | Thu, 8:00AM-8:50AM | Capen 260 | |
| Recitation 2 | Thu, 9:30AM-10:20AM | Baldy 112 | |
| Recitation 3 | Fri, 10:00AM-10:50AM | Capen 260 | |
| Recitation 4 | Fri, 9:00AM-9:50AM | Capen 260 |
(Other than office hours) All questions/requests to the instructor, TAs, and Graders should be sent using Piazza (New Post and select Instructors only if this is a private post), and not via emails (which can be used as a secondary means if Piazza post didn't work).
UB Learns should be used for checking the grades (and doing quizzes) – all other materials such as syllabus, announcements, homeworks, and Q&As, are handled by Piazza only.
| Role | Name | Office Hours |
|---|---|---|
| Instructor | Xiangyu Guo （xiangyug@buffalo.edu） | Davis Hall 318, Tue & Thu, 1:30 PM – 2:30 PM. (Zoom Link) |
| TA | Sean Grzenda (seangrze@buffalo.edu) | Bansal Atrium, 1st floor of Davis Hall, Tue 9 am - 11 am |
| TA | Nicole Ewenike (esomchuk@buffalo.edu) | Baldy 109, Mon & Wed 3 pm - 4 pm |
| Grader | Parag Shah | N/A |
| Grader | Harshit Malpani | N/A |
| Grader | Piyush Gulhane | N/A |
| Grader | Sreeram Melpadi | N/A |
| Grader | Aakash Vydana | N/A |
This will be a mostly mathematical course. The first main objective of the course is to convey those major concepts and results in the theory of computation that guide our thinking about the power of computers and the problems we can solve with them. This includes the entire historical origin of the field in the work of Alan M. Turing, Kurt Gödel, and Cook-Levin. Finite automata, regular expressions, boolean circuits, and idealized programs (if not the Turing machine, think of the Java Virtual Machine) are tools of everyday computing practice. Computational complexity theory asks the fundamental question of how much time, memory, and other computational resources computers need to solve certain problems, and today is relied upon for Internet security.
A second main objective is not as "concrete" as the above-listed syllabus material, but is just as important. Computers are by-nature entirely formal entities---they do precisely what is prescribed in programming languages that are ultimately formal and mathematical. Not just to reason about them, but even to communicate effectively in the field and on the job, one must be able to state assertions precisely and design prototypes concisely. This requires fluency in the underlying mathematical language used to describe problems, computations, and objectives. This course gives valuable training in formal modes of reasoning, analysis, and presentation.
A tentative list of topics are
What is computation:
What is and is not computable:
What is efficient computation.
The outreach of the theory of computation
Course Credits: 4
At the end of this course, each student should be able to apply mathematical foundations, algorithmic principles, and CS theory to model and design systems with comprehension of the tradeoffs involved in design choices.
Students need to have some basic knowledge of
The primary textbook we will use is
[Sipser] Michael Sipser. Introduction to the Theory of Computation. 2nd ed.
[Widgerson] Avi Widgerson. Mathematics and Computation. Princeton University Press. (2019). Available online.
[MM] Cristopher Moore and Stephan Mertens. The Nature of Computation. Oxford University Press (2011)
[Aaronson1]. Scott Aaronson. Quantum Computing Since Democritus. Cambridge University Press (2013)
[LPV] László Lovász, József Pelikán, and Katalin Vesztergombi. Discrete Mathematics: Elementary and Beyond. Springer (2003)
[LLM] Eric Lehman, F. Thomson Leighton, Albert R Meye. Mathematics for Computer Science. Also freely available online.
[Aaronson] Scott Aaronson's website
(==Tentative and subject to change==)
The overall score will be calculated based on the scores from the 3 parts (with weights) as follows:
All Homeworks should be done individually. In each of the 3 parts listed, you will receive a numerical score (normalized to 0~100 range), and the final score is a weighted average of the 3 parts.
The following indicates the grade breakdown which will be used in assigning grades in the course. It is possible that these ranges may be adjusted at the end of the semester to address inconsistencies or hardships that arise.
| Percentage | Letter Grade |
|---|---|
| >= 90 | A |
| 85 ~ 89 | A- |
| 66 ~ 71, 72 ~ 77, 78 ~ 84 | B-, B, B+ |
| 48 ~ 53, 54 ~ 59, 60 ~ 65 | C-, C, C+ |
| 35 ~ 47 | D |
| < 35 | F |
Note: We reserve the right to assign grades based on overall performance, taking into consideration the scores from different assignments and exams. Grades will be “curved” if something systematic happens to make clear that expectations on a problem were misplaced or snow happened or the allocated time was too short. Grades will not be curved/adjusted during the semester.
Your written solution may be either handwritten and scanned, or typeset. Either way, you must produce a PDF that is legible and displays reasonably on a typical PDF reader. You should view your submission after you upload it to make sure that it is not corrupted or malformed. Submissions that are rotated, upside down, or that do not load will not receive credit. Illegible submissions may also lose credit depending on what can be read. Ensure that your final submission contains all pages.
You are responsible for making sure your submission went through successfully.
All assignments are due on the day and time posted.
You can submit an assignment up to 1 days late with a penalty of 20% out of total points. That means you will receive at most 80% of max points even if it’s all correct; 0 points if more than 24 hours late.
Please start all homeworks early! Excuses that you did not have enough time for an assignment will not be considered. Extraordinary circumstances will be considered at the discretion of the instructor (not the TAs), contact the instructor via e-mail if you think these apply to you.
If you miss an exam because of sickness or similar reasons, visit a physician and obtain a note detailing the period during which you were medically incapable of taking the exam.
Notify the instructor immediately via e-mail if you are going to miss an exam before the exam takes place unless medically impossible.
See the instructor as soon as you return to class.
If you miss an exam without a valid excuse, you will receive a zero grade for that exam. No make-up exam will be available unless there is a provable extreme circumstance.
No extra work in the next semester will be given to improve your grade.
Academic integrity is a fundamental university value. Through the honest completion of academic work, students sustain the integrity of the university and of themselves while facilitating the university's imperative for the transmission of knowledge and culture based upon the generation of new and innovative ideas. For more information, please refer to the Graduate Academic Integrity policy.
No tolerance for cheating
Upon your first instance of academic integrity violation, the penalty will be at least a score of 0 for that assignment / exam.
If a second violation occurs, you will get an F and NOT pass the course.
All the violation (whether it’s the first or second instance) will be reported to the Office of Academic Integrity (OAI), the Department, and the School, as required by the University policy Academic Integrity.
Consult the Department and University Statements on Academic Integrity.
Group study/discussion of the assignment at the conceptual level is encouraged, but the submission must be your own work. You must list all people you've discussed with in your submission.
Homework: Homework reports must be written up individually. Use of reference materials in the library or online is allowed, provided that the homework explicitly cites the references used. Note that copying the solutions from online sources or the previous semester is still considered cheating even if you cite the sources.
Students who do share their work with others are as responsible for academic dishonesty as the student receiving the material. Students are not to show work to other students, in class or outside the class. Students are responsible for the security of their work and should ensure that printed copies are not left in accessible places, and that file/directory permissions are set to be unreadable to others.
Excuses such as “I was not sure” or “I did not know” will not be accepted. If you are not sure, ask the TAs and/or the instructor.
Usage of Large Language Model (LLM) services is not allowed unless explicitly stated
Any student may withdraw their submission (homework, lab, projects) at any time, no questions asked, BEFORE any AI violation is discovered.
These bullets should be obvious things not to do (but commonly occur):
Other violations that may not be as obvious:
All materials prepared and/or assigned by me for this course are for the students’ educational benefit. Other than for permitted collaborative work, students may not photograph, record, reproduce, transmit, distribute, upload, sell or exchange course materials, without my prior written permission.
“Course materials” include, but are not limited to, all instructor-prepared and assigned materials, such as lectures; lecture notes; discussion prompts; study aids; tests and assignments; and presentation materials such as PowerPoint slides, Prezi slides, or transparencies; and course packets or handouts. Public distribution of such materials may also constitute copyright infringement in violation of federal or state law.
Violation of this policy may additionally subject a student to a finding of “academic dishonesty” under the Academic Integrity policy and/or disciplinary charges under the Student Code of Conduct.
Accommodations for medical emergencies will be made on a case-by-case basis. Requests for extensions based on medical emergencies must be accompanied by documentation of the emergency from student health services:
http://www.buffalo.edu/studentlife/who-we-are/departments/health.html.
We do NOT accept just the proof of the doctor’s appointment as the accommodation request.
If you have any disability which requires reasonable accommodations to enable you to participate in this course, please contact the Office of Accessibility Resources in 60 Capen Hall, 716-645-2608 and also the instructor of this course during the first week of class. The office will provide you with information and review appropriate arrangements for reasonable accommodations, which can be found on the web at: http://www.buffalo.edu/studentlife/who-we-are/departments/accessibility.html.