Taught: Winter 2003
Oakland University, Michigan, USA
Description
The Discrete Mathematics course will be taught from a Computer Science perspective. Chapters were selected to match the needs of students majoring in Computer Science.
We present in chapter 1 an introduction to both prepositional, predicate logic, rules of inference, basics proof methods, as well as to sets and functions. We introduce in chapter 2, the concept of an algorithm, its properties and some fundamental concepts from number theory, including the division algorithm, prime factorization and congruences. We will cover mathematical reasoning, induction and recursion in chapter 3. We will learn in this chapter various strategies for proving theorems. We will highlight the roles of conjecture and counterexamples. In chapter 4, we will present a rich set of basic counting techniques. We will stress throughout the chapter that finding an appropriate technique and model is the substantial part of the solution of a counting problem. We will show throughout chapter 5 how to develop basic concepts of discrete probability, including conditional probability and expected values. We will show how to use these concepts to study the average case complexity of an algorithm. In chapter 7, we will cover an important discrete structure, namely:the relation. Basic concepts of graph theory and its applications will be studied in chapter 8. We will present in chapter 10 a brief introduction to Boolean algebra. We do not study Boolean algebra in a general setting, but rather we study {0,1}n and Boolean functions on this set. Finally, we will introduce some basics concepts of the theory of computation in chapter 11. We will demonstrate the connection between phrase-structure grammars and finite-state automata throughout the chapter.
Textbook
Kenneth H. Rosen, Discrete Mathematics and its Applications, Fifth Edition, Mc Graw-Hill, © 2003.
Course Materials