CSC 104 - Syllabus

The City College of New York • Grove School of Engineering • Computer Science Department • Course Syllabus

Course number

CSc 10400

Course name

Discrete Mathematical Structures

Credits & hours

4 cr., 3 hr. lecture, and 2 hr. recitation

Course coordinator

Prof. Douglas Troeger

 

Textbook, title, author, and year

  • Grimaldi, Ralph P. Discrete and Combinatorial Mathematics, An Applied Introduction,5th Edition, Pearson/Addison-Wesley, 2004
  • Other supplemental materials: web available materials related to course work

Specific course information

  • 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, and trees.
  • Prereq.: Math 20100 with minimum C grade
  • Required course

Specific goals for the course and Relationship to student outcomes

 

1

2

3

4

5

6

a. the student gains understanding of combinatrics and be able to apply its techniques needed in computer science

I

    

I

b. the student gains understanding of logic and proofs and be able to apply their techniques needed in computer science

I

    

I

c. the student gains understanding of set theory and be able to apply their techniques needed in computer science

I

    

I

d. the student gains understanding of relations and functions and be able to apply their techniques needed in computer science

I

    

I

e. the student gains understanding of graphs and trees and be able to apply their techniques needed in computer science

I

    

I

I - introductory-level; R - reinforced-level; P - program-level

Brief list of topics to be covered

Seq.

Topics

1

Fundamental Principles of Counting: The rules of sum and product; Permutations; Combinations: The Binomial Theorem; Combinations with repetitions: distributions

2

Fundamentals of Logic: Basic connectives and truth tables; Logical equivalence: the laws of logic; Logical implication: methods of proof; The use of quantifiers; Quantifiers, definitions, and the proofs of theorems

3

Set Theory: Sets and subsets; Set operations and the laws of set theory; Counting and Venn diagrams

4

Mathematical Induction: The well-ordering principle: mathematical induction;Recursive definitions

5

Relations and Functions: Cartesian products and relations; One-to-one and onto functions; Special functions; The pigeonhole principle; Function composition; inverse functions

6

Relations continued: Properties of relations; Computer recognition: zero-one matrices and graphs; Partial orders: Hasse diagram; Equivalence relations and partitions

7

Recurrence relations: First-order linear recurrence relations; Second-order linear recurrence relations; Non-homogeneous recurrence relations

8

An introduction to graph theory: Definitions and examples; Subgraphs; graph isomorphism; Vertex degree; Euler trails and circuits

9

Trees: Definitions, properties and examples; Rooted trees; Trees and sorting problems; Weighted trees and prefix codes

 

 

Last Updated: 05/22/2018 19:51