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, Seventh Edition,
by Kenneth H. Rosen, published by McGrawHill 2012
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, handson 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 inclass examples  Suggested Homework 
Chapter 1 The Foundations: Logic and Proofs (5 weeks)
1.1  Propositional Logic.  Examples All  1216/1, 3, 7, 9, 13, 17, 19, 25, 27, 31, 37, 43 
1.2  Translating English sentences.  Examples 18  2224/5, 7, 11, 13, 17, 21

1.3  Propositional Equivalences  Examples All  35/121 (odd)

1.4  Predicates and Quantifiers  Examples 118, 2024, 28  53 /127 (odd), 31, 33, 35, 53, 55 
1.5  Nested quantifiers.  Examples 115  64/1, 3, 5, 9, 15, 25, 27, 33 
1.6  Rules of Inference. Fallacies.  Examples 111  78/19 (odd) 
Chapter 2 Basic Structures: Sets, Functions, Sequences, Sums (3 weeks)
2.1  Sets, power sets, Cartesian products.  Examples 119  125/l9 (odd), 1523 (odd), 27, 31, 35

2.2  Set operations. Set identities.  Examples 115  136/1, 3, 13, 25 
2.2  Computer representations of sets.  Examples 18, 19, 20  137/5255(all) 
2.3  Onetoone and onto functions.  Examples 117  152/17 (odd) 
2.3  Inverse and composition of functions. Graphs. Some important functions.  Examples 1830  152/9, 12, 13, 15, 23, 31, 36, 43 
2.6  Matrix Arithmetic. Transposes and powers of matrices. Zeroone matrices.  Examples 19  183/1, 3, 5, 19, 20, 26, 27 
(OVER)
Chapters and sections  Suggested inclass examples  Suggested Homework 
Chapter 3 Algorithms (1 week)
3.1  Algorithms. Pseudocode. Searching algorithms  Examples 13  202/1, 3, 5 
3.1  Sorting. Greedy algorithms.  Examples 46  202/2, 7, 13, 19, 35 
Chapter 4 Number Theory and Cryptography (2 weeks)
 
4.1  Division. The division algorithm.  Examples 14  244/1, 9 
4.1  Modular arithmetic.  Examples 56
 244/21, 29 
4.5  Applications of congruences (hashing functions). Pseudorandom numbers.  Examples 13  292/3, 5 
4.3  Primes. Fundamental Theorem of Arithmetic. The Infinitude of Primes. The Euclidean Algorithm.  Examples 15, 16  272/3, 15, 17, 33 
4.2  Representations of integers.  Examples 17  254/1, 3, 5, 7 
4.2  Algorithms for integer operations. Modular exponentiation.  Examples 8, 10, 12  254/25 
Chapter 6 Counting (3 weeks)
6.1  Basic counting principles  Examples 114  396/l17 (odd) 
6.1  More complex counting problems. Exclusion inclusion principle. Tree diagrams.  Examples 1523  396/1933 (odd)

6.3  Permutations and combinations.  Examples 115  413/119 (odd), 20 
6.4  Binomial coefficients. Pascal's triangle.  Examples 14  421/19 (odd), 12, 13

Chapter 7 Discrete Probability (1 week)
7.1  Introduction to probability  Examples 19  451/l27 (odd) 
RK/2003; Revised Nov 2006/JP/SP Fall 2007, CO'S Fall 2008, NN 2012