## Discrete Structures

3 Cr. (Hrs.:3 Lec.)

Course includes those mathematical topics which will help students in future courses. It refines problem solving skills by providing a vocabulary, structures and techniques for working with problems. Topics include logic, theorem proving, properties of sets, functions, relations and sequences, counting techniques, recursion and graph theory. Prerequisite: (CSCI 112, CSCI 114, CSCI 117 or CSCI 135) and M 171
(1st)

Course generally offered fall (1st) semester.

#### Expectations:

E1. Students are proficient in a programming language and have learned basic error handling, testing and debugging techniques. (Programming Course)

E2. Students are familiar with summation notation, union and intersection of sets, logarithms, exponential functions, and are able to work with abstractions and manipulate formulas. (M 171)

#### Course Outcomes:

R1. Students are able to use propositional and predicate logic to specify and reason about program requirements. (CAC-a; EAC-a, 2)

R2. Students can use inference to prove statements, can distinguish valid from invalid proofs, and know the vocabulary of proofs. (CAC-a; EAC-a, 2)

R3. Students can use mathematical structures such as sets, relations, functions and sequences to reason about problems. (CAC-a; EAC-a, 2)

R4. Students can use graph terminology and theory to reason about problems. (CAC-a; EAC-a, 2)

R5. Students know when induction can be applied and can develop inductive proofs; similarly they know when recursion can be employed and can develop recursive algorithms. Students understand the relation between recursion and induction and can prove the correctness of recursive algorithms using induction. (CAC-a; EAC-a, 2)

R6. Students can use combinatoric approaches to problem-solving and will be able to apply counting arguments to algorithmic design. (CAC-a; EAC-a, 2)