CS 30: Discrete Math in CS
Winter 2024 | 10A hour (TTh 10:10—12:00; F 15:30—16:20) | ECSC 008
Professor Amit Chakrabarti
Home Schedule Assessment Policies

Course Description

This course covers the mathematical foundations of computer science that are not calculus-based. Such mathematics is especially important in computer science, because data is ultimately represented as discrete bits and an algorithm is inherently a series of discrete steps.

We will begin with an overview of mathematical notation and the basic concepts of sets, functions, and relations. We will then study logic, proof techniques, combinatorics (counting), probability, and the beginnings of graph theory. If time permits, we will work in some elementary number theory. A set of guiding examples from computer science will motivate the topics studied.

Learning Objectives

If you do well in this course, by the end of it, you will

  • be able to read mathematical notation and terminology fluently;
  • become comfortable with mathematical thinking that allows you to write clean, logical, proofs;
  • become familiar with a number of discrete structures that are used throughout computer science;
  • achieve a certain clarity of thinking and expression that (as a side effect) enables you to write correct and efficient code more easily.

Administrative Information

Course Staff and Office Hours
Besides the professor (Amit Chakrabarti), we have an experienced team of TAs to support your learning in this course. Details are on the course's Canvas page.
Attendance
In each regular meeting of this class, 40–50% of the time will be spent in a working session, where students will solve 3–4 problems in small groups, each guided by a TA. Since these sessions are a vital part of the learning experience, in-person attendance is a must.
Getting Help
Please use Ed Discussion to ask any questions related to the course and do not use email.
Prerequisites
CS 10 (or equivalent), and
a good high-school mathematics education that you can recall very well.
Textbook
There is no required textbook. In fact, reading a textbook is rather low-priority on the list of study techniques for this course. The best way to learn this subject is by working out lots of problems by yourself and writing up the solutions using pen-and-paper and/or LaTeX. Maintain a good notebook with your own lecture notes and your own written solutions. Treat this evolving notebook, along with any supplementary notes provided by the professor, as your "primary text" for studying.

With that said, here are three textbooks I can recommend as references for further reading. Each book has its strengths (and weaknesses) and each has its own style: I encourage you to read bits of each to figure out which you like best. The answer will differ from one person to another and from one topic to another.