Math 55—Discrete Mathematics—Fall 2008
855 Evans Hall, office hours W 1:30-2:15, 2:30-3:00, F 1:30-3:00.
Section Instructors:
- Amit
Gupta, 845 Evans Hall, office hours M 3-4, W 9-10, Th 2-3.
- Darsh Ranjan, 789 Evans
Hall, office hours W 2:30-3:30, Th 2-3 and F 1-2.
- Cinna
Wu, 941 Evans Hall, office hours Th 10-11, F 2:30-3:30.
Lectures: MWF 12:00-1:00pm, Room 2060 Valley LSB
Discussion sections: See schedule.
You can change sections online through TeleBears. When you sign up
for a section that is full, you get put on its wait list. Students on
the wait list are automatically enrolled when spaces open. If you are
near the top of the wait list for your preferred section, you are
likely to get in. Otherwise, a good strategy is to check daily for
other sections that become open or whose wait list shortens, and
switch if you find one that improves your wait list position.
If you have problems you can't resolve with the online system, see the
Head TA, Ishai Dan-Cohen, in 1039 Evans Hall. His office hours (for
the first two weeks of classes) are MWF 3:30-6:30, TTh 2:30-3:30 and
4-6. Don't email him—he is responsible for too many
students to reply to email.
Description: This course provides an introduction to logic
and proof techniques, basics of set theory, algorithms, elementary
number theory, combinatorial enumeration, discrete probability, graphs
and trees, with applications to coding theory. It is designed for
majors in mathematics, computer science, and other related science and
engineering disciplines.
Prerequisites: Mathematical maturity appropriate to a sophomore
math class. 1A-1B recommended but not required. Freshmen with strong
high school math background and a possible interest in majoring in
mathematics may also wish to consider taking this course.
Textbook: Kenneth H. Rosen, Discrete Mathematics and Its
Applications, 6th Edition
Grading: Based on weekly homework (20%), two midterm exams
(20% each), and final exam (40%).
Incomplete (I) grades are rarely given, and only for a documented
serious medical problem or genuine personal/family emergency. Falling
behind in the course or problems with workload on other courses are
not acceptable reasons to request an incomplete.
Exams:
- Midterm 1: Friday, October 3, 12-1, in two rooms
- Last names A-K: 2060 Valley LSB (the usual lecture room)
- Last names L-Z: 120 Latimer
- Midterm 1 Solutions
- Midterm 2: Friday, November 7, 12-1
- Last names A-K: 390 Hearst
Mining Building (NOT 50 Birge as previously announced)
- Last names L-Z: 2060 Valley LSB (the usual lecture room)
The exam will start promptly at 12:10. Please arrive as early as
possible to facilitate handing out exams. You will write your
answers on the exam paper, but please bring your own scratch
paper.
- Midterm 2 Solutions
- Final Exam: Friday, December 19, 5-8pm (exam group 18), 230 Hearst Gym
The final exam is comprehensive, covering the whole course. However,
about 60% of it will be on material from Homeworks 10-14, which was
not covered on the midterms.
You can expect exam questions to be similar in difficulty to those on
the midterm exams and the more routine types of homework problems.
The exam will only cover material assigned as homework; it will not
contain questions from the last two lectures.
You are allowed one sheet of notes (both sides), the same as for
midterms. You will write your answers on the exam paper, but please
bring your own scratch paper.
For review, you might find helpful these review
problems with answers and final
exam with solutions from when I taught this course in Spring 2003
(ignore the questions on graph theory topics and big-O notation which
we did not cover this semester).
- Final Exam Solutions
At exams you will be allowed one (ordinary sized) sheet of notes,
written on both sides. No other notes, books, calculators, computers
or other aids will be permitted.
No make-up exams will be given. If you miss one midterm, your score
on the following exam will count in place of that midterm. (However,
you cannot "miss" a midterm retroactively after turning in the exam).
For review, you can find web pages from this course in earlier years,
including exams with solutions, on Richard Borcherds' math courses
archive.
Homework: Homework will be due on Mondays and returned in
discussion sections on Wednesdays. The deadline to turn in homework
for all students is the end of the last discussion section on
Monday.
A semi-random subset of the problems on each homework will be chosen
for full grading, and scored out of 10 points each. The remaining
problems will only be checked quickly and will count 2 points each.
The choice of problems for grading will not be announced in advance,
but will be indicated on the solutions. I am somewhat more likely to
choose for grading those problems requiring more thought.
You are free to discuss the homework problems and ideas for solving
them with other students, but you must write up your solutions
individually. It is not acceptable to copy solutions worked out by
others or found on the internet.
Special accomodations: Students requiring special
accomodations for exams must provide documentation from the Disabled
Students' Program (DSP), and should contact me well in advance of the
first exam so that suitable arrangements can be made.
Syllabus
- Propositional logic, quantifiers, rules of inference,
proof techniques (Rosen Chapter 1)
- Sets, functions, countability and uncountable sets (Sections
2.1-2.3, and part of 2.4 on cardinality)
- Algorithms, halting problem (Section 3.1), undecidability (covered
in lecture)
- Division algorithm, modular arithmetic, primes, GCD (Sections
3.4-3.5)
- Euclidean algorithm, modular exponentiation, solving
conguences, Chinese Remainder Theorem, applications to
cryptography (Sections 3.6-3.7)
- Induction and recursion, recursive algorithms (Sections
4.1-4.4; revisit 2.4 for summations)
- Counting, pigeon hole principle, permutations and
combinations, binomial coefficients, distributions, Stirling
numbers (Sections 5.1-5.5)
- Discrete probability theory, conditional probability,
independence, random variables (Sections 6.1-6.2)
- Bayes' Theorem and applications (Section 6.3)
- Expected value, variance, Chebyshev's inequality (Section
6.4)
- Recurrence relations and generating functions (Sections
7.1-7.2 and Examples 10-15 in 7.4)
- Inclusion-exclusion, derangements, formula for Stirling
numbers (Sections 7.5, 7.6)
- Relations, directed graphs, transitive closure, equivalence
relations, set partitions, partial orders (Section 8.1, part
of 8.3 on digraphs, 8.4-8.6)
- Graphs, isomorphism, connectivity (Sections 9.1-9.4)
- Trees, spanning trees, minimum-weight spanning trees
(Sections 10.1, 10.4-10.5)
- Additional topics to be included as time permits, most likely
drawn from the following: (i) primality testing and factoring
algorithms, (ii) matrices and error-correcting codes, (iii)
shortest-path problems, (iv) planar graphs and the four and five-color
theorems (v) counting trees.
Reading and Homework Assignments
By popular demand, I'm also posting here files of the computer demos
of RSA, Pollard's factoring algorithm, and Reed-Solomon codes shown in
the lectures. These are in two formats:
- PDF files, which you can view with any PDF viewer but are not
interactive: RSA and factoring, Reed-Solomon
- Mathematica 6.0 notebooks. If you have access to a computer with
Mathematica (version 6.0 or later) installed, you can download these
to experiment with the code: RSA and
factoring, Reed-Solomon
[ Top of page | Prof. Haiman's home page ]