CS241 Syllabus

08/20/2012 07:47

MEDGAR EVERS COLLEGE OF CUNY

Department of Physical, Environmental and Computer Sciences

Discrete Structures (CS 241)

Adj. Lecturer: Alida Segal E-mail: asegal@mec.cuny.edu

Class Schedule : M,W 2:30 - 3:45 PM Room : A1/C07

F 3:00 - 3:50 PM Room : A1/C09

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

Grading criteria : 30% Midterm Exam, 30% Homework+Quizzes, 40% Final Exam

Back

Search site