Discrete Mathematical Structures

CSc 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 ]

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 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