BRONX COMMUNITY COLLEGE

Of the City University of New York

DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE


SYLLABUS: CSI30 DISCRETE MATHEMATICS 1 3 credits / 3 hours

PREREQUISITE: MTH 06 and ENG 02 and RDL 02 if required

TEXT: Discrete Mathematics and its Applications, Sixth Edition,

by Kenneth H. Rosen, published by McGraw-Hill 2007


Goals of the course:

CSI 30 is an introduction to mathematical methods in computer science. It begins with basic concepts of mathematical logic, continues with an introduction to algorithms and programming, and concludes with an introduction to counting techniques and probability. The emphasis is on computational, hands-on experience. The material on set theory reinforces and complements parallel topics covered in Precalculus (MTH 30). It is highly recommended that MTH 30, if required, and CSI 30 are taken in the same semester.


Objectives: A successful student in this course will learn to:

  1. Understand the idea of an algorithm and computer program;

  2. Write and analyze simple programs;

  3. Understand the use of formal logic in mathematics and programming;

  4. Understand basic concepts of set theory, particularly those of a function;

  5. Use basic combinatorial counting techniques, particularly permutations and combinations;

  6. Understand basic concepts of probability theory, and the way counting techniques are used there.




Chapters and sections

Suggested in-class examples

Suggested Homework


Chapter 1 The Foundations: Logic and Proof, Sets, and Functions (5 weeks)


1.1

Propositions. Boolean connectives. Implications.

Examples 1-11

16/1, 3, 5, 7, 17

1.1

Translating English sentences.
System specifications. Boolean
Searches. Bit operations. Truth
Tables.

Examples 12-21

19/27, 29, 37, 49, 53

1.2

Propositional Equivalences

Examples All

28/1-9 (odd)

1.3

Predicates and Quantifiers

Examples 1-12

Examples 23, 24, 28

46/l-25 (odd)

48/27, 31, 35, 55

1.4

Nested quantifiers.

Examples 1-15

58/1, 3, 5, 9, 15, 25, 27, 33

1.5

Rules of Inference. Fallacies.

Examples 1-11

72/1-7 (odd)


Chapter 2 Basic Structures: Sets, Functions, Sequences, Sums


2.1

Sets, power sets, Cartesian

products.

Examples 1-19

119/l-9 (odd), 19-25 (odd)

2.2

Set operations. Set identities.

Examples 1-14

130/1, 3, 25

2.2

Computer representations of sets.

Examples 18, 19, 20

132/50, 51, 52, 53

2.3

One-to-one and onto functions.

Examples 1-15

148/1-7 (odd)

2.3

Inverse and composition of functions. Graphs. Some important functions.

Examples 16-28

148/9, 12, 13, 15, 19, 27, 32, 39



(OVER)




Chapters and sections

Suggested in-class examples

Suggested Homework


Chapter 3 The Fundamentals: Algorithms, the Integers, and Matrices


3.1

Algorithms. Pseudocode.

Searching algorithms

Examples 1, 2

177/1, 3, 5

3.1

Sorting. Greedy algorithms.

Examples 4, 5

177/2, 7, 13, 19, 35

3.4

Division.

Examples 1-4

208/1, 9

3.4

Modular arithmetic. Applications of congruences. Pseudorandom numbers.

Examples 5-8

208/17, 19, 27

3.5

Fundamental Theorem of Arithmetic.

The Infinitude of Primes.

Examples 1-5

217/3, 11, 12

3.5

Representations of integers

Examples 1-6

229/1, 3, 5

3.5

Algorithms for integer operations.

Modular exponentiation.

The Euclidean algorithm.

Examples 7-9, 11, 12

230/19, 23

3.8

Matrix arithmetic.

Examples 1-6

254/1, 3, 5

3.8

Transposes and powers of

Matrices. Zero-one matrices.

Examples 7-12

255/19, 20, 28, 29


Chapter 5 Counting (4 weeks)


5.1

Basic counting principles

Examples 1-13

344/l-17 (odd)

5.1

More complex counting

problems. Exclusion inclusion

principle. Tree diagrams.

Examples 14-21

345/19-31 (odd)

5.3

Permutations and combinations.

Examples 1-15

360/1-19 (odd)

5.4

Binomial coefficients.

Pascal's triangle.

Examples 1-4

369/1-9 (odd), 12, 13


Chapter 6 Discrete Probability


6.1

Introduction to probability

Examples 1-9

398/l-27 (odd)



RK/2003; Revised Nov 2006/JP/SP Fall 2007, CO'S Fall 2008