Discrete Mathematical StructuresCSc 10400 AB–Fall 2018 |
The City College of CUNY Department of Computer Science |
Instructor:
Prof. Nelly Fazio
Lectures: M/W, 9:00–10:40am, NAC 4130
Office hours: Mondays, 11:00–12:00pm, SH-279
Email: fazio AT cs DOT ccny DOT cuny DOT edu
[Put CSc104 in Subject line]
TA: Edy Garfinkiel
Email: egarfinkiel AT ccny DOT cuny DOT edu
Recitations: Wed. 12:00–1:40pm, NAC 5102
Office hours: Wednesdays, 11:00–12:00pm
[ Course Description | Syllabus | Textbook | Grading | CUNY Academic Integrity Policy | Slides | Homework | Weekly Schedule ]
Prerequisites: Math 20100 (min. C grade).
Lecture | Date | Topic | Readings |
1 | Aug 27 |
Introduction The rule of sum and product Permutations |
1.1, 1.2 |
2 | Aug 29 |
Combinations: the binomial theorem Combinations with repetition |
1.3, 1.4 |
Sep 3 | No class! (Labor Day) | ||
3 | Sep 5 |
Basic connectives and truth tables Logical equivalence: the laws of logic |
2.1, 2.2 |
Sep 10 | No class! | ||
4 | Sep 12 | Logical implication: rules of inference | 2.3 |
5 | Sep 17 | The use of quantifiers | 2.4 |
Sep 19 | No class! | ||
6 | Sep 24 | Quantifiers, definitions, and the proof of theorems | 2.5 |
7 | Sep 26 | Sets and subsets | 3.1 |
7 | Sep 26 | Set operations and the laws of set theory | 3.2 |
9 | Oct 1 | Counting and Venn Diagrams | 3.3 |
Oct 8 | No class! (Columbus Day) | ||
10 | Oct 10 | Midterm Exam | |
11 | Oct 15 |
The well-ordering principle: mathematical induction Recursive definitions |
4.1, 4.2 |
12 | Oct 17 |
The division algorithm: prime numbers The greatest common divisor: the Euclidean algorithm |
4.3, 4.4 |
13 | Oct 22 |
Cartesian products and relations Functions: plain and one-to-one Onto functions: Stirling numbers of the second kind |
5.1, 5.2, 5.3 |
14 | Oct 24 |
Special functions The pigeon principle Function composition and inverse function |
5.4, 5.5, 5.6 |
15 | Oct 29 | Relations revised: properties of relations | 7.1 |
16 | Oct 31 | Computer recognition: zero-one matrices and directed graph | 7.2 |
17 | Nov 5 |
Rings: definition and examples Ring properties and substructures |
14.1, 14.2 |
18 | Nov 7 | The integers modulo n | 14.3 |
19 | Nov 12 |
Groups: definition, examples, and elementary properties Homomorphisms, isomorphisms. Cyclic groups |
16.1, 16.2 |
20 | Nov 14 | Cosets and Lagrange's theorem | 16.3 |
21 | Nov 19 |
The principle of inclusion and exclusion Generalization of the principle |
8.1, 8.2 |
22 | Nov 21 | Midterm Exam (tentative) | |
23 | Nov 26 |
First-order linear recurrence relations The second-order linear homogeneous recurrence relation with constant coeffecients Nonhomogeneous recurrence relations |
10.1, 10.2, 10.3 |
24 | Nov 28 |
Graphs: definitions and examples Subgraphs, complements, and graph isomorphism |
11.1, 11.2 |
25 | Dec 3 |
Vertex degree: Eulerian trails and circuits Planar graphs |
11.3, 11.4 |
26 | Dec 5 |
Hamiltonian paths and cycles Graph coloring and chromatic polynomials |
11.5, 11.6 |
27 | Dec 10 |
Trees: definitions, properties, and examples Rooted trees |
12.1, 12.2 |
28 | Dec 12 |
Trees and sorting Weighted trees and prefix codes |
12.3, 12.4 |
Dec 19 | Final Exam, Wed., Dec 19, 8:00–10:15am |
Copyright © Nelly Fazio