dwills@ad.umuc.edu

Class web site: http://sensei.ad.umuc.edu/dwills/cmis160/

PREREQUISITE: MATH 107

Not that there's much algebra in 160... It's not that kind of boring math.
The prereq is to ensure that students have some math maturity.

COURSE DESCRIPTION: An introduction to discrete mathematical techniques for solving problems in the field of computing. Basic principles from areas such as sets, relations and functions, logic, graph theory and recursion are examined. Topics are selected on the basis of their applicability to typical problems in computer languages and systems, databases, networking, and software engineering.

Several reasons to take this course: you'll learn part of the vocabulary and culture of every computer scientist, you will learn some useful techniques and concepts, you will learn some of the canonical examples that come up in various other courses, and finally, and probably most important, it's required for the degree (for the above reasons, of course).

COURSE OBJECTIVES: On successful completion of this course, you will be able to:

- perform basic operations with sets
- classify functions according to various properties
- work with important special functions
- classify relations according to various properties
- work with important special relations
- translate between informal (English) and formal expressions of statements
- work with logical connectives and quantifiers, alone or in combination
- recognize valid and invalid logical reasoning
- construct proofs of simple mathematical statements
- work with sequences, including recursively defined sequences
- use sum and product notations
- construct simple proofs using mathematical induction
- classify graphs and trees according to various properties
- work with paths and circuits in graphs
- find a minimal spanning tree of a weighted graph
- represent a formal language using regular expressions
- construct finite-state automata and determine what operations they perform

REQUIRED TEXTBOOK:

__Discrete Mathematics with Applications__ 3rd Ed. by Epp.

Note: the textbook is very good. You should study it a lot. You will
form a solid understanding of the foundations of computation.
Unfortuneately, it's designed for a two semester course for math
majors, not computing majors, so there's excessive amount of
mathematical material in it. This being a one term CMIS course, we
will concentrate on the aspects that are relevant and applicable to
programming and computing. We will learn the definitions and be able
to do examples, we will not be proving theorems etc.

EVALUATION: Your final grade will be based on four quizzes and a cumulative final exam.

Quizzes 60% Final Exam 30% Attendance/Participation 10%

According to the UMUCAD catalog the grade of 'A' means 'Outstanding', 'B' is 'Good', 'C' is 'Satisfactory'. Grades are curved, based on the class average. There is no fixed grading of 90-100 is an A, etc. Significantly above the average is A-ish, above the average or maybe just above or at the average is B-ish, etc.

Week Reading ---- ------- Week 1 1.1 Logic: statements, connectives, truth tables. 1.1: 6-51 Module 2.I ABC 1.4 Digital logic circuits. 1.4: 1-23 26-29 31 34 Module 2.I F Week 2 1.5 Binary and hexadecimal numbers, adder circuit. 1.5: 1-36 38-47 Quiz 1 Week 3 3 misc: even 127-8, prime 138-9, Fermat 138, rational 141-2, divisibility 148 unique factorization 153-4 div/mod 157-8, floor/ceiling 165-6, Euclidean GCD 192-6 3.2: 1-7 3.3: 1-3 6 7 10 11 34 3.4: 7-11 3.5: 1-4 3.8: 9-18 Week 4 4.1 Sequences: summation, factorial, arrays. 4.1: 1-6 8-16 18-44 63-68 Module 3.I 4.2 sum of sequences 221-2, 225. 4.2: 19-28 Module 3.II A 5.1 Set theory: Venn diagrams, subset, union, intersection, Cartesian product, formal languages empty set, power set, partitions. 5.1: 1-12 14 18-27 29 30 5.2 pages 278-9,285 Module 1.I Quiz 2 Week 5 6.1 Counting and probability. 6.1: 1-19 6.2 Possibility trees, multiplication rule, permutations 6.2: 1-25 29-36 6.3 Addition rule. 6.3: 1-17 23 26-28 6.4 Combinations (thru page 337). 6.4: 1-5 Quiz 3 Week 6 7.1 functions: Hamming, Boolean. 7.1: 1-6 13 14 25-30 Module 1.II 12.1 Formal languages, regular expressions. 12.1: 1-39 Module 4.I 12.2 Finite state automata. 12.2: 1-47 Module 4.II Week 7 11.1 Graphs. 11.1: 1-29 36 Module 5.I ABCF Quiz 4 Week 8 11.2 Paths and circuits. 11.2: 1-6 8 9 12-24 36 Module 5.I DE 11.5 Trees. 11.5: 1-4 7-21 30 32-50 Module 5.II ABC Exam