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:
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