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
COREQUISITES: ENG 02 and RDL 02, if
required
TEXT: Discrete
Mathematics and its Applications, Seventh Edition,
by Kenneth H. Rosen, published by McGraw-Hill 2012
ISBN: 978-0-07-3338309-5
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:
Chapters and sections |
Suggested in-class examples |
Suggested Homework |
Chapter 1 The Foundations: Logic and Proofs (5
weeks)
1.1 |
Propositional Logic. |
Examples All |
12-16/1, 3, 7, 9, 13, 17, 19, 25, 27, 31, 37, 43 |
1.2 |
Translating English
sentences. |
Examples 1-8 |
22-24/5, 7, 11, 13, 17, 21 |
1.3 |
Propositional
Equivalences |
Examples All |
35/1-21 (odd) |
1.4 |
Predicates and
Quantifiers |
Examples 1-18, 20-24, 28 |
53 /1-27 (odd), 31, 33, 35, 53, 55 |
1.5 |
Nested quantifiers. |
Examples 1-15 |
64/1, 3, 5, 9, 15, 25, 27, 33 |
1.6 |
Rules of Inference.
Fallacies. |
Examples 1-11 |
78/1-9 (odd) |
Chapter 2 Basic Structures: Sets, Functions,
Sequences, Sums (3 weeks)
2.1 |
Sets, power sets,
Cartesian products. |
Examples 1-19 |
125/l-9 (odd), 15-23 (odd), 27, 31, 35 |
2.2 |
Set operations. Set
identities. |
Examples 1-15 |
136/1, 3, 13, 25 |
2.2 |
Computer
representations of sets. |
Examples 18, 19, 20 |
137/52-55(all) |
2.3 |
One-to-one and onto
functions. |
Examples 1-17 |
152/1-7 (odd) |
2.3 |
Inverse and composition
of functions. Graphs. Some important functions. |
Examples 18-30 |
152/9, 12, 13, 15, 23, 31, 36, 43 |
2.6 |
Matrix Arithmetic.
Transposes and powers of matrices. Zero-one matrices. |
Examples 1-9 |
183/1, 3, 5, 19, 20, 26, 27 |
Chapters and sections |
Suggested in-class examples |
Suggested Homework |
Chapter 3 Algorithms (1 week)
3.1 |
Algorithms. Pseudocode. Searching algorithms |
Examples 1-3 |
202/1, 3, 5 |
3.1 |
Sorting. Greedy
algorithms. |
Examples 4-6 |
202/2, 7, 13, 19, 35 |
Chapter 4 Number Theory and Cryptography (2
weeks) |
|||
4.1 |
Division. The division
algorithm. |
Examples 1-4 |
244/1, 9 |
4.1 |
Modular arithmetic. |
Examples 5-6 |
244/21, 29 |
4.5 |
Applications of
congruences (hashing functions). Pseudorandom numbers. |
Examples 1-3 |
292/3, 5 |
4.3 |
Primes. Fundamental
Theorem of Arithmetic. The Infinitude of Primes. The Euclidean
Algorithm. |
Examples 1-5, 16 |
272/3, 15, 17, 33 |
4.2 |
Representations of
integers. |
Examples 1-7 |
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 1-14 |
396/l-17 (odd) |
6.1 |
More complex counting problems. Exclusion
inclusion principle. Tree
diagrams. |
Examples 15-23 |
396/19-33 (odd) |
6.3 |
Permutations and combinations. |
Examples 1-15 |
413/1-19 (odd), 20 |
6.4 |
Binomial coefficients. Pascal's triangle. |
Examples 1-4 |
421/1-9 (odd), 12, 13 |
Chapter 7 Discrete Probability (1 week)
7.1 |
Introduction to
probability |
Examples 1-9 |
451/l-27 (odd) |
Academic Integrity
Academic
dishonesty (such as plagiarism and cheating) is prohibited at Bronx Community
College and is punishable by penalties, including failing grades, dismissal and
expulsion. For additional information and the full policy on Academic
Integrity, please consult the BCC College Catalog.
Accommodations/Disabilities
Bronx Community College
respects and welcomes students of all backgrounds and abilities. In the event
you encounter any barrier(s) to full participation in this course due to the
impact of a disability, please contact the disAbility Services Office as soon
as possible this semester. The disAbility Services specialists will
meet with you to discuss the barriers you are experiencing and explain the
eligibility process for establishing academic accommodations for this course.
You can reach the disAbility Services Office at: disability.services@bcc.cuny.edu, Loew Hall, Room 211, (718) 289-5874.
RK/2003; Revised Nov
2006/JP/SP Fall 2007, CO'S Fall 2008, NN 2012
Last updated 01/14/2019, 07/17/2019 for typo