CS 173 - Discrete Structures

* Note: My knowledge surrounding CS173 is primarily based on the “old” version of CS173 (Professor Fleck’s content). The information in this article may be unaligned with the new section (Professor Cedre). Corrections adjusting for this bias are greatly appreciated. - Yanni

This is the first theory class in the core CS(+X) curriculum, comprising of in-person lectures, problem sets, weekly exams (called examlets), and a final exam. Please refer to the syllabus (Section A/B and Section C) for the most up-to-date information on the course’s structure.

Topics Covered

• Proofs and proof techniques
• Elementary number theory
• Graphs
• Functions
• Elementary set theory

Resources

Each class hosts office hours. Please refer to the latest iteration of the course website for exact times.

Developer’s Commentary

Why is this course important?

A comment we’ve heard about this class is that this class’ content seems disjoint from computer science- there’s no programming at all!

Computer Science is not software engineering; in fact, software engineering is only a small part of the Computer Science discipline. Theoretical Computer Science (TCS), which roots itself in Mathematics, is an equally important part of the field, and as such, we must also develop a solid foundation in Mathematics. This course is the start of said foundation.

From a less definition-chase-y perspective, this class is important because it teaches you how to rigorously apply logic and prove a claim. In Computer Science roles, we often need to make guarantees about an aspect of a system (correctness, reliability, etc). As such, we must make accurate and precise conclusions. These conclusions, are derived from certain known primitive statements and orchestrated through logic. A solid understanding on how to construct a rigorous proof will be immensely useful for many future classes, especially those that are more theoretical in nature.

Please learn how to write a proof.

In line with the previous section, one of the most important things to take out of this class is the ability to construct a rigorous proof. Unfortunately, historically, the class does not put a very heavy emphasis on this, and makes completing this course without developing this skill very possible. For the sake of your future self, do not skip out on this.

Misc.

This class is colloquially considered the CS version of MATH 314/MATH 347. Material from that class is generally applicable here.

Related Classes

If the math side of this class interests you, consider taking more mathematics classes!

• MATH 444, MATH 447, MATH 424- These are the undergraduate (real) analysis classes offered, listed in increasing difficulty.
• MATH 417, MATH 427- There are the undergraduate abstract algebra classes offered, listed in increasing difficulty.
• MATH 453- Number Theory.

Proficiency Exam

This course does offer a proficiency exam. For exam logistics, please refer to the official CS proficiency exam website.