CPSC 289 Special Topics on Discrete Structures for Computing
Fall 2008
Course Information
Instructor: Andreas Klappenecker
Where: Scoates Hall 214
When: MWF 10:20am-11:10am
Office: HRBB, Room 509B
Course Information: Syllabus
This course discusses some basic mathematical techniques that are
useful in the analysis of algorithms. In particular, we will discuss
proof techniques; basic mathematical notions such as sets, functions,
and relations; basic techniques from combinatorics concerning counting
and recurrence relations. We will give a brief introduction to
algorithms and their complexity, and discuss the
automata and the Turing machine models of computation.
Office Hours
Monday
Klappenecker, HRBB 509B, 11:15-12:15; Skach, CE 137, 1:40-2:40;
Zhang, HRBB 520, 4:00-5:00
Tuesday Klappenecker, HRBB 509B, 11:00-12:00
Wednesday Zhang, HRBB 520, 1:30-3:30; Skach, CE 137,
1:40-2:40
Thursday Skach, Rich 912B, 10:15-11:15;
Zhang, HRBB 520, 2:30-5:30
Announcements
- Additional office hours by Klappenecker on Wednesday, Sep 24,
11:15am-12:15pm, HRBB 509B.
- Sep 22: The location of the MW office hours by Skach has changed.
- The office hours by Klappenecker on Tuesday, October 28, are cancelled.
- Exam 2 is scheduled for Wednesday, November 5
- Additional office hours by Klappenecker on Friday, Oct 31, 11:15-12:15.
- Office hours by Klappenecker on Tuesday, November 4, are moved to
9:55am-10:55am due to the talk by David Kribs.
- Solution to Homework 8 by Le Zhang.
- Exam 2 Practice Problems by Cynthia Skach.
- We will not have any culture assignments.
- Final Exam Practice Problems by Cynthia Skach.
- The final exam is on Tuesday, Dec 9, 8:00am, in our classroom.
- Preview of grades is on Monday, Dec 15, 9:35am-10:35am, HRBB 509B.
Lecture Notes
Homework
Schedule
M Aug 25 Syllabus, Direct Proofs, Proof by Contradiction.
Read LN Proofs, TB Chapter 1.6, 1.7
W Aug 27 Proof by Induction, Primality Test. Read LN From Proofs to Programs, TB Chapter 1.6, 1.7, skim 4.1
F Aug 29 Primality Test, Haskell, Propositional Logic;
Read LN Propositional Logic, TB Chapter 1.1, 1.2
M Sep 01 Propositional Logic. Read LN Propositional Logic, TB Chapter 1.1, 1.2
W Sep 03 Propositional Logic, Satisfiability, Tautologies,
NP and coNP
F Sep 05 Predicate Logic, Quiz 1, Homework 1 due
M Sep 08 Quantifiers, de Morgan's Law
W Sep 10 Multiple Quantifiers, Inference Rules
F Sep 12 Classes are canceled due to Hurricane Ike
M Sep 15 Sets, Quiz 2, Homework 2 due
W Sep 17 Set operations
F Sep 19 Functions, Injectivity, Surjectivity, Bijectivity
Quiz 3, Homework 3 due
M Sep 22 Functions, Sequences, Summations
W Sep 24 Review of Chapters 1, 2, and 4.1, Homework 4 due
F Sep 26 Exam 1
M Sep 29 Summation, Geometric Series, Relations
W Oct 01 Equivalence Relations, Equivalence Classes, Partitions
F Oct 03 Exam Solutions Quiz 4
M Oct 06 Relations, Partial Orders, EC Quiz
W Oct 08 Noetherian Induction, Homework 5 due
F Oct 10 Noetherian Induction, Quiz 5
M Oct 13 Algorithms
W Oct 15 Big Oh Notation
F Oct 17 Big Oh, Big Omega, Big Theta, Quiz 6, Homework 6 due
M Oct 20 Complexity of Algorithms
W Oct 22 Integer division, Greatest Common Divisors
F Oct 24 RSA Quiz 7
M Oct 27 RSA, Counting
W Oct 29 Counting
F Oct 31 Counting, Quiz 8
M Nov 03 Review
W Nov 05 Exam 2
F Nov 07 Recurrences, Fibonacci numbers
M Nov 10 Linear homogeneous recurrences
W Nov 12 Analysis of Fibonacci algorithm, Divide-and-Conquer,
Karatsuba
F Nov 14 Divide-and-Conquer recurrences, Quiz 9
M Nov 17 Language and Grammars
W Nov 19 Language and Grammars, Automata
F Nov 21 Automata
M Nov 24 Turing Machines
W Nov 26 Review
M Dec 01 Review
Additional Information
Suggested Reading
- P.J. Eccles, An Introduction to Mathematical Reasoning,
Cambridge University Press, tenth printing, 2007
[An excellent introduction to proofs and mathematical reasing.]
- D.J. Velleman, How to prove it, a
structured approach, Cambridge University Press, 1994.
[Another very good introduction to proofs and mathematical reasoning.]
- W. Rudin, Principles of Mathematical Analysis, 3rd edition, McGraw-Hill International Editions, 1976
[Examples for a good style of proofs in Analysis.]
- M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the
Theory of NP-Completeness, W.H. Freeman, 1979
- Jiri Matousek, Jaroslav Nesetril,
An Invitation to Discrete Mathematics,
Oxford University Press, 2nd edition, 2008
[More advanced than our textbook, but a pleasure to read.
Contains many elegant proofs]
- Kees Doets, Jan van Eijck,
The Haskell Road to Logic, Maths, and Programming,
King's College London Publications, 2004
[Experiment with a functional programming language
while learning discrete mathematics. Unfortunately, the recommendations
concerning proof style given there contradict our philosophy.]
- John Stillwell, Elements of Algebra - Geometry, Numbers,
Equations Springer, 1994
[Algebra is highly structured mathematical discipline, so the proofs
are a bit more predictable than in combinatorics. This book contains
many elementary proofs. A common side effect is that you will learn
abstraction and eventually become a better programmer.]
Check out our library for these and other excellent books!