CS 2051

CS 2051, formally known as Honors Introduction to Discrete Mathematics, is a 3-credit Computer Science class taken as a core requirement for Computer Science majors. It serves as an advanced alternative to the standard discrete math option of CS 2050. It provides a detailed overview of common and uncommon discrete structures used in computing, as well as methods of proof key to the design and analysis of various algorithms.

Class Structure

Workload

Unlike its non-honors counterpart, CS 2051 is more in the style of upper-level math classes. Problem sets are given once a week and generally lean on the moderate to very difficult side. On average these will take north of 3 hours to complete, and collaboration is strongly encouraged.

There are a total of three exams in the class: two midterms and a final. These asses the mastery of material through both multiple choice as well as proof-writing questions.

Like CS 2050, proof writing skill is not expected for students in this class. However, unlike CS 2050, the class does expect its students to master proof writing fairly quickly. Problem sets and exams generally asks for more proofs compared to CS 2050, and more of the class content is dedicated to proving and deriving relationships.

Topics List

As with a typical honors class, CS 2051 goes into a couple extra topics compared to CS 2050. The topics exclusive to CS 2051 are marked with an asterisk.

1. Propositions and Propositional Logic
   1. Propositions and Truth Values
   2. Propositional Operations
   3. Truth Tables
   4. Implications
   5. DeMorgan's Laws
   6. Propositional Functions
   7. Quantifications
   8. Arguments
2. Methods of Proof
   1. Direct Proof
   2. Contraposition
   3. Contradiction
   4. Construction (Direct and Indirect)
   5. Equivalency
   6. Casework
   7. Induction (Weak and Strong)
   8. Combinatorial Proof (*)
3. Set Theory and Cardinality
   1. Fundamentals
   2. Subsets and Power Sets
   3. Finite Cardinality
   4. Cartesian Product
   5. Set Operations
   6. Functions
   7. Injection, Surjection, and Bijection
   8. Infinite Cardinality (*)
   9. Countability (*)
   10. Cantor's Theorem (*)
4. Relations (*)
   1. Standard Binary Relations
   2. Properties of Relations
   3. Equivalence Relations
   4. Equivalence Classes and Partitions
   5. Functions as Relations
5. Induction and Recursion
   1. Weak Induction
   2. Strong Induction
   3. Recursive Induction
6. Algorithms and Big-O Analysis
   1. Big-O, Big-Omega, and Big-Theta
   2. Formal Definition of Big-O
   3. Properties of Big-O
   4. Recursive Algorithms
   5. Algorithm Efficiency
   6. Recurrence Relations (*)
7. Introductory Number Theory
   1. Partition of the Integers & Quotient Spaces (*)
   2. Congruence Classes
   3. GCD
   4. Modular Inverse
   5. Linear Congruences (*)
   6. Systems of Linear Congruences (*)
   7. Divisibility Rules
   8. Intro to Diophantine Equations (*)
   9. The Totient Function (*)
   10. Primality Testing (*)
8. Number Theoretic Algorithms
   1. Fast Exponentiation
   2. Euclid's Algorithm
   3. Fermat's Little Theorem (*)
   4. Bezout's Theorem & the Extended Euclidean Algorithm (*)
   5. Chinese Remainder Theorem (*)
   6. Euler's Theorem (*)
9. The RSA Cryptosystem (*)
   1. Introduction to Cryptosystems
   2. The RSA Algorithm
   3. Encoding and Decoding
10. Counting and Combinatorics
    1. Standard Counting Rules
    2. Principle of Inclusion-Exclusion
    3. The Pigeonhole Principle
    4. Generalized Pigeonhole Principle (*)
    5. Permutations and Combinations
    6. The Binomial Theorem
    7. Counting with Repetition (*)
11. A selection of more advanced topics (varies by semester)

Majors

Majors that take CS 2051 are listed below:

• Computer Science (choice between CS 2050 and 2051)

Future Outlook

CS 2051, like CS 2050, is a critical component of the Theory and Intelligence threads, and in fact, CS 2051 is a decently good class in deciding whether one wants to take the Theory thread. CS 2051 acts as one of the soft prerequisites for MATH 3012 (Applied Combinatorics), as well as a hard prerequisite for for CS 3510 (Algorithm Design), which are both key classes for the Theory thread CS classes: CS 4540 (Advanced Algorithms) and CS 4510 (Automata and Complexity Theory). Furthermore, the proof writing in CS 2051 is an excellent introduction to proof writing in general for future Theory (and even Intelligence) thread classess.

Current Registration Information

CS 2051 is not a linked course, and unlike CS 2050, has no Recitation. Thus, you must only register for the lecture section (marked with an A, B, C, etc.)

Key Registration Footnote:

• Please note that CS 2051 is not offered regularly. Please check the future course plan on the CoC website, found here, to gain a rough idea as to when this course will be offered.
• CS 2051 was last offered in: Fall 2021, Spring 2021, Spring 2020.

Prerequisites

None! CS 2051 can be taken as a first year class.

Equivalent Courses

CS 2050 is the equivalent non-honors section of discrete math. It gives equivalent credit. If you do not like math or do not consider yourself strong at math, it is strongly recommended to take CS 2050.

Resources

Spring 2021

The advanced topics in Spring 2021 included:

• Recursive Counting and Recurrence Relations
• Generating Functions