MEDGAR EVERS COLLEGE OF CUNY
Department of Physical, Environmental and Computer Sciences
Discrete Structures (CS 241) Syllabus
Adj. Lecturer: Alida Segal E-mail: asegal@mec.cuny.edu
Course Web Site: csi241.webnode.com
Class Schedule : T,TH 2:00 - 3:40 PM Room : A1/C09
CS 241 course 3 credits, 4 class hours
Prerequisite: CS 151
Textbook: Mathematical Structures for Computer Science by Judith L. Gersting, University of Hawaii,
Hilo Sixth Edition ©2007 ISBN-10: 0-7167-6864-X ISBN-13: 978-0-7167-6864-7
Course Outline
Chapter/Sections Topics
Week 1 FORMAL LOGIC
(1.1 to 1.2) Statements, Symbolic Representation, and Tautologies; Propositional Logic;
Quantifiers, Predicates, and Validity
Weeks 2 FORMAL LOGIC
(1.3 to 1.4) Quantifiers, Predicates, and Validity; Predicate Logic
Weeks 3 FORMAL LOGIC
(1.5 to 1.6) Logic Programming; Proof of Correctness
Weeks 4 PROOFS, RECURSION, AND ANALYSIS OF ALGORITHMS
(2.1 to 2.2) Proof Techniques; Induction
Weeks 5 PROOFS (2.1 to 2.2) More Induction Examples
Weeks 6 PROOFS, RECURSION, AND ANALYSIS OF ALGORITHMS
(2.3 to 2.4) More on Proof of Correctness; Recursion and Recursive Relations
Weeks 7 SETS, COMBINATORICS, AND PROBABILITY
(3.1 to 3.2) Sets; Counting Principals
Weeks 8 SETS, COMBINATORICS, AND PROBABILITY
(3.3 to 3.4) Principle of Inclusion and Exclusion: Pigeonhole Principle;
Permutations and Combinations
Weeks 9 SETS, COMBINATORICS, AND PROBABILITY
(3.5) Discrete Probability
Weeks 10 RELATIONS, FUNCTIONS, AND MATRICIES
(4.1 to 4.2) Relations and Partial Orderings; Topological Sorting
Weeks 11 RELATIONS, FUNCTIONS, AND MATRICIES
(4.4 to 4.5) Review of the Properties and Order of Magnitude of Functions; Matrices
Weeks 12 GRAPHS AND TREES
(5.1 to 5.2) Graphs and Their Representations; Trees and Their Representations
Weeks 13 GRAPHS AND TREES (5.3 to 5.4) Decision Trees; Huffman Codes
Weeks 14 MODELING ARITHMETIC, COMPUTATION, AND LANGUAGES
(8.1 to 8.2) Algebraic Structures; Finite-State Machines
Weeks 15 MODELING ARITHMETIC, COMPUTATION, AND LANGUAGES
(8.2 to 8.3) Finite-State Machines; Turing Machines
CS 241 Learning objectives and outcomes
Basic Logic
Sets, Relations, Functions
Proof Techniques
Basics of Counting
Discrete Probability
Graphs and Trees
Grading criteria : 30% Midterm Exam, 30% Homework+Quizzes, 40% Final Exam