As a computer scientist, your goal will be to choose or design, then implement, efficient algorithms that accomplish the goals for which they were designed, with certainty. The aim of FOCS is to give you the tools necessary to establish certainty about your algorithms: that they do what they claim to.
As such, this course introduces the fundamental mathematics used in computer science for the purpose of ensuring such certainty: discrete mathematics and the theory of computation.
- Discrete mathematics
- This is the study of objects that can be counted—including proofs, sums and recurrences, graphs, counting, and probability—this toolbox is essential for showing algorithms do as we claim.
- Theory of Computation
- This branch of CS helps delineate what kinds of problems can even be hoped to be solved, and how efficiently. Understanding this helps you to avoid tilting at windmills.
See the course syllabus for more details.
Lectures will be held synchronously, then uploaded to the course's Youtube playlist.
Lectures: Tue/Fri 10:10am-12pm ET; WebEx (see Piazza for the link)
Course Discussions: Piazza
Instructor: Alex Gittens (gittea)
TAs: Yitian Liu (liuy57), Owen Xie (xieo), Shuting Yang (yangs21)
Undergraduate mentors: Haoyu He (heh3), Qifan Jiang (jiangq3), Jacob Libsman (libsmj), Kaiwen Min (mink3), David Qian (qiand), Joshua Wu (wuj14)
Course Coordinator: Shianne Hulbert (hulbes)
If you need testing accomodations (e.g. a shift or extension in your test time), please contact Shianne. She will also be sending emails to ensure that you are informed about your test time accomodations near to the tests and quizzes.Office Hours:
TA office hours will be held through WebEx: the WebEx link for each TA is of the form
|Tuesday noon-1pm and Friday 1-2pm ET||Zoom||Alex Gittens|
|Thursday 8-10am ET||WebEx Meetings||Yitian Liu|
|Tuesday 4-6pm ET||WebEx Meetings||Owen Xie|
|Monday 8-10am ET||WebEx Meetings||Shuting Yang|
|Sunday 2-6pm ET||Submitty office hours queue + WebEx||Rotating: one TA and two mentors. See Pizza post @27 for instructions|
The recitations will be held in a hybrid format to facilitate mathematical communication (drawing diagrams, writing proofs, etc. is much easier in person). Because of Institute policy, if you choose to attend in person, you will be turned away if there are already more than 30 students present. If you do not attend in person, you can watch prerecorded videos of the TAs working through the recitation problems on the course's Youtube playlist.
|Wed 10:10-11pm ET||Darrin 308||Owen Xie|
|Wed 11:15-12:05pm ET||Darrin 308||Owen Xie|
|Wed 12:20-1:10pm ET||Darrin 308||Yitian Liu|
|Wed 1:25-2:15pm ET||Darrin 308||Yitian Liu|
|Wed 4:45-5:35pm ET||Darrin 308||Shuting Yang|
- Course Syllabus
- Important Dates
- Homeworks and Exams
- HOMEWORK SUBMISSION LINK (pdf only, 1MB limit)
- Solutions to DMC Pop Quizzes and Exercises
- DMC Problems
Announcements: It is the student's responsibility to be aware of and understand all announcements made in the lectures.