Discrete Math for Computer Science
Discrete mathematics is fundamental to Computer Science in much the same way that calculus is fundamental to the physical sciences. At the machine level, computers as we know them now are essentially discrete structures, where information and instructions are encoded in strings of binary digits. Writing any computer program requires precise and logical thinking; logic is essential for verifying program correctness. Recursion is a powerful concept in computing as well as in mathematics: it is used for implementing algorithms, specifying syntax, and working with data structures. Graphs and trees represent relations among data, both theoretically and practically (e.g. data structures, social networks, the Internet).
Additionally, discrete mathematics creates a framework for examining and improving the efficiency of algorithms. Besides its crucial role in the foundations of computer science, discrete mathematics also plays important roles in natural sciences, engineering, operations research, the social sciences, and most fields of mathematics.
Course Format: Classes and tests will be in person. Course material and information will be posted in eClass
Textbook: Kenneth H. Rosen, Discrete Mathematics and Its Applications (8th Edition). 2025: McGraw Hill.)
Official Course Calendar Description: Introduction to abstraction. Use and development of precise formulations of mathematical ideas. An informal introduction to logic; introduction to naïve set theory; induction; relations and functions; big O-notation; recursive definitions, recurrence relations and their solutions; graphs and trees.
Expanded Course Description from Supplemental Calendar
The purpose of this course is to develop students' ability to think abstractly, develop and use precise formulations of mathematical ideas, and prepare students for more advanced topics in computer science and mathematics. Discrete mathematics is the study of discrete structures like sets, functions, relations, graphs, and trees, and the relationships between them. An example of a problem solved using discrete mathematics is “What is the shortest path between two cities using a transportation system?” Solving this problem involves constructing a graph, and cannot be simply solved by applying a formula. Discrete mathematics will challenge you and make you think in ways that other courses have not, because one of the primary goals of this course is to teach mathematical reasoning and problem-solving, rather than giving formulae and a set of skills to apply these formulae.
Course-level learning objectives
The purpose of this course is to develop students' ability to think abstractly, develop and use precise formulations of mathematical ideas, and prepare students for more advanced topics in computer science and mathematics.
Discrete mathematics is the study of discrete structures like sets, functions, relations, graphs, and trees, and the relationships between them. Discrete mathematics will challenge you and make you think in ways that other courses have not because one of the primary goals of this course is to teach mathematical reasoning and problem-solving, rather than giving formulae and a set of skills to apply these formulae.
Upon successful completion of this course, students should be able to correctly apply:
- Apply logical arguments, definitions, set identities, and mathematical induction to write valid proofs using a variety of methods;
- Compare functions in terms of their structure and growth by proving properties of given functions (e.g., one-to-one, onto, big-O, big-Omega, big-Theta);
- Prove properties of recursively defined structures and solve counting problems and recurrence relations; and
- Analyze graphs to determine the properties they have (e.g., type of graph, connectivity, Euler and Hamilton paths and circuits
Learning in this course:
In this course, your learning experience is multifaceted, encompassing attendance in class, reading the textbook, and completing exercises. Aside from the mandatory homework, you'll also be provided with a list of extra exercises posted in eClass, consisting of odd-numbered exercises from the text. The solutions and brief explanations for these exercises can be found at the back of the text and are similar to the questions you'll encounter on tests and exams.
To maximize your learning potential, it's essential to read the sections covered in each class before attending. Although you may not comprehend everything on your first reading, it will aid your understanding of the course content.
For a conventional 3-credit class like this, plan to devote approximately 6 hours outside of class time per week to the course for preparation, readings, practice problems, and homework assignments. It's crucial to keep pace with the course material, as falling behind can be detrimental and challenging to catch up
