CSCI 2014 - Discrete Structures of Computer Science

1. EFFICIENCY OF ALGORITHMS real-valued functions and their graphs Big-O, Big-Omega, Big-Theta notation efficiency of various sorting algorithms divide and conquer algorithms
2. FUNCTIONS: definition one-to-one, onto and inverse functions pigeonhole principle composition of functions
3. LOGIC: propositional logic valid and invalid arguments predicates and quantified statement application to digital circuits
4. MATHEMATICAL INDUCTION: sequences weak induction strong induction application: elements of program correctness
5. METHODS OF PROOF: direct proof indirect proof proof by contradiction proof by cases and generalization some classic proofs infinity of primes irrationality of 2 Pythagorean theorem
6. RECURSION: recursively defined sequences solving recurrence relations by iteration
7. SET THEORY: basic definitions properties of sets partitions and power sets relation to Boolean algebra classic problems related to set theory Russells paradox Turings halting problem
8. TREES AND GRAPHS: terminology paths and circuits tree traversals spanning trees

1. demonstrate the validity of a set relationship using an algebraic argument.
2. demonstrate the validity of a set relationship using an element argument.
3. demonstrate if 2 logical statements are equivalent or not.
4. derive the logical negation of statements.
5. explain what constitutes a valid argument.
6. use mathematical induction to prove properties of sequences.
7. prove basic properties of numbers using direct proofs, indirect proofs and proofs by contradiction.
8. describe what makes a relation between the elements of 2 sets a function.
9. calculate the degree of any vertex of a network graph, and the total degree of the graph.
10. define what a (network) graph is and identify its constituent parts (vertices, edges, loops, etc).
11. define what characterizes a sequence as a recursive sequence.
12. derive an explicit (i.e., non-recursive) formula for a recursively defined sequence using the technique of iteration.
13. describe how the computing efficiency of an algorithm can be calculated.
14. describe what it means for one function to be of the same order as another (with respect to its rate of growth).
15. describe what properties make a function 1-to-1 and/or onto.
16. determine if a given walk within a graph is a path and/or circuit.
17. determine if a given walk within a graph is an Euler path and/or Hamiltonian circuit.

Courses and Registration