Building the mathematical foundations behind computer science, algorithms, proofs, graph theory, probability, and logical reasoning.
About
CS 1800 introduces the abstract discrete structures that underpin computing. Per the Fall 2025 syllabus, the course begins with mathematical notation, logic, and sets, then progresses through proof techniques, combinatorics, probability, mathematical induction, graph theory, and asymptotic notation — building familiarity with structures used throughout computer science.
Topics including logic, predicate logic, sets, proof techniques, induction, counting, probability, graph theory, and asymptotic analysis appear far beyond the classroom. They shape how software engineers reason about correctness, how data scientists model uncertainty, and how algorithms are evaluated for efficiency at scale. This course established the rigorous vocabulary I still use when approaching technical problems.
Skills
Course Topics
Propositional logic, truth tables, logical equivalence, and predicate logic formed the language of rigorous reasoning. I learned to construct direct proofs, proofs by contradiction and contraposition, and arguments grounded in formal structure rather than intuition alone.
Sets, combinatorics, and probability provided the counting tools behind algorithm analysis. From the product and sum rules to permutations, combinations, and conditional probability, this block built fluency in quantifying discrete possibilities.
Graphs modeled relationships between entities — vertices, edges, trees, traversals, and connectivity. Asymptotic analysis tied these structures to efficiency, asking how algorithms scale as inputs grow.
Learning Outcomes
Evaluating statements systematically using propositional and predicate logic.
Building valid arguments through direct proof, contradiction, and induction.
Questioning assumptions and identifying gaps in informal reasoning.
Defining structures and functions inductively and reasoning about base cases.
Connecting discrete math to how programs are analyzed and designed.
Representing networks, dependencies, and relationships as graphs.
Quantifying uncertainty with joint, conditional, and expected values.
Expressing ideas with precise notation, definitions, and proof structure.
Translating word problems into formal structures before solving them.
Understanding the mathematical backbone behind computing disciplines.
Identifying recurring structures across logic, counting, and graph problems.
Preferring rigor over guesswork when correctness must be guaranteed.
Course Structure
Following the syllabus topic sequence, CS 1800 moved from formal logic through sets and counting, into probability and induction, and concluded with graph theory and asymptotic analysis.
Resources
Reflection
CS 1800 fundamentally changed how I approach technical problems. Before this course, I could follow instructions and write code — but I had not yet learned to think rigorously about whether a solution was actually correct. Discrete Structures pushed me to slow down, define terms precisely, and prove claims instead of relying on intuition alone.
That shift matters for everything that comes next: CS 2500, Algorithms, Data Structures, Machine Learning, Software Engineering, and Data Science. Understanding why an algorithm works — not just how to implement it — is the difference between writing code and reasoning like a computer scientist. That foundation started here.
Interesting Facts
PageRank models the web as a graph — ranking pages by link structure and connectivity.
Shortest-path and traversal algorithms on weighted graphs power GPS routing.
Graph theory explains communities, influence, and how information spreads online.
Modular arithmetic, primes, and discrete structures secure modern encryption.
Probability and combinatorics underpin Bayesian models, search, and decision making.
Relations, sets, and formal logic structure queries, schemas, and integrity constraints.
Counting and probability drive collaborative filtering and ranking predictions.
Graphs model routers, paths, and flow — optimizing how data moves across systems.