CECS 228

Discrete Structures With Computer Science Applications

Course Meeting Time and Location

MW 12-12:50PM ECS-302

MW 1-2:15 VEC-518

Instructor

Dr. Mehrdad Aliasgari

Email: mehrdad.aliasgari at csulb.edu

Office: ECS-539

Office hours: TuTh 11am-12pm Wed: 6:45-7:45pm

Required Textbook

 K. Rosen,  Discrete Mathematics and its Applications , Seventh Edition, McGraw-Hill, 2011, ISBN-10: 0073383090, ISBN-13: 978-0073383095

Course Description

This course provides an introduction to the fascinating world of discrete mathematics in its relation to solving problems in computer science and engineering. The topics covered include set theory, functions, logic, relations, trees, recursion, graphs, integers, mathematical proofs, and counting.

Course Objectives

• An ability to: model statements and systems using propositional and predicate logic; translate between English sentences and propositional/predicate logic; determine the consistency of a set of logical statements; solve logic puzzles from a set of given statements.
• An ability to: define a set and perform set operations; find the Cartesian product of sets, and the power set of a given set; represent a set as a binary vector, and define vector/set operations; recognize well-known set identities, and determine the relationship between two sets (equal, subset, etc.); identify when a relationship between two sets represents a function; find the domain and range of a function, and determine whether or not it is 1-1, onto, or both; find composite and inverse functions; use special functions including the floor and ceiling functions; understand and write recursive definitions and algorithms; determine the cardinality of a set using the sum rule, product rule, principle of inclusion-exclusion, generalized pigeonhole principle, permutations, and combinations; solve linear recurrence relations; represent a binary relation using set notation (ordered pairs), a directed graph, and a matrix.
• Understand n-ary relations and their applications; determine if a given relation is reflexive, irreflexive, symmetric, anti-symmetric, asymmetric, and transitive; determine if a relation on a given set is an equivalence relation; determine if a relation on a given set is a partial ordering; apply equivalence relations and partial orderings to some common problems; represent a graph using an adjacency list, an adjacency matrix, and an incidence matrix; recognize some special graphs including: complete graphs, cycles, wheels, n-cubes, bipartite graphs; use simple properties to rule out two graphs being isomorphic; determine the connectivity of a given graph; recognize a tree, and compute various properties of a tree including internal vertices, leaves, and height.
• An ability to: apply a rule of inference in an argument; construct an argument using rules of inference to show the conclusion is valid; find all possible conclusions one can deduce from a set of statements using rules of inference; identify fallacies in an argument; construct a mathematical proof using mathematical induction, cases, the direct method, the indirect method, and proof by contradiction; prove the correctness of recursive algorithms and definitions using mathematical induction

Course Topics

• Foundations: logic, propositional equivalences, predicates and quantifiers, sets, lists, spaces, objects, functions and their implementation.
• Recursion: recursive functions and recursive structures, implementing recursive functions over integers, strings, lists, and general recursive structures.
• Mathematical Reasoning: rules of inference and fallacies, mathematical induction, mathematical proof techniques.
• Counting: counting and combinations, permutations, pigeon-hole principle.
• Basic Discrete Structures: relations, applications and representations, equivalence relations, partial orderings, graphs, graph terminology, graph applications, connectivity in graphs, trees.

Grading

Your final grades are comprised of the following components: Class participation 10%, Problem sets 25%, Quizzes 10% Midterm 1 15% Midterm 2 15%and Final Exam 25%.

Exam Schedule

• Midterm 1: TBA
• Midterm 2: TBA
• Final Exam: Friday, December 13 12:30PM-2:30PM

Academic Integrity and Dishonesty

Please read here.

Emergency Preparedness Instructions

Please read here.