CSU200 Discrete Structures (4 SH)

Introduces the mathematical structures and methods that form the foundation of computer science. Discusses structures such as sets, tuples, sequences, lists, and possibly trees or graphs. Discusses the counting techniques and arguments needed to estimate the size of sets, the growth of functions, and the space-time complexity of algorithms. Introduces basic logic and principles of proof including proof by induction.

Prerequisites: high school algebra and MTH U121 Precalculus or equivalent

There are many usable books available. Kenneth H. Rosen, "Discrete Mathematics and its applications, Fifth Edition", McGraw Hill, 2003 (ISBN 0-07-242434-6) This book covers far more material than we can get to in one semester. Sherwood Washburn, Thomas Marlowe, and Charles T. Ryan, "Discrete Mathemetics," Addison Wesley Longman, Inc, 2000.

Algebraic Abstraction Working with formulas that contain literals Sequences Summation notation Formulas for finite sums of arithmetic and geometric sequences Recursive Sequences (optional) Sets Finite and infinite sets, R, Q, Z, N Set builder notation Subsets Set operations Venn diagrams Strings sets of strings (optional) Integers division algorithm prime factorization gcd, lcm Euclidean algorithm Extended Euclidean algorithm (optional) Modular arithmetic binary, octal and hex representations of integers twos-complement (optional) Functions Functions on finite sets and on R, Q, Z, N. Particular attention to 2^x and log2(x) n!, floor, ceil Graphing functions on graph paper and using Excel Introduction to growth of functions and big-O Onto and one-to-one functions, bijections (optional) Relations (optional) Algorithms (optional) a couple of sorting and searching algorithms as inspiration for looking at growth of functions Counting permutations and combinations binomial coefficients pigeonhole principle generating permutations and combinations (optional) Logic logical operators, not, and, or and De Morgan’s Laws What we mean by A==>B, B==>A, ~B==>~A, A iff B Predicates and quantifiers Proofs Students will be introduced to proofs when they arise naturally as other topics are covered, including: Proof by direct argument Proof by induction, weak (and possibly strong) Counterexamples Examples that provide existence proofs And possibly: proving the contrapositive proof by contradiction proof of a logical equivalence circle of implications Additional Optional Material Discrete Probability ..................................... Some of the following, if time permits: Recurrences Relations Graphs Trees

Upon completion of this course, a student should be able to : use algebraic expressions with one or more variables describe sets using set operations and set-builder notation do arithmetic modulo n be able to compute gcd and lcm of pairs of integers or of integers expressed abstractly (e.g. gcd(pq^2,qr^3) find the prime factors of integers like 3300 or 10!. give decimal, binary, octal, hexadecimal representations of positive do simple combinatorics problems using permutations and combinations compute values of, graph, and use 2^x and log2(x), n!, floor, ciel make mathematical statements using logical notation including: not, and, or, implies, iff, for all, there exists. A student should have been introduced to big-O a variety of proofs

The course outcomes will be measured and verified by: Some combination of On-line homework Written homework Work completed in class Two to six quizzes or hour exams Final Exam

This course provides the mathematical foundation for many courses in computer and information science including, data structures, algorithms, theory of computation, compilers, computer security, and operating systems.