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,

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:

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 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. System specifications. Boolean Searches. Logic Puzzles. 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 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