CS 212 --- Fall 2024
Mathematical Foundations of Computer Science Part 1:
Discrete Mathematics for Computer Science
Basic info
Course description: This course explores fundamental concepts and tools in discrete mathematics, with an emphasis on their applications to computer science. Topics include formal logic and proof-writing techniques (such as contrapositive, contradiction, and induction), as well as key mathematical structures like sets, functions, relations, and graphs. The course provides an introduction to combinatorics and graph theory, through the lens of computer science.
Prerequisites: CS 110 or CS 111.
Instructors: Miklos Z. Racz, Anjali Agarwal
Lecture time and location: TuTh 9:30 am - 10:50 am, 217 Fisk Hall
Office hours: MZR: Th 11:00 am - 1:00 pm, Mudd 3108; AA: Tu 4:00 - 6:00 pm, Mudd 3108
Teaching Assistants (TAs):
- Shuwen Chai, office hours: F 3:00 - 5:00 pm, Mudd 3rd Floor Counter
- Anant Shah, office hours: W 4:00 - 6:00 pm, Mudd 3532
- Aryaman Chawla, office hours: W 11 am - 1 pm, Mudd 3rd Floor Counter
- Kevin Fan, office hours: Tu 5 - 7 pm, Mudd 3rd Floor Counter
- Sirie He, office hours: Tu 12 - 2 pm, Mudd 3532
- Ryan Liu, office hours: Th 5 - 7 pm, Mudd First Floor Lobby
- Sophia Pi, office hours: W 6 - 8 pm, Mudd 3108
- Nicholas Qiu, office hours: Th 5 - 7 pm, Mudd First Floor Lobby
- Andre Shportko, office hours: M 10 am - 12 pm, Tech MG51
- William Tong, office hours: Tu 2 - 3 pm, Mudd 3rd Floor Counter, and Th 2 - 3 pm, Mudd 3532
- Harry Wang, office hours: W 10 am - 12 pm, University Library 4722
- Helen Zhu, office hours: M 3:30 - 5:30 pm, Mudd 3rd Floor Counter
Grading and course policies
Grading: There will be homework problem sets throughout the quarter (approximately weekly), graded in-class participation, as well as a midterm and a final exam. Your final score is a combination of your performance in these, with the following breakdown:
- HW 50%
- midterm 20%
- final exam 25%
- in-class participation 5%
Final info: Thursday, December 12, 12 - 2 pm, 217 Fisk Hall
Homework and collaboration policy:
Submission clarity: You may choose to hand-write your homework solutions, or typeset them. If you choose to typeset, we recommend LaTeX. If you choose to hand-write your solutions, please be considerate of the grader and write neatly. Unreadable solutions will not be graded.
Late days and drop-one rule: To help you more flexibly manage deadlines, we give you three late days for the quarter to use on homework assignments. A late day allows you to turn in an assignment up to 24 hours later without penalty. At most one late day may be used per assignment.
In addition, your lowest homework score will be dropped.
Late days are meant to automatically handle minor issues; the drop-one rule is meant for a one-off larger issue (e.g., emergency) or a busy week. If you are experiencing a major issue, especially one outside of your control (such as illness or injury), please contact us as soon as possible.
Collaboration: You should first attempt to solve homework problems on your own. You are encouraged to discuss any remaining difficulties in study groups of two to four people. However, you must write up the solutions on your own and you must never read or copy the solutions of other students.
Outside resources: You may use books or online resources to help solve homework problems, but you must always credit all such sources in your writeup, and you must never copy material verbatim.
Advice: do the homeworks! The best way to understand the material is to solve many problems. In particular, the homeworks are designed to help you learn the material along the way.
Resources and Tools
Textbook: There is no required textbook for this course. The following textbook is the suggested reference book:
-
Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science, 2018.
Gradescope: Gradescope is the tool used in this course to turn in completed assignments. You may resubmit as many times as you wish before the deadline. Assignment grades and staff feedback will be visible in Gradescope. You can access Gradescope through a tab on the course Canvas page.
Discussion: The course has an Ed Discussion page. Think of this as a Q&A wiki for the course, use it for questions and discussions. Students are encouraged to answer one another's questions on the message board as well. You should receive an email invitation to join within the first week of class.
Poll Everywhere: In-class participation will be measured through Poll Everywhere. You should receive an email invitation to join within the first week of class. You can access Poll Everywhere through a tab on the course Canvas page.
Panopto Recordings: Class recordings will be made available. Please keep in mind that watching these is not a substitute for attending lectures. You can access Panopto through a tab on the course Canvas page.
Schedule
Classes begin on Tuesday, September 24. An approximate schedule for the course:
- Lectures 1 -- 5 (Sep 24 -- Oct 8): Formal Logic and Proofs. Includes propositional logic, predicate logic and quantifiers, existence proofs, direct proofs, contrapositive proofs, proof by cases, proof by contradiction.
- Lectures 6 -- 10 (Oct 10 -- 24): Sets, Functions, Relations. Includes a study of fundamental objects in mathematics, including sets, functions, and relations. In addition, includes a study of two additional proof techniques: induction and strong induction.
- Oct 29: Midterm exam
- Lectures 11 -- 16 (Oct 31 -- Nov 19): Graphs. A study of graph theory, including connectivity, trees, cycles, graph coloring, bipartite graphs, matchings, and more.
- Lectures 17 -- 20 (Nov 21 -- Dec 5): Combinatorics and Probability. Includes counting, permutations and combinations, pigeonhole principle, binomial theorem, probability, Bayes' Rule, random variables, and expectation.
Back to Teaching Home