CS 2051 - Honors Introduction to Discrete Mathematics

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. It is immediately succeeded by MATH 3012.

Workload

Unlike its non-honors counterpart, CS 2051 is more in the style of 3000-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 assess 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 Proofs
   6. Casework
3. Set Theory
   1. Sets
   2. Subsets
   3. Venn Diagrams
   4. Finite Cardinality
   5. Power Sets
   6. Cartesian Products
   7. Set Operations
   8. Functions
   9. Infinite Cardinality (*)
   10. Countability (*)
   11. Cantor's Theorem (*)
4. Relations (*)
   1. 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. Induction and Recursive Problems
6. Algorithms and Big-O Analysis
   1. Formal Definition of Big-O, Big-Omega, and Big-Theta
   2. Properties of Big-O
   3. Basic Algorithm Analysis
   4. Solving for Algorithm Runtime (*)
   5. Recurrence Relations (*)
7. Introductory Number Theory
   1. Partition of the Integers & Quotient Spaces (*)
   2. Congruence Classes
   3. Fast Exponentiation (*)
   4. GCD and Euclid's Algorithm
   5. Modular Inverse
   6. Linear Congruences (*)
   7. The Extended Euclidean Algorithm and Bezout's Theorem (*)
   8. Systems of Linear Congruences (*)
   9. The Chinese Remainder Theorem (*)
   10. Divisibility
   11. Fermat's Last Theorem (*)
   12. Intro to Diophantine Equations (*)
   13. The Totient Function (*)
   14. Euler's Theorem (*)
   15. Primality Testing (*)
8. The RSA Cryptosystem (*)
   1. Introduction to Cryptosystems
   2. The RSA Algorithm
   3. Encoding and Decoding
9. 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 (*)
10. A selection of more advanced topics (varies by semester)

Prerequisite Knowledge

Programming

Very basic programming exposure is required for this course, as a bit of pseudocode will be written during the algorithms section. However, unlike CS 2050, some algorithms knowledge is also helpful, as runtime analyses of common algorithms like linear search and binary search are performed.

Mathematics

Only basic algebra is required for this course, no calculus is necessary. However, exposure to linear algebra can be useful, especially during the discussion of injective, surjective, and bijective functions, but this is absolutely not required.

No proofs knowledge is also required for this course, even though it is significantly more proofs heavy.

Future Outlook

CS 2051 is an optional advanced version of CS 2050 for CS majors. For those with either the Intelligence or Theory threads, CS 2051 might be a useful alternative to CS 2050 due to the heavy math and proofs nature of those threads (although Intelligence is remarkably lighter on proofs compared to Theory).

Otherwise, like CS 2050, CS 2051 is the start to a major prerequisite chain. CS 2051 acts as a prerequisite for CS majors for MATH 3012, and is one of the prerequisites for CS 3510, both of which are prerequisites for theory classes for both the Intelligence and Theory threads, as well as the Theory Thread's Advanced Math Elective.

CS 2051 is also one of the prerequisites for daring CS majors willing to take MATH 3235 for their probability and statistics option. Do note that CS 2050 will NOT meet this prerequisite.

Registration

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, Spring 2022
• It will be offered next in Spring 2023 (not Fall 2022)

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