## Discrete Mathematics CS 275

Topics in Discrete Mathematics aimed at application in Computer Science. Fundamental principles: set theory, induction, relations, functions, Boolean algebra. Techniques of counting: permutations, combinations, recurrences, algorithms to generate them. Introduction to graphs and trees.

### Correlated Learning Outcomes

• AL-02 Estimate time and space complexities for a given algorithm using Big-O notation. [Evaluating]
• AL-03 Contrast standard complexity classes. [Analyzing]
• AL-06 Investigate the use of random/pseudo random number generation in cybersecurity applications. [Applying]
• AL-17 Explain why the halting problem has no algorithmic solution. [Understanding]
• AR-02 Analyze alternative formats to represent numerical data. [Analyzing]
• AR-05 Compare different methods for converting numerical data from one format to another. [Analyzing]
• CYB-21 Describe key terms in cryptology, including cryptography, cryptanalysis, cipher, cryptographic algorithm, and public key infrastructure. [Understanding]
• CYB-22 Use a variety of ciphers to encrypt plaintext into ciphertext. [Applying]
• CYB-23 Apply cryptographic hash functions for authentication and data integrity. [Applying]
• CYB-24 Contrast symmetric and asymmetric encryption in relation to securing electronic communications and transactions. [Analyzing]
• DS-01 Explain with examples the basic terminology of functions, relations, and sets. [Understanding]
• DS-02 Perform the operations associated with sets, functions, and relations. [Applying]
• DS-03 Compare practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context. [Analyzing]
• DS-04 Convert logical statements from informal language to propositional and predicate logic expressions. [Understanding]
• DS-05 Apply formal logic proofs and/or informal, but rigorous, logical reasoning to real problems such as predicting the behavior of software or solving problems such as puzzles. [Applying]
• DS-06 Use the rules of inference to construct proofs in propositional and predicate logic. [Applying]
• DS-07 Describe how symbolic logic can be used to model real-life situations or computer applications. [Understanding]
• DS-08 Apply formal methods of symbolic propositional and predicate logic, such as calculating validity of formulae and computing normal forms. [Applying]
• DS-09 Describe the strengths and limitations of propositional and predicate logic. [Understanding]
• DS-10 Outline the basic structure of each proof technique, including direct proof, proof by contradiction, and induction. [Analyzing]
• DS-11 Apply each of the proof techniques (direct proof, proof by contradiction, and induction) correctly in the construction of a sound argument. [Applying]
• DS-12 Deduce the best type of proof for a given problem. [Analyzing]
• DS-13 Explain the parallels between ideas of mathematical and/or structural induction to recursion and recursively defined structures. [Understanding]
• DS-14 Explain the relationship between weak and strong induction and give examples of the appropriate use of each. [Understanding]
• DS-15 Apply counting arguments, including sum and product rules, inclusion-exclusion principle and arithmetic/geometric progressions. [Applying]
• DS-16 Apply the pigeonhole principle in the context of a formal proof. [Applying]
• DS-17 Calculate permutations and combinations of a set, and interpret the meaning in the context of the particular application. [Applying]
• DS-18 Compare real-world applications appropriate to counting formalisms. [Analyzing]
• DS-19 Solve a variety of basic recurrence relations. [Applying]
• DS-20 Analyze a problem to determine underlying recurrence relations. [Analyzing]
• DS-21 Perform computations involving modular arithmetic. [Applying]
• DS-22 Illustrate the basic terminology of graph theory including properties and special cases for each type of graph/tree. [Applying]
• DS-23 Demonstrate different traversal methods for trees and graphs, including pre-, post-, and in-order traversal of trees. [Understanding]
• DS-24 Solve a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system. [Applying]
• DS-25 Implement and use balanced trees and B-trees. [Applying]
• DS-26 Implement graph algorithms. [Applying]
• DS-27 Demonstrate how concepts from graphs and trees appear in data structures, algorithms, proof techniques (structural induction), and counting. [Understanding]
• DS-28 Describe binary search trees and AVL trees. [Understanding]
• DS-29 Explain complexity in the ideal and in the worst-case scenario for both implementations. [Understanding]
• DS-30 Calculate probabilities of events and expectations of random variables for elementary problems. [Applying]
• DS-31 Differentiate between dependent and independent events. [Understanding]
• DS-32 Explain the significance of binomial distribution in probabilities. [Understanding]
• DS-33 Apply Bayes Theorem to determine conditional probabilities in a problem. [Applying]
• DS-34 Apply the tools of probability to solve problems. [Applying]