CSE 20210

Source: A. Chaudhary

Course Outcomes

At the end of the course, students will be able to demonstrate the following abilities.   The level for each ability (since, e.g., there is a wide range of proofs, from the obvious to extremely hard, that can satisfy Outcome 2 below)  is made more concrete by a example exercise from the textbook ?Discrete Mathematics and Its Applications? by Kenneth H. Rosen, Sixth Edition, published by McGraw Hill.

1.   Translate statements in propositional and predicate logic to English and vice versa; and determine logical equivalences using truth tables and standard equivalences.  Examples: Sec 1.2 44, Sec 1.4 37.
2.   Verify if an argument or proof is correct, as well as create proofs or find counterexamples for conjectures on integers, rationals, and irrationals using common forms such as direct, indirect, contradiction, and existence.  Examples: Sec 1.7 24, 44.
3.   Use set operations to prove set identities, as well as identify different types of functions: injective, surjective, and bijective.  Find sums of arithmetic and geometric progressions and determine if a set is countable or otherwise.  Examples: Sec 2.3 72,  Sec 2.4 41.
4.   Determine if a function has the same order as another, as in O, ?, and ?; and determine the time complexity of simple algorithms.  Use Euclid?s algorithm to determine the greatest common divisor of two integers, and the Chinese Remainder Theorem to solve a system of linear congruences.  Examples: Sec 3.2 36, Sec 3.3 25,  Sec 3.7 16.
5.   Construct proofs using induction and specify mathematical objects using recursive definitions.  Examples: Sec 4.2 19,  Sec 4.3 54.
6.   Use the pigeonhole principle, count number of permutations and combinations satisfying given criteria, model counting problems with recurrence relations, and use inclusion-exclusion for counting.  Examples: Sec 5.2 10,  Sec 5.5 44,  Sec 7.6 8.
7.   Determine the probability of simple events, verify if two events are independent, and use the linearity of expectation.  Examples: Sec 6.4 6, 34.
8.   Determine if a relation is reflexive, symmetric, or transitive, and its closure with respect to some property, as well as identify equivalence classes, partially ordered sets, and various kinds of elements in a lattice.  Examples: Sec 8.1 56, Sec 8.4 24, Sec 8.6 43.
9.   Use the handshaking theorem for graphs, determine if two graphs are isomorphic, find Euler and Hamilton paths and circuits, and relate the number of leaves in a tree to its height.  Examples: Sec 9.3 64,    Sec 9.4 28,  Sec 10.1 30.

Direct Measures

Each of the above numbered outcomes was measured using questions in graded homework assignments (H), quizzes (Q), mid-semester exams (M), and final exam (F) as follows (based on the last completed offering in Fall 2005):

H1 1-6; H2 1-17; Q1 1-3; M1 1-3; F 1
H3 1-8; H6 1-3, 5-9; Q2 1-2; Q3 1; M1 4, 8; M2 1; F 16, 19
H3 9-14; H4 1-9; H6 10-12;  M1 5, 6; M2 2; F 2, 18
H4 10-13; H5 1-14; H6 5; M1 7, 9; F 3
H7 1-7; H8 1-10; Q3 2-3; M2 3, 7, 8; F 4
H8 11-16; H9 1-8; H11 1-10; M2 4, 5; F 5, 7, 15, 17, 20
H9 9-12; H10 1-9; M2 6; F 6
H11 1-2; H12 1-11; F 8-10, 14
H12 12-16; H13 1-9; F 11-13

Mapping of Outcomes to Computer Science Program Outcomes

1.   a, c, f, j.
2.   a, c, f, j.
3.   a, c, j. 
4.   a, b, c, f, i, j.
5.   a, c, j.
6.   a, b, c, i, j.
7.   a, b, c, f, i, j.
8.   a, b, i, j.
9.   a, b, c, f, i, j.


Mapping of Outcomes to Computer Engineering Program Outcomes

1.   1, 2, 5, 7, 11.
2.   1, 7.
3.   1, 5, 11.
4.   1, 2, 3, 5, 7, 11
5.   1, 5, 11
6.   1, 2, 3, 5, 11.
7.   1, 2, 3, 5, 7, 11.
8.   1, 3, 5, 7, 11.
9.   1, 2, 3, 5, 7, 11.