discrete structures

Discrete Structures, Spring 2013
Course Information and Syllabus

Sample Final

Instructor:

Catherine Durso
(email cdurso"AT"cs"DOT"du"DOT"edu)
Office: JGH 106 303 871 3598
Office Hours: 1:00-3:00 MW
and by appointment

GTA:
Ryan Davis
(email ryandavisbusiness"AT"gmail"DOT"com)
Office: JGH 331
Office Hours: Tuesday, Thursday noon-2:00
and by appointment

About This Course

Discrete and Combinatorial Mathematics presents the fundamentals of combinatorics, logic, set theory, recursion, functions and relations, probability, and algorithm analysis. Combinatorics, counting theory, applies to algorithm analysis and to probabilistic analysis. Logic, set theory, recursion, and functions and relations provide intellectual structures to support more sophisticated program structures, such as recursive algorithms, and data mining. Relations are central to structuring and querying databases.

The material depends on college algebra. Ingenuity is more essential than specific prerequisites beyond algebra.

Problem sets and exams will be primarily pencil-and-paper exercises, rather that programming assignments. Students will determine the cardinality of finite sets, evaluate and simplify logical expressions, solve logical problems, write valid proofs, design and verify recursive structures, and calculate probabilities.

Course Meeting Times

The MW lecture is held 10:00-11:50am.

The TR lecture is held 2:00-3:50pm.

Text

Discrete Mathematics and Its Applications, ed. 7, Kenneth H. Rosen, ISBN 978-0-07-338309-5

Zermelo-Fraenkel Axioms

Syllabus

We will cover the chapters 1, 2, 3, 5, 6, 7 and 9 with supplementary material as dictated by time and interest.

Grading

Grades in this course will be calculated as follows:

homework	30% total
in-class exam, May 1/2	30%
quizzes	10%
final (M:10:00-11:50am, 6/3/13, T:2:00-3:50, 6/4/13)	30%

In addition, each student must provide an acceptable technical writing sample based on course assignments.

Collaboration and Academic Honesty

When you turn in work in this course, you are implicitly agreeing that you have followed the rules for collaboration set forth for that assignment. In general,

For problem sets, you may consult with the instructor, or fellow students. Do not do web searches for solutions.
For the in-class exams and quizzes, you will work individually.
For the midterm exam, you are allowed notes on both sides of one 8.5"x11" piece of paper.
For the final exam, you will work individually.

Guidelines for Presentation of Homework Assignments

You may certainly type your solutions, however, handwriting is acceptable as long as I find it to be readable, understandable and organized. Only the even-numberes problem will be graded. The solutions to the odd-numbered problems are in the back of the book. Please turn in paper copies in class on the due date. You may turn in one assignment for two-person groups. If you wish to work in a larger group, you may do so, but the writeups for the assignments should be independent.

Assignments

Readings week 1, assigned March 25-26, due March 27-28:

section 1.1

section 1.2

section 1.3 (We will review the Sudoku example.)

section 1.4

Look over problems 1.1: 16, 24, 30, 32, 1.2: 6, 12, 24, 32

The bolded problems can be found here.

Problem set 1, assigned March 27/28 , due April 3/4:

Study:

section 1.1: 23, 31
section 1.2: 17, 33
section 1.3: 17, 49
Hand in:

section 1.1: 32
section 1.2: 12, 32
section 1.3: 16, 50

Readings due April 1/2

section 1.5, skip example 16
Look over problems 1.3: 9, 11, 17, 50, 1.4: 5, 13 (there is an error in the solutions), 36. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Readings due April 3/4

section 1.6, don't stress about memorizing the names of the rules.
section 1.7,pp. 80-88
Look over problems 1.5: 5, 26, 1.6:15, 20, 23 You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Readings due April 8/9

section 1.7, finish.
section 1.8,through "Chomp".
Look over problems 1.7: 5, 9, 11, 24. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Problem set 2, assigned April 3/4 , due April 10/11:

Study:

section 1.4: 9, 15
section 1.5: 27, 35
section 1.6: 9, 15
Hand in:

section 1.4: 14, 36
section 1.5: 26, 46
section 1.6: 20

Readings due April 10/11

section 1.8, finish.
section 2.1
section 2.2
Look over problems section 1.8: 9, 13, 15, 32, section 2.1: 9, 11, 23, 24, section 2.2: 1, 15, 27, 40, 49. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Problem set 3, assigned April 10/11 , due April 17/18:

Study:

section 1.7: 5, 9, 11
section 1.8: 9, 13, 15
section 2.1: 9, 11, 23
section 2.2: 1, 15, 27, 49
Hand in:

section 1.7: 24
section 1.8: 32
section 2.1: 24, 30
section 2.2: 40

Readings due April 15/16

section 2.3
section 2.4
Look over problems section 2.3: 15, 43, 73, 74, section 2.4: 3, 9, 29, 39, 36. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Readings due April 17/18

section 2.5
section 3.1
Look over problems section 2.5: 1, 10, 11, section 3.1: 7, 19, 53, 54. You will work on the bolded problems in class. The others are guides to whether you have understood the reading. For 2.5, please note definitions of cardinality, cardinality inequality, countable, uncountable and computable . For 3.1, please note the definitions of searching and sorting, the description of greedy algorithms, example 6, and example 7.
The bolded problems can be found here.
Problem set 4, assigned April 17/18 , due April 24/25:
Study:

section 2.3: 15, 43, 73
section 2.4: 3, 9, 29, 39
section 2.5: 1, 11
section 3.1: 7, 19, 53
Hand in:

section 2.3:74
section 2.4: 36, 40
section 2.5: 10
section 3.1: 54

Readings due April 22/23

section 5.1: This is a shorter reading assignment, because it is conceptually challenging.
Look over problems section 5.1: 2, 3, 18, 32. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Readings due April 24/25

section 5.2
Look over problems section 5.2: 4, 5, 14, 15. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.
A sample midterm is available for your review.

Readings due April 29/30

section 5.3
Look over problems section 5.3: 1, 5, 7, 26, 27, 32, 33. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.
Problem set 5, assigned April 24/25 , due May 8/9:
Study:

section 5.1: 2, 3
section 5.2: 5, 15
section 5.3: 1, 5, 27, 33
Hand in:

section 5.1: 18, 32
section 5.2: 14
section 5.3: 26, 32

Readings due May 6/7

section 5.4 pp. 360-367
Look over problems section 5.4: 7, 21, 18, 24, 29. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Readings due May 8/9

section 5.5, 6.1
Look over problems section 5.5: 7, 12, 6.1: 1, 3, 5, 32, 33, 44. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.
Problem set 6, assigned May 8/9 , due May 15/16:
Study:

section 5.4: 7, 21, 29
section 6.1: 1, 3, 5, 33
Hand in:

section 5.4: 18, 24
section 5.5: 12
section 6.1: 32, 44

Readings due May 13/14

section 6.2, 6.3
Look over problems section 6.2: 1, 9, 13, 14, 31, 35, 6.3: 1, 9, 11, 13, 24, 30. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Readings due May 15/16

section 6.4, 7.1
Look over problems section 6.4: 3, 7, 9, 21, 28, 7.1: 1, 15, 16, 34. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Problem set 7, assigned May 15/16 , due May 22/23:
Study:

section 6.2: 1, 9, 13, 31, 35
section 6.3: 1, 9, 11, 13
section 6.4: 3, 7, 9, 21
section 7.1: 1, 15
Hand in:

section 6.2: 14
section 6.3: 30
section 6.4: 28
section 7.1: 16, 34

Readings due May 20/21

section 7.2 through Example 15, 7.3
Look over problems section 7.2: 1, 5, 7, 27, 30, 38 a 7.3: 5, 8, 16. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Readings due May 22/23

section 7.4 p. 477 through Example 8, and p. 487- example 14, 9.1
Look over problems section 7.4: 1, 5, 8, 11, 9.1: 5, 6. You will work on the bolded problems in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.

Problem set 8, assigned May 22/23 , due May 29/30:
Study:

section 7.2: 1, 5, 7, 27
section 7.3: 5
section 7.4: 1, 5
Hand in:

section 7.2: 30, 38a
section 7.3: 8, 16
section 7.4: 8

Readings due May 28/29

section 9.5
Look over problems section 9.5: 3, 28. You will work on the bolded problem in class. The others are guides to whether you have understood the reading.
The bolded problems can be found here.