MEDGAR EVERS COLLEGE of CUNY
Department of Physical, Environmental and Computer Sciences
Department Office, Carroll 417 - Phone 718-270-6453
“Time, Effort, Integrity”
Discrete Structures (CS 241)
Course Syllabus - 3 class hours, 1 lab hour, 3 credits
Course Description: 3 credits, 3 class hours, 1 lab hour
The objective of this course is to introduce the elements of discrete mathematics systems pertinent to the field of computer science. Through computer programming examples, exercises and case studies, students are taught the following mathematical concepts: sets and binary relations, functions, first-order logic, proof techniques, algebraic systems, graph theory, vectors and matrices, elementary probability theory, combinatorial computing and counting arguments. Definitions and analysis of algorithms are also introduced.
Prerequisite: CS 15l
Required Textbook: Mathematical Structures for Computer Science: A Modern Treatment of Discrete Mathematics (5/E) July 2002 Judith L. Gersting ISBN: 0716743582 Publisher: W. H. Freeman
Course Requirements: All students have the responsibility to arrive on time, attend class regularly, and to participate fully in the work of the course. Additionally, students are not to work on other materials in class. Assigned readings, problems and programs should be completed before class. Students are also responsible for the end-of-section Techniques contained on the Web site for the textbook ( HYPERLINK "http://www.whfreeman.com/gersting" www.whfreeman.com/gersting). These Techniques include compressed audio files that contain a first-person stream-of-consciousness thought process about each step of the solution to the problem. These problems will be assigned to reinforce the concepts presented in class. Unless you own or have access to equivalent hardware and software, plan on spending a lot of time on campus.
Grading Procedure: The final grade will be determined objectively by using a weighted average along with the following weighted areas: computer programs, chapter examinations, homework assignments, and the final examination. Check with the college catalog for information regarding the official grading policy. Note that missed chapter examinations cannot be made-up. The lowest score from all chapter examinations will be dropped, before calculating the final average, provided all class examinations are taken. Programming projects submitted after the stated deadline will receive a reduced grade. Programming projects submitted more than three class meetings, or ten days -- which ever is shorter -- after the stated deadline will not be accepted, and a grade of F will be recorded for that project.
Academic Requirements and Regulations: Students who officially withdraw from a course between the 4th through the 8th week receive a grade of W, which is not counted in computing the grade point average. Courses officially dropped after the 8th week of class will appear as a WF and count as an F grade. INC (Incomplete) or ABS (absent) grades will only be given to students who are passing the course.
Honor Code and Plagiarism: Students are required to sign and adhere to the departmental honor pledge. Check with the department for a copy of the pledge.
CUNY Proficiency Examination (CPE)
The CPE is a graduation requirement. All students between 45-60 credits are required to sit for and pass the CPE. You have only three chances to pass this examination. Each missed scheduled examination after the 45 credit mark counts as a failure. For more information about this requirement, contact the Medgar Evers College CPE Liaison.
MEDGAR EVERS COLLEGE of CUNY
Department of Physical, Environmental and Computer Sciences
Discrete Structures (CS 241)
Course Outline
Chapter/Sections Topics
Week 1FORMAL LOGIC
(1.1 to 1.2)Statements, Symbolic Representation, and Tautologies; Propositional Logic;Quantifiers, Predicates, and Validity
Weeks 2FORMAL LOGIC
(1.3 to 1.4)Quantifiers, Predicates, and Validity; Predicate Logic
Weeks 3FORMAL 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, RECURSION, AND ANALYSIS OF ALGORITHMS
(2.3 to 2.4)More on Proof of Correctness; Recursion and Recursive Relations
Weeks 6 PROOFS, RECURSION, AND ANALYSIS OF ALGORITHMS
(2.5)Analysis of Algorithms
Weeks 7SETS, COMBINATORICS, AND PROBABILITY
(3.1 to 3.2)Sets; Counting Principals
Weeks 8SETS, COMBINATORICS, AND PROBABILITY
(3.3 to 3.4)Principle of Inclusion and Exclusion: Pigeonhole Principle; Permutations and Combinations
Weeks 9SETS, COMBINATORICS, AND PROBABILITY
(3.5)Discrete Probability
Weeks 10RELATIONS, FUNCTIONS, AND MATRICIES
(4.1 to 4.2)Relations and Partial Orderings; Topological Sorting
Weeks 11RELATIONS, FUNCTIONS, AND MATRICIES
(4.4 to 4.5)Review of the Properties and Order of Magnitude of Functions; Matrices
Weeks 12GRAPHS AND TREES
(5.1 to 5.2)Graphs and Their Representations; Trees and Their Representations
Weeks 13GRAPHS AND TREES
(5.3 to 5.4)Decision Trees; Huffman Codes
Weeks 14MODELING ARITHMETIC, COMPUTATION, AND LANGUAGES
(8.1 to 8.2)Algebraic Structures; Finite-State Machines
Weeks 15MODELING ARITHMETIC, COMPUTATION, AND LANGUAGES
(8.2 to 8.3)Finite-State Machines; Turing Machines
