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)
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
8. Number Theoretic Algorithms (*)
9. RSA (*)
10. Counting, Permutations, and Combinations

How it fits in the Curriculum

CS 2051, like CS 2050 is a required class for all CS, CompE, and CM majors. It is a critical class in the prereq chain for Theory threads (and even Intelligence threads' Theory requirement), being used as prerequisites for for Algorithms (CS 3510) and Applied Combinatorics (MATH 3012), which are both used as prerequisites for Advanced Algorithms (CS 4540), and Automata and Complexity Theory (CS 4510).

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.)

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.

Majors that Require this Class

• Computer Science (pick between CS 2050 and CS 2051)