CMSC 250: Discrete Structures

Catalog Description: Fundamental mathematical concepts related to computer science, including finite and infinite sets, relations, functions, and propositional logic. Introduction to other proof techniques, to model and solve problems in computer science. Introduction to permutations, combinations, graphs, and trees with selected applications.

Objectives: A systematic study of mathematical concepts that are fundamental to Computer Science, with applications.

Pre or Corequisite: MATH 141.

Text: Discrete Mathematics with Applications by Susanna S. Epp, Second Edition, PWS Publishing Co., New York, 1995.

Topics:

Chapter 1: 1.1--1.4

Propositional logic, connectives, truth tables, tautologies, validity, implication, converse, inverse, negations, contradiction, digital logic circuits.

Chapter 2: 2.1--2.3

Predicate logic, universal and existential quantification, modus ponens, modus tallens, validity.

Chapter 3: 3.1, 3.5, 3.6

Direct proofs, proof by counterexample, proof by contraposition, proof by contradiction.

Chapter 4: 4.1, 4.2, 4.4, 4.5

Mathematical induction, strong induction, well orderings.

Chapter 5: 5.1--5.3

Sets, Venn diagrams, complements, Cartesian products, relations amongst sets, properties of sets, power sets.

Chapter 6: 6.1--6.4

counting, probability, permutations and combinations.

Chapter 7: 7.1, 7.3, 7.5, 7.6

Functions, one-to-one functions, onto functions, inverse functions, composition, cardinality and countability.

Chapter 10: 10.1--10.3

Relations, reflexivity, symmetry, transitivity, equivalence relations.

You will be responsible for all the material from these sections of the textbook, even if the material is not explicitly discussed in lecture.

Grading: Your final grade will be based on performance on homework, quizzes, and exams.

There will be 10 - 12 homework assignments. 2 - 3 problems (out of 1-5) will be graded each week, for a maximum of 10 points per week. Participation in each in-class ``cooperative quiz'' will count for a 1 point bonus on your homework grade.

If your homework average is less than 50%, then your course grade will be ``F'', regardless of your other grades.

If your homework average is at least 50%, then your exam and quiz average will determine your final grade.

The homework average will decide borderline cases. For example, if your exam and quiz average is close to being an ``A'' and your homework average is at least 80%, you will receive an ``A''; otherwise, a ``B''. The homework average required to push a borderline grade to a ``B'', ``C'', or ``D'' is 70%, 60%, and 55% respectively.