# Introductory Discrete Mathematics for Computer Science

Educational level: this is a tertiary (university) resource. |

Subject classification: this is an information technology resource. |

Subject classification: this is a mathematics resource. |

Completion status: this resource is ~25% complete. |

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

edit### Logic

edit- 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

edit**Lesson 2.1:**Introduction to set theory**Lesson 2.2:**Intersection**Lesson 2.3:**Union

### Functions and Relations

edit- Video:
*Equivalence Relations and Partial Orders* - Video:
*Equivalence Relations and Partial Orders* **Lesson 3.1:**Introduction to functions

### Sums and Recurrence Relations

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

### Mathematical Reasoning

edit### Counting

edit- 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

edit**Lesson 7.1:**Introduction to graphs

### Number Theory

edit## Problems Sets

editADUni problem sets:

## Exams

editADUni exams:

Exam 1 |

Exam 2 |

Exam 3 |

Final Exam |

Exams are open notes, as they are in Columbia University's COMS 3203 course in Discrete Mathematics (as of Spring 2009).

## Textbooks

editFree 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

edit- AFriedman 23:24, 11 January 2009 (UTC)

## Online Courses

editArt of Problem Solving:

## Related Websites

edit- Extra lecture videos:
- Full set of lecture videos and notes from the University of Colorado
- MIT (ADUni) Discrete Mathematics course

- Art of Problem Solving:
- 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