# Introductory Discrete Mathematics for Computer Science

This is the first of two discrete math subjects for students of Computer Science at Wikiversity. The second course is called Discrete Mathematics for Computer Science. This page is tailored to provide you with introductory topics and problems in discrete mathematics. It is a prerequisite for Analysis of Algorithms, which is fundamental to any computing practices that require optimal performance in the face of limited resources.
Discrete mathematics is the part of mathematics devoted to the study of discrete (i.e. distinct) objects. In general, it is used whenever objects are counted, when relationships between finite (or countable) sets are studied, and when processes involving a finite number of steps are analyzed. It is important for computer science because in computing machines, information is stored and manipulated in a discrete fashion.

## Course Outline
### Logic

* Video: Boolean Algebra and formal logic (no audio)
* Video: More logic: quantifiers and predicates (no audio)
* Lesson 1.1: Introduction to boolean logic
* Lesson 1.2: Using truth tables
* Lesson 1.3: Logical AND
* Lesson 1.4: Logical OR
* Lesson 1.5: Logical XOR
* Lesson 1.6: Conditional Operator
* Lesson 1.7: Biconditional Operator
* Lesson 1.8: Compound Propositions and Useful Rules

### Set Theory

* Video: Sets
* Video: Diagonalization, functions and sums review
* Lesson 2.1: Introduction to set theory
* Lesson 2.2: Intersection
* Lesson 2.3: Union

### Functions and Relations

* Video: Functions 1, Video: Functions 2, Video: Functions 3
* Video: Equivalence Relations and Partial Orders
* Video: Equivalence Relations and Partial Orders
* Lesson 3.1: Introduction to functions

### Sums and Recurrence Relations

* Video: Basic arithmetic and geometric sums, closed forms
* Video: Solving recurrence equations
* Video: Solving recurrence equations (cont.)

### Mathematical Reasoning

* Video: Mathematical Induction
* Video: Methods of Proof
* Video: Proving Programs Correct

### Counting

Introductory counting videos
* Video: Combinations and permutations
* Video: Counting problems 1
* Video: Counting problems 2
* Video: Counting problems using combinations, distributions
* Video: Counting problems using combinations, distributions
* Video: The pigeonhole principle and examples; inclusion/exclusion theorem and examples; a combinatorial card trick
* Lesson 6.1: Introduction to counting

### Graphs

* Video: Graphs
* Video: Graphs (cont.)
* Video: Trees
* Video: Trees and graphs
* Lesson 7.1: Introduction to graphs

### Number Theory

* Video: Euclid's Algorithm
* Video: Cryptography

## Problems Sets

ADUni problem sets:
| Logic, Proofs, and Mathematical Reasoning | (Solutions, Code) |
| Sets, Functions, Big-O, Rates of Growth | (Solutions) |
| Recursion and Induction | (Solutions, Code) |
| Induction and Recurrence Equations | (Solutions) |
| Combinatorics and Counting | (Solutions, Code) |
| Combinatorics and Discrete Probability | (Solutions, Code) |
| Generating functions, Number Theory, Cryptography | (Solutions, Code) |
MIT Assignments and Solutions

## Exams

ADUni exams:
* Exam 1
* Exam 2
* Exam 3
* Final Exam
MIT Exams and Solutions
Exams are open notes, as they are in Columbia University's COMS 3203 course in Discrete Mathematics (as of Spring 2009).
* Review of Lesson 1

## Textbooks

Free textbooks:
* A Short Course in Discrete Mathematics, by Edward A. Bender and S. Gill Williamson
* Discrete Mathematics with Algorithms, by M. O. Albertson and J. P. Hutchinson
* Notes on Discrete Mathematics, by James Aspnes, which is used in the Yale University CPSC 202 class
You may also buy a copy of the following text, which is used in the Columbia University course: Discrete Mathematics and its Applications, 6th ed. by Kenneth Rosen (book homepage). Schaum's Outline of Discrete Mathematics by Lipschutz and Lipson is another possible resource.

## Instructors

* AFriedman 23:24, 11 January 2009 (UTC)

## Online Courses

Art of Problem Solving:
* Introduction to Counting and Probability
* Intermediate Counting and Probability
* Introduction to Number Theory
* Intermediate Number Theory

## Related Websites

* Extra lecture videos:
** Full set of lecture videos and notes from the University of Colorado
** MIT (ADUni) Discrete Mathematics course
* Art of Problem Solving:
** Wiki pages for number theory articles and problems, and counting articles and problems
** Alcumus - interactive problems and solutions for counting and probability
** Forum for proposing and solving math problems
* Columbia University's Spring 2009 course in discrete mathematics, offered by the Department of Computer Science
* Nic Ford's personal webpage, which contains a tutorial on logic, set theory and the foundations of mathematics
* A collection of logic resources intended for homeschoolers
* How to Write Proofs, from Professor Larry Cusick's page at California State University, Fresno
* Supplementary discrete mathematics Lecture notes by L. Lovász and K. Vesztergombi