CSCI 2200: Foundations of Computer Science (FOCS), Spring 2024
Personnel
- Instructor:
Rado Ivanov
(ivanor@rpi.edu), Lally 309
- Course Coordinator: Shianne Hulbert (hulbes@rpi.edu), Aemos Eaton 125
- TAs: Michael Cleversley (clevem), Sharmishtha Dutta (duttas), Shuhang Tan (tans5), Yuchen Zhang (zhangy94)
- Mentors: Wilde Chu (chuw7), Mohamed Lashuel (lashum), Michael Lyga (lygam), David Wang (wangd14), Ilan Beyen (beyeni), Emma Huntington (huntie), Matthew Hurtado (hurtam), Jun Kim (kimj43), Zain Magdon-Ismail (magdoz2), Junyi Wu (wuj18), Justin Ottesen (ottesj), Shimu Pan (pans), Eric Scheer (scheee2)
- Office hours:
- Rado: M 1-2pm, W 4-5pm, F 9-10am (Lally 309)
- Yuchen: M 2-3pm (Aemos Eaton 127)
- Shuhang: M 3-4pm (Aemos Eaton 127)
- Michael: T 10-11am (Aemos Eaton 127)
- Sharmishtha: T 2-3pm (Aemos Eaton 127)
- Mentors: by appointment
Class Time and Location
- Class: MTh 10am-noon (Sage 3303)
- Recitations:
- W 10am-11am (Aemos Eaton 215)
- W 11am-noon (Aemos Eaton 215)
- W noon-1pm (Aemos Eaton 215)
- W 1pm-2pm (Aemos Eaton 215)
- W 2pm-3pm (Aemos Eaton 215)
- W 3pm-4pm (Low 3039)
- Quiz 1: 8-9am, Feb. 7 (DCC 308)
- if you need special accommodations, please go to DCC 236
- Quiz 2: 8-9am, Mar. 27 (DCC 308)
- if you need special accommodations, please go to DCC 236
- Quiz 3: 8-9am, Apr. 17 (DCC 308)
- if you need special accommodations, please go to DCC 236
- Midterm Exam: 8-10am, Feb. 28 (DCC 308)
- if you need special accommodations, please go to DCC 236
- Final Exam: 8-11am, Apr. 29 (DCC 308)
- if you need special accommodations, please go to DCC 330
Course Description
This is a theory course in discrete mathematics and the theory of computation. Every computer scientist should have a solid grasp of these concepts in order to be able to develop fast algorithms, design large systems and be able to reason about program correctness.
Discrete Mathematics
(i) Proofs, especially induction (ii) Sums and Recurrences (iii) Graphs (iv) Counting and Probability
Theory of Computing
(v) What is computing? (vi) How to compute? (vii) What can we compute? (viii) How fast? (P vs. NP)
Textbook
Discrete Mathematics and Computing, M. Magdon-Ismail.
The textbook is required. Reading the book is complementary to lecture material – you are also required to work through all exercises in addition to attending the lectures. Homework problems will be assigned from the book as well.
Grading
- Quizzes: 30% (10% each)
- Midterm Exam: 30%
- Final Exam: 30%
- Homeworks: 10%
- Bonus in-class pop quizzes: 2%
Useful Resources
Announcements
It is the student's responsibility to be aware of and understand all announcements made in the lectures.
Assignments
Unless otherwise noted, each assignment will be due
at midnight Tuesday. All assignments must be submitted through Submitty. You are expected to work alone on all assignments - please check the syllabus for a clarification of what constitutes academic dishonesty.
- . Deadline: 11:59pm, Tuesday, Jan. 16.
- . Deadline: 11:59pm, Tuesday, Jan. 23.
- . Deadline: 11:59pm, Tuesday, Jan. 30.
- . Deadline: 11:59pm, Tuesday, Feb. 13.
- . Deadline: 11:59pm, Tuesday, Feb. 20.
- . Deadline: 11:59pm, Tuesday, Mar. 12.
- . Deadline: 11:59pm, Tuesday, Mar. 19.
- . Deadline: 11:59pm, Tuesday, Apr. 2.
- . Deadline: 11:59pm, Tuesday, Apr. 9.
- . Deadline: 11:59pm, Tuesday, Apr. 23.
Past Quizzes and Exams
- Quiz 1 -- [, ], [, ]
- Quiz 2 -- [, ], [, ]
- Quiz 3 -- [, ], [, ]
- Midterm -- [, ], [, ]
- Final -- [, ], [, ]
Quizzes and Exams
- Feb. 7 -- ,
- Feb. 28 -- ,
- Mar. 27 -- ,
- Apr. 17 -- ,
- Apr. 29 -- ,
Lectures
- Jan. 8 -- Course Overview []
- Jan. 11 -- Discrete Objects []
- Jan. 18 -- Precise Statements []
- Jan. 22 -- Proofs []
- Jan. 25 -- Induction []
- Jan. 29 -- Strong Induction []
- Feb. 1 -- Recursion []
- Feb. 5 -- Proofs with Recursion []
- Feb. 8 -- Sums and Asymptotics []
- Feb. 12 -- Number Theory []
- Feb. 15 -- Graphs []
- Feb. 20 -- Matching and Coloring []
- Feb. 22 -- Counting []
- Feb. 26 -- Advanced Counting []
- Feb. 29 -- Probability []
- Mar. 11 -- Conditional Probability []
- Mar. 14 -- Independence []
- Mar. 18 -- Random Variables []
- Mar. 21 -- Expected Value []
- Mar. 25 -- Expected Value of a Sum []
- Mar. 28 -- Deviations from the Mean []
- Apr. 1 -- Infinity []
- Apr. 4 -- Languages []
- Apr. 8 -- Deterministic Finite Automata []
- Apr. 11 -- Context-Free Grammars []
- Apr. 15 -- Turing Machines []
- Apr. 18 -- Unsolvable Problems []
- Apr. 22 -- Efficiency []