COSC 311/317 — Discrete Structures
Fall 2014
For
a student of mathematics to hear someone talk about mathematics
does hardly any more good than for a student of swimming to hear
someone talk about swimming. You can’t learn swimming techniques
by having someone tell you where to put your arms and legs; and
you can’t learn to solve problems by having someone tell you to
complete the square or to substitute sin u for y. — Paul Halmos (1975)
Directory
Contact Information
Instructor:
Bruce MacLennan, PhD
Phone: 974-0994
Office: Min H. Kao 550
Hours: MF 1:30–2:30 or make an
appointment
Email: maclennan@eecs.utk.edu
Teaching Assistants:
Kai Wang
Office: Min Kao 210
Hours: M 3:30–5:00 or make an
appointment
Email: kwang11
at vols.utk.edu
Ouassim Bara
Office: Min Kao 338
Hours: T 2:00–3:30 or make an
appointment
Email:
obara at utk.edu
Classes: MWF 2:30–3:20, Min H. Kao 404
This page: http://web.eecs.utk.edu/~mclennan/Classes/311
Catalog Description
Sets, functions, relations, equivalence relations, partial orderings
and proof techniques, especially mathematical induction. Application
of proof techniques to prove correctness of algorithms. Introduction
to basic counting and combinatorics.
Prerequisites
(RE) COSC 160, MAT 142/148. (DE) COSC 140.
Texts
- Ralph P. Grimaldi: Discrete and Combinatorial
Mathematics: An Applied Introduction (5th ed.),
Addison-Wesley, 2003. ISBN-10: 0201726343, ISBN-13:
978-0201726343. New copies are available through Amazon.com
for $135, used copies from $56. You can probably get by with an
older edition, but there are some differences.
- Recommended text on proof techniques: Unless you have
significant prior experience with proving mathematical theorems,
I strongly recommend
that you get a copy of How to
Read and Do Proofs by Daniel Solow (Wiley), ISBN-10:
0470392169, ISBN-13: 978-0470392164. A new copy of the latest
edition costs $66
at Amazon, but you can get used copies of this and earlier
editions for much less (down
to $39 last time I checked). It does not matter which
edition you get.
A similar book is How to
Think Like a Mathematician by Kevin Houston (Cambridge,
2009). It costs $58
new at Amazon, and used copies are available for a few
dollars less. Also good is The
Nuts and Bolts of Proofs by Antonella Cupillari (3rd
ed., Elsevier, 2012). It is $74
new at Amazon, with used copies about the same. Older,
less expensive editions of these books are just as good.
Schedule
- Fundamentals of Logic [Grimaldi, ch. 2]
- Mathematical Proof and Problem Solving [Solow, chs. 2, 4–11,
13]
- Fundamental Principles of Counting [G(rimaldi) 1.1–1.4]
- Set Theory [G 3.1–3.4, 3.8]
- Properties of the Integers and Induction [G 4.1–4.2; Solow 12;
perhaps G 4.3–4.5]
- Relations and Functions [G 5.1–5.5; perhaps 5.6–5.8, 7.1–7.4]
- Supplementary Topics:
- Normal Forms [G 15.1]
- Countable and Uncountable Sets [G App. 3]
- Limitations of Predicate Logic
- Recurrence Relations [G 9, 10.1–10.4]
Topics
Topics
- Propositional logic [G2.1–2.3] (“G2.1” refers to section 2.1
in Grimaldi)
- Logical connectives [G2.1]
- Truth tables [G2.1–2,1]
- Normal forms (conjunctive and disjunctive) [G15.1]
- Validity [G2.1, 2.3]
- Predicate logic [G2.4]
- Universal and existential quantification [G2.4–2.5]
- Modus ponens and modus tollens [G2.3]
- Limitations of predicate logic [G3.8 + additional material]
Learning Outcomes
- Apply formal methods of symbolic propositional and predicate
logic.
- Describe how formal tools of symbolic logic are used to model
real-life situations, including those arising in computing
contexts such as program correctness, database queries, and
algorithms.
- Use formal logic proofs and/or informal but rigorous logical
reasoning to, for example, predict the behavior of software or
to solve problems such as puzzles.
- Describe the importance and limitations of predicate logic.
Topics
- Notions of implication, converse, inverse, contrapositive,
negation, and contradiction [G2.2]
- The structure of mathematical proofs [G2.3; S2, 11, 13]
- Direct proofs [G2.3; S4–7]
- Proof by counterexample [G2.3; S8]
- Proof by contradiction [G2.3; S9–10]
- Mathematical induction [G4.1; S12]
- Recursive mathematical definitions [G4.2]
- Well orderings [G4.1]
Learning Outcomes
- Outline the basic structure of and give examples of each
proof technique described in this unit.
- Discuss which type of proof is best for a given problem.
- Relate the ideas of mathematical induction to recursion and
recursively defined structures.
- Use proof techniques to prove properties about data
structures and algorithms presented in CS140.
- Use proof techniques to prove various properties about
boolean algebra.
Topics
- Functions [G5.2–5.4]
- Relations [G5.1; perhaps G7.1–7.4]
- Sets (Venn diagrams, complements, Cartesian products, power
sets) [G3.1–3.3]
- Pigeonhole principle [G5.5]
- Cardinality and countability [G A3]
Learning Outcomes
- Explain with examples the basic terminology of functions,
relations, and sets.
- Perform the operations associated with sets, functions, and
relations.
- Relate practical examples, such as relational databases, to
the appropriate set, function, or relation model, and interpret
the associated operations and terminology in context.
Topics (Time permitting, to be covered more extensively
in COSC 312). Some of the topics, denoted in italic, are optional
and may be covered at the instructor’s discretion:
- Counting arguments [G1]
- Sum and product rule [G1.1]
- Inclusion-exclusion principle [G3.3]
- Arithmetic and geometric progressions
- The pigeonhole principle [G5.5]
- Permutations and combinations [G1.2–1.3]
- The binomial theorem [G1.3]
- Solving recurrence relations [G9–10]
- The Master theorem
Learning Outcomes
- Compute permutations and combinations of a set, and interpret
the meaning in the context of the particular application.
- Solve a variety of basic recurrence equations.
- Analyze a problem to create relevant recurrence equations or
to identify important counting questions.
Homework and Tests
SUBJECT TO CHANGE!
There will be three tests, each of which will count 30%
of your Homework + Test
average.
We will assign occasional homework, which will count a
total of 10% of your Homework
+ Test average.
Late homework policy: In
order to allow me to discuss homework in class and to be fair to all
students, we have the following late homework policy. First, the
presumption is that you will normally turn in homework on time. The
individual homeworks are designed to be easily doable in the time
allocated to each. Also, if you get behind in the homework it will
be difficult to catch up, since the material is cumulative. Turning
homework in on time means at the beginning
of class on the day it is due. Homework turned in after I
have started lecturing is considered late. (Of course I will
consider extenuating circumstances, such as being run over by a bus
on the way to class!) I will take off a letter grade for each day
late, including weekends. And the date will be determined by when
the TA or I receives the work, not by when you deposit it. (We can’t
be responsible if you turn it in after we’ve left for the day or if
we’re not on campus.) Of course, I will consider extenuating
circumstances. I hate to sound so legalistic, but experience shows
that is pays to be explicit.
Collaboration policy: In order to improve your learning, you
can collaborate on homework, provided you keep the following in
mind:
- “Collaboration” does not mean “copying.” You can discuss
problems and solutions with your classmates, provided that you
write up your answers individually.
- You must write on your paper that you have
collaborated and name those with whom you have collaborated.
- Remember that there is no collaboration on tests!
Homework provides an opportunity for you to practice the skills
that you will need in order to do well on the tests. Therefore
you will be better prepared for the tests if you work as many
problems as you can on your own.
Homework Assignments:
- HW 1 (due Aug. 29): §2.1: 6, 8, 10.
- HW 2 (due Sept. 05): §2.2: 6, 12; §2.3: 6a, 10.
- HW 3 (due Sept. 10): §2.4: 8, 18, 22; §2.5: 12, 14.
- HW 4 (due Sept. 19): [pdf]
- HW 5 (due Sept. 26): [pdf]
- HW 6 (due Oct. 3): §1.1&1.2: 6, 16, 30, 38.
- HW 7 (due Oct 13): §1.3: 12, 18, 26; §1.4: 4, 8, 18.
- HW 8 (due Oct. 20): §3.1: 8, 12, 18; §3.2: 4, 6a, 14.
- HW 9 (due Oct. 27): §3.3: 4, 8; §3.4: 8, 12, 14.
Tentative Test Schedule:
- Exam 1: Oct. 6 (ch. 2, proof techniques).
Final Exam and Grading
SUBJECT TO CHANGE! It is anticipated that your grade will be
50% Homework + Tests
and 50% Final Exam.
The Final Exam is Mon., Dec. 8, 2:45–4:45. The
cumulative Final Exam will be two hours worth of questions similar
in difficulty to those on the Tests.
For Students with Disabilities
The Office of Disability Services and the Campus Disability Monitors
have asked us to pass this statement along in our syllabi:
Students who have a disability that require
accommodation(s) should make an appointment with the Office of
Disability Services (974-6087) to discuss their specific needs as
well as schedule an appointment with me during my office hours.
Handouts
Some charts to help you with mathematical proofs:
- The Laws of Logic (pp. 58–9) from Grimaldi [pdf]
- Table 2.19 (Rules of Inference) from Grimaldi [pdf]
- Steps from Polya’s How to
Solve It [pdf]
- Summary of proof techniques from Solow [pdf]
- A
Guide to Proof Strategies by Daniel J. Velleman (opens in
new window). You may find the Proof
Designer (opens in new window) by Velleman helpful; use it
as a learning tool, not a crutch. It goes with his book How to Prove It.
There is a supplemental handout [pdf]
with problems for practice in writing inductive proofs.
Return to MacLennan's
home page
Send mail
to Bruce MacLennan / MacLennan@eecs.utk.edu
This page is web.eecs.utk.edu/~mclennan/Classes/311
Last updated: 2014-10-23.