CS 441 Discrete
Mathematics for Computer Science
Time: TH 11:00am-12:15pm 205 LAWRN
Instructor:
- Milos
Hauskrecht
5329 Sennott Square, x4-8845
e-mail: milos at cs pitt edu
office hours: Monday 1:00-3:00pm
Recitations:
- Section 1: Thursday: 5:00 -- 4:50 PM, 5313 SENSQ,
- Section 2: Friday: 11:00 -- 11:50 AM, 5313 SENSQ
TA:
- Zitao Liu
5406 Sennot Square, x4-0513
e-mail: ztliu at cs pitt edu
office hours: Monday 3:30-5:00pm, Tuesday 2:00-5:00pm, Wednesday 10:00-11:00am
Links
Course
description
Lectures
Grading
Homeworks
Additional
Student Resources
Academic
Honesty
Announcements
(check often):
- The final exam for the course is on Saturday, April 26, 2014 at 10:00-11:50am in 205 LAWRN. The exam is a closed book, cumulative exam. Please bring your own calculator. You may need it to complete the solution for some of the counting problems.
- The review will be held during the recitations on Thursday (04/17) and Friday (04/18).
- Please note that all problems in the homework assignments are from the 7th edition of the textbook.
- Homework assignment solutions:
Course description
The purpose of this course is to understand and use (abstract)
discrete structures that are backbones of computer science. In
particular, this class is meant to introduce logic, proofs, sets,
relations, functions, counting, and probability, with an emphasis on applications in computer science.
Prerequisites:
2 years of high school algebra.
Syllabus
Textbook:
Kenneth Rosen.
Discrete Mathematics and Its Applications, 7th Edition , McGraw Hill Publishing Co., 2012.
Tentative Syllabus
- Logic: propositional logic, logical equivalence, predicates &
quantifiers, and logical reasoning.
- Sets: basics, set operations
- Functions: one-to-one, onto, inverse, composition, graphs
- Integers: greatest common divisor, Euclidean algorithm.
- Sequences and Summations
- Mathematical reasoning: Proof strategies, Mathematical Induction,
Recursive definitions, Structural Induction
- Counting: basic rules, Pigeon hall
principle, Permutations and combinations, Binomial coefficients and
Pascal triangle.
- Probability: Discrete probability. Expected values and variance.
- Relations: properties, Combining relations, Closures, Equivalence,
partial ordering
- Graphs , directed, undirected graphs.
Lectures
Lectures |
Topic(s) |
Readings |
Assignments |
January 7 |
Administrivia, Propositional logic.
|
Section 1.1. |
. |
January 9 |
Propositional logic.
|
Sections 1.1-3. |
Homework assigment 1 |
January 14 |
Predicate logic.
|
Sections 1.4. |
. |
January 16 |
Predicate logic.
|
Sections 1.4-5. |
Homework assigment 2 |
January 21 |
Predicate logic. Formal and informal proofs
|
Sections 1.5-6. |
. |
January 23 |
Informal proofs
|
Sections 1.5-7. |
Homework assigment 3 |
January 28 |
Sets and set operations
|
Sections 2.1-2. |
. |
January 30 |
Sets and set operations (cont.), Functions
|
Sections 2.1-3. |
Homework assigment 4 |
February 4 |
Functions II.
|
Sections 2.1-3. |
. |
February 6 |
Sequences and summations
|
Sections 2.4. |
Homework assigment 5 |
February 11 |
Countable and uncountable sets. Matrices.
|
Sections 2.5-6. |
. |
February 13 |
Matrices. Integers and division
|
Sections 2.6., 4.3. |
Homework assigment 6 |
February 18 |
Integers and divisions. Congruency. CS applications.
|
Sections 4.3., 4.5. |
. |
February 20 |
Integers: Applications, base conversions. Mathematical induction.
|
Section 4.2., 4.5. |
Homework assigment 7 |
February 25 |
Mathematical induction and recursion.
|
Chapter 5 |
. |
February 27 |
Counting: basic counting rules.
|
Sections 6.1-2. |
Homework assigment 8 |
March 4 |
Counting: permutations, combinations.
|
Chapter 6 |
. |
March 6 |
Midterm exam
|
Chapters 1,2,4,5 and 6.1. |
. |
March 18 |
Midterm exam solutions
|
Chapters 1,2,4,5 and 6.1. |
. |
March 20 |
Counting: advanced counting methods. Probability
|
Sections 6.3-5; Chpater 7 |
Homework assigment 9 |
March 25 |
Probabilities.
|
Chapter 7 |
. |
March 27 |
Probabilities: Bayes theorem, Bernoulli trial, Random variables, Expected value.
|
Chapter 7 |
Homework assigment 10 |
April 1 |
Probabilities: expected value
Relations
|
Chapters 7,9.1-3. |
. |
April 3 |
Relations II.
|
Chapter 9.1-3. |
Homework assigment 11 |
April 8 |
Relations III
|
Chapters 9.1-3. |
. |
April 10 |
Relations IV. Graphs
|
Chapter 9.1-6. |
Homework assigment 12 |
April 15 |
Graphs: graph types, graph properties
|
Chapter 10. |
. |
April 17 |
Graphs: Connectivity, Trees
|
Chapter 10. |
. |
April 26 |
Final exam
|
|
. |
Grading
-
Lectures 10 %
- Homework assignments 40%
-
Exams
50%
Homeworks
There will be weekly homework assignments. The
assignments are due at the beginning of the class on the day specified
on the assignment. In general, no extensions will be granted.
Additional Student Resources
Academic Honesty
All the work in this course should be done
independently. Collaborations on homeworks are not permitted. Cheating
and any other antiintellectual behavior, including giving your work to someone
else, will be dealt with severely. If you feel you may have violated
the rules speak to us as soon as possible.
Please make sure you read, understand and abide by the Academic
Integrity Code for the Faculty and College of Arts and Sciences.
Students With Disabilities
If you have a disability for which you are or may be requesting an
accommodation, you are encouraged to contact both your instructor and
Disability Resources and Services, 216 William Pitt Union, (412)
648-7890/(412) 383-7355 (TTY), as early as possible in the term. DRS
will verify your disability and determine reasonable accomodations for
this course.
The web page is maintained by milos