CS 215-3
Discrete Mathematics
Catalog Description
Introduction to topics from discrete mathematics relevant to the study of computer science including: binary and hexadecimal number systems, sets, logic and truth tables, functions and relations, matrix operations, combinations, permutations, counting techniques, recurrence relations, boolean algebra, simple combinational circuits, simplification techniques.
Prerequisite:
Mathematics 111 or equivalent with a grade of C or better.
Objectives
1. To lay the mathematical foundation for further study in computer science.
2. To have the students develop a greater proficiency in basic mathematical concepts that are important in computer science at an early stage in their undergraduate education.
3. To treat these fundamental topics early in the computer science curriculum so they can be presupposed in subsequent courses.
4. To show where and how these fundamental topics impact the study of computer science. The relevance of the topics to computer science will be discussed through examples from various areas of computer science.
Organization
The course meets for three lecture hours per week. Topic coverage is given in terms of lecture hours. The following course outline is not necessarily intended as a sequential ordering. There will be at least five projects during the course of the semester. A final project that will be presented could be a group project.
Course Outline
| The following is not necessarily intended as a sequential ordering. | Lectures | |
| 1. | Logic
Propositional logic, truth tables Conjunction, disjunction, negation Conditional, inverse, converse, contrapositive Logical equivalence Quantification: existential and universal, nesting Counterexample Methods of proof: direct, indirect, contradiction Example: Logic Programming |
6 |
| 2. | Sets
Definitions: equality, subset, cardinality, power set n-tuple, Cartesian product, empty set, disjoint sets, universe Operations: union, intersection, difference, complement Principle of inclusion-exclusion Set identities Example: Computer representation of sets |
2 |
| 3. | Functions and relations
Definitions: function, one-to-one functions, onto functions, domain range, inverse function, composition Representing the graph of a function Common functions: floor, ceiling, factorial, absolute value, polynomial functions Horner's method Properties of relations: reflexive, symmetric, transitive, composite of two relations Equivalence relations Equivalence classes and partitions n-ary relations Examples: Growth curves, databases and relations |
4 |
| 4. | Integers
Definition of division Definition of a prime number and a composite Fundamental theorem of arithmetic Prime factorizations The division algorithm Concept of the div and mod operators Greatest common divisor Least common multiple Modular arithmetic Representations of integers in decimal, binary, and hexadecimal Conversion from one base to another Horner's method Euclidean algorithm Examples: Pseudo random numbers, cryptography |
4 |
| 5. | Matrices
Definitions: identity matrix, sum, product, transpose symmetric matrix Example: Representation of relations using matrices |
2 |
| 6. | Sequences and Summations
Arithmetic progression Geometric progression Summation notation Common summation |
2 |
| 7. | Proof by Mathematical Induction
Mechanics of a proof Validity of a proof by mathematical induction |
2 |
| 8. | Counting Techniques
Product rule Sum rule Principle of inclusion-exclusion Use of tree diagrams Permutations Combinations Binomial Theorem Pascal's triangle Permutations with repetitions Example: Generating permutations and combinations |
3 |
| 9. | Recurrence Relations
Definitions Common examples: compound interest, Fibonacci numbers, Tower of Hanoi Solving recurrence relations Example: Divide and conquer recurrence relations |
3 |
| 10. | Boolean Algebra
Boolean Algebra and Logic Gates Simplification of Boolean Functions Simple Combinational Circuits |
12 |
| Total | 40 | |