## Discrete Structures ITCS2012

This course provides an introduction to the foundations of discrete mathematics as they apply to computer science, and focuses on providing a solid theoretical foundation for further work. Topics include logic, set algebra, equivalence relations and partitions, functions, mathematical induction, cardinality, recurrence relations, basic combinatorial methods, and trees and graphs; with an emphasis on applications in computer science.

### Correlated Learning Outcomes

• AL-01 Analyze best, average, and worst-case behaviors of an algorithm. [Analyzing]
• AL-02 Estimate time and space complexities for a given algorithm using Big-O notation. [Evaluating]
• AL-03 Contrast standard complexity classes. [Analyzing]
• AL-04 Analyze the performances of an algorithm with various input sizes. [Analyzing]
• AL-16 Describe the concept of finite state machines. [Understanding]
• AL-17 Explain why the halting problem has no algorithmic solution. [Understanding]
• 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]