Difference between revisions of "CS 2051"

From Georgia Tech Student Wiki
(Created CS 2051 page)
 
m (Added course name to display title)
 
(14 intermediate revisions by 4 users not shown)
Line 1: Line 1:
  +
{{DISPLAYTITLE:CS 2051 - Honors Introduction to Discrete Mathematics}}
−
== Overview ==
  
  +
[[Category:Courses|^CS^CS]]
−
CS 2051 is the honors equivalent of [[CS 2050]]. CS 2050 and CS 2051 are both math classes in the CS department.
 
   
  +
'''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]].
−
==== Topics List ====
  
  +
−
The difference between CS 2050 and CS 2051 is that CS 2051 covers a few additional topics, covers the CS 2050 topics in slightly more depth, moves at a faster pace, and has significantly harder homework assignments. In Spring 2021, the topics list for CS 2051 was (with the CS 2051 exclusive topics marked with an *):
  
  +
== 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.
   
 
# Propositions and Propositional Logic
  
# Propositions and Propositional Logic
  +
## Propositions and Truth Values
  +
## Propositional Operations
  +
## Truth Tables
  +
## Implications
  +
## DeMorgan's Laws
  +
## Propositional Functions
  +
## Quantifications
  +
## Arguments
 
# Methods of Proof
  
# Methods of Proof
  +
## Direct Proof
−
# Set Theory and Cardinality
  
  +
## Contraposition
  +
## Contradiction
  +
## Construction (Direct and Indirect)
  +
## Equivalency Proofs
  +
## Casework
  +
# Set Theory
  +
## Sets
  +
## Subsets
  +
## Venn Diagrams
  +
## Finite Cardinality
  +
## Power Sets
  +
## Cartesian Products
  +
## Set Operations
  +
## Functions
  +
## Infinite Cardinality (*)
  +
## Countability (*)
  +
## Cantor's Theorem (*)
 
# Relations (*)
  
# Relations (*)
  +
## Binary Relations
  +
## Properties of Relations
  +
## Equivalence Relations
  +
## Equivalence Classes and Partitions
  +
## Functions as Relations
 
# Induction and Recursion
  
# Induction and Recursion
  +
## Weak Induction
  +
## Strong Induction
  +
## Induction and Recursive Problems
 
# Algorithms and Big-O Analysis
  
# Algorithms and Big-O Analysis
  +
## Formal Definition of Big-O, Big-Omega, and Big-Theta
  +
## Properties of Big-O
  +
## Basic Algorithm Analysis
  +
## Solving for Algorithm Runtime (*)
  +
## Recurrence Relations (*)
 
# Introductory Number Theory
  
# Introductory Number Theory
  +
## Partition of the Integers & Quotient Spaces (*)
−
# Number Theoretic Algorithms (*)
  
  +
## Congruence Classes
−
# RSA (*)
  
  +
## Fast Exponentiation (*)
−
# Counting, Permutations, and Combinations
  
  +
## GCD and Euclid's Algorithm
  +
## Modular Inverse
  +
## Linear Congruences (*)
  +
## The Extended Euclidean Algorithm and Bezout's Theorem (*)
  +
## Systems of Linear Congruences (*)
  +
## The Chinese Remainder Theorem (*)
  +
## Divisibility
  +
## Fermat's Last Theorem (*)
  +
## Intro to Diophantine Equations (*)
  +
## The Totient Function (*)
  +
## Euler's Theorem (*)
  +
## Primality Testing (*)
  +
# The RSA Cryptosystem (*)
  +
## Introduction to Cryptosystems
  +
## The RSA Algorithm
  +
## Encoding and Decoding
  +
# Counting and Combinatorics
  +
## Standard Counting Rules
  +
## Principle of Inclusion-Exclusion
  +
## The Pigeonhole Principle
  +
## Generalized Pigeonhole Principle (*)
  +
## Permutations and Combinations
  +
## The Binomial Theorem
  +
## Counting with Repetition (*)
  +
# A selection of more advanced topics (varies by semester)
   
  +
== Prerequisite Knowledge ==
−
==== 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]]).
 
   
  +
=== Programming ===
−
== Current Registration Information ==
  
  +
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.)
  
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 [https://www.dropbox.com/s/yadp1zyvmfbbzvx/CS%20three%20year%20course%20outline%20Sp%2022%20to%20Sp%2023.pdf?dl=0 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 ===
  
=== Prerequisites ===
Line 26: Line 118:
   
 
=== Equivalent Courses ===
  
=== Equivalent Courses ===
−
CS 2050 is the equivalent non-honors section of discrete math. It gives equivalent credit.
 +
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 ==
   
−
=== Majors that Require this Class ===
 +
==== Spring 2021 ====
  +
The advanced topics in Spring 2021 included:
   
  +
* Recursive Counting and Recurrence Relations
−
* Computer Science (pick between CS 2050 and CS 2051)
  
  +
* Generating Functions

Latest revision as of 15:15, 12 May 2022


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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

Programming[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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

Equivalent Courses[edit | edit source]

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[edit | edit source]

Spring 2021[edit | edit source]

The advanced topics in Spring 2021 included:

  • Recursive Counting and Recurrence Relations
  • Generating Functions
Retrieved from "https://gt-student-wiki.org/mediawiki/index.php?title=CS_2051&oldid=1863"