Discrete Mathematical Structures

CSc 10400 FG–Fall 2017

The City College of CUNY
Department of Computer Science

Instructor: Prof. Nelly Fazio
Lectures: M/W, 4:00–5:40pm, Marshak 1026
Office hours: Wednesdays, 3:00–4:00pm, SH-279
Email: fazio AT cs DOT ccny DOT cuny DOT edu [Put CSc104 in Subject line]


[ Course Description | Syllabus | Textbook | Grading | CUNY Academic Integrity Policy | Slides | Homework | Weekly Schedule ]


Course Description

From the course catalog: Introduction to the mathematics fundamental to all phases of computer science, from the formulation of problems to the understanding of their underlying structure, to the comparative analysis of the complexity of algorithms that can be used to solve these problems. The course introduces combinatorics, first-order logic, induction, set theory, relations and functions, graphs, trees, and number theory.

Prerequisites: Math 20100 (min. C grade).

Course Syllabus

The syllabus for this course is available here.

Textbook

Required:

Grading

NOTE: There will be NO make-up or substitute exams.

CUNY Academic Integrity Policy

Cheating will not be tolerated. If you cheat, you risk losing your position as a student in the department and the college. CUNY policy on academic integrity can be found here. Failure to understand and follow these rules will constitute cheating, and will be dealt with as per university guidelines.

Slides

Slides are posted on blackboard.

Homework

Weekly Schedule (tentative)

Lecture Date Topic Readings
1 Aug 28 Introduction
The rule of sum and product
Permutations
1.1, 1.2
2 Aug 30 Combinations: the binomial theorem
Combinations with repetition
1.3, 1.4
  Sep 4 No class! (Labor Day)  
3 Sep 6 Basic connectives and truth tables
Logical equivalence: the laws of logic
2.1, 2.2
4 Sep 11 Logical implication: rules of inference 2.3
5 Sep 13 The use of quantifiers 2.4
6 Sep 18 Quantifiers, definitions, and the proof of theorems 2.5
  Sep 20 No class!  
7 Sep 25 Sets and subsets
Set operations and the laws of set theory
3.1, 3.2
8 Sep 27 Counting and Venn Diagrams 3.3
9 Oct 2 Midterm Exam  
10 Oct 4 The well-ordering principle: mathematical induction
Recursive definitions
4.1, 4.2
  Oct 9 No class! (Columbus Day)  
11 Oct 11 More on mathematical induction  
12 Oct 16 The division algorithm: prime numbers
The greatest common divisor: the Euclidean algorithm
4.3, 4.4
13 Oct 18 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 23 Special functions
The pigeon-hole principle
Function composition and inverse function
5.4, 5.5, 5.6
15 Oct 25 Relations revised: properties of relations 7.1
16 Oct 30 Computer recognition: zero-one matrices and directed graph 7.2
17 Nov 1 Rings: definition and examples
Ring properties and substructures
14.1, 14.2
18 Nov 6 The integers modulo n 14.3
19 Nov 8 Groups: definition, examples, and elementary properties
Homomorphisms, isomorphisms. Cyclic groups
16.1, 16.2
20 Nov 13 Cosets and Lagrange's theorem 16.3
21 Nov 15 Midterm Exam  
22 Nov 20 60th Birthday Celebration for Prof. Leonid Gurvits
23 Nov 22 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 27 Graphs: definitions and examples
Subgraphs, complements, and graph isomorphism
11.1, 11.2
25 Nov 30 Vertex degree: Eulerian trails and circuits
Planar graphs
11.3, 11.4
26 Dec 4 Hamiltonian paths and cycles
Graph coloring and chromatic polynomials
11.5, 11.6
27 Dec 6 Trees: definitions, properties, and examples
Rooted trees
12.1, 12.2
28 Dec 11 Trees and sorting
Weighted trees and prefix codes
12.3, 12.4
Dec 18 Final Exam, Mon., Dec 18, 3:30–5:45pm

Copyright © Nelly Fazio