CMIS 160 - Discrete Mathematics for Computing
DE Term 4: Apr 9 - Jul 6 2007
Instructor: David Wills
Class web site:
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.
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).
On successful completion of this course, you will be able to:
UMUC's list of objectives can be found at
- 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
- work with logical connectives and quantifiers, alone or in
- 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
Discrete Mathematics with Applications 3rd Ed. by Epp.
Textbooks can be ordered online at the Asia DE Web site,
https://de.asia.umuc.edu/textbookinfo.cfm. Books ordered from any
other source will be at the students own risk. UMUC Asia DE cannot be
responsible for problems encountered when textbooks are ordered from
sources outside of the Asia DE Web site.
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
do examples, we will not be proving theorems etc.
EVALUATION: Your final grade will be based on five quizzes and
a cumulative final exam.
The quizzes will be assigned on a Friday and due Sunday night.
I suggest that you have read the material and worked the suggested
exercises listed in the schedule below before getting the quiz.
The final's questions will be similar to the quizzes, except it will
be closed book closed note and proctored and time limited.
5 Quizzes 50%
Final Exam 50%
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. However, a 90 will
be at least an A, an 80 will be at least a B, etc. In other words,
the scale will most likely be lowered, so maybe 85 and above is the A
etc. This grading is advantageous to you.
All Web courses have a required proctored examination. Students are
responsible for scheduling their appointment to test with the UMUC
Field Rep office where they registered for their classes, normally the
week prior to Proctored Exam Week. For complete instructions regarding
proctored exam procedures go to the Asia DE Web site at
http://de.asia.umuc.edu, and select the "Proctored Exams" link.
Computer-Based Proctored Exams are available only for students testing
at designated UMUC Asia Computer Labs (ask your local UMUC Asia Field
Rep or Computer Lab Monitor if their location is participating), and
only during the scheduled Proctored Exam period. All other students
must be administered paper exams.
CMIS 160 CLASS SCHEDULE.
TERM LENGTH 12 WEEKS (Apr 9 ~ Jul 6)
MANDATORY BREAK (May 23 ~ 27)
PROCTORED EXAM WEEK IS WEEK 10 (Jun 18 ~ 24).
The schedule is approximate and tentative, liable to change due to time
constraints. We will cover the basics, without getting into the
mathematical details, concentrating on what is useful for
Sections or pages, modules, and exercise lists follow.
A book section by itself means the entire section, page numbers mean
those pages only (not the other parts of the section), the modules
are UMUC's online Course Modules accessible through Course Content.
The modules are optional study material; they may or may not help you
learn the material; if you find the textbook's explaination
sufficient, you can skip the modules. The quizzes and exam material
is only from the textbook (the questions in the quizzes and exam are
similar to but not identical to exercise questions in the textbook).
The exercises are not to be turned in or graded. You should work them
to understand the material in the readings.
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
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.3: 1-3 6 7 10 11 34
Week 4 4.1 Sequences: summation, factorial, arrays. 4.1: 1-6 8-16 18-44 63-68
4.2 sum of sequences 221-2, 225. 4.2: 19-28
Module 3.II A
Week 5 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
Week 6 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
Week 7 6.4 Combinations (thru page 337). 6.4: 1-5
Week 8 7.1 functions: Hamming, Boolean. 7.1: 1-6 13 14 25-30
12.1 Formal languages, regular expressions. 12.1: 1-39
12.2 Finite state automata. 12.2: 1-47
Week 9 11.1 Graphs. 11.1: 1-29 36
Module 5.I ABCF
Week 10 Proctored Exam.
Week 11 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
Week 12 Quiz 5
For administrative assistance: contact firstname.lastname@example.org
SDES students should contact: email@example.com
For WebTycho assistance: contact firstname.lastname@example.org.
assistance on Saturdays and Sundays: email@example.com
For proctored exam procedure information, please visit the DE Asia
Website at http://de.asia.umuc.edu and click on 'Proctored Exams'.
For textbook assistance: contact firstname.lastname@example.org
Support for Asian Division Students is also available by phone at
225-3696 (DSN) or 81-42-552-2510 Ext. 5-3696 (international comm.),
Monday - Friday 7:30 a.m. - 4:30 p.m. (JST).
Academic Policies are not course specific and are therefore created
and housed separately from this syllabus. You may access and print
Academic Policies from the Syllabus sub-menu in your classroom.
This syllabus is tentative and subject to change, if
necessary. Changes will be announced with as much notice as possible.
Online Etiquette and Conduct::
- Be polite
- Do not write anything you would be embarrassed to have printed in
the newspaper. Computer messages are not private.
- Keep in mind that any message you write can and may be forwarded to
others. Again, be careful what you write.
- Do not forward personal notes or messages to others or a group
unless you are certain the content is appropriate and you have asked
the author. Do NOT forward chain letters to anyone who is enrolled in
a UMUC course.
- Be aware of how your words may affect others. Since you have no
body language cues, you must be more careful.
- When using quoted material or someone else's idea, include the
citation just as you would in a hard-copy version.
- Reread your message before sending it; edit if necessary.
- NO CHAIN LETTERS.