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 OutlineEdit
LogicEdit
- 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 TheoryEdit
- Lesson 2.1: Introduction to set theory
- Lesson 2.2: Intersection
- Lesson 2.3: Union
Functions and RelationsEdit
- Video: Equivalence Relations and Partial Orders
- Video: Equivalence Relations and Partial Orders
- Lesson 3.1: Introduction to functions
Sums and Recurrence RelationsEdit
- Video: Basic arithmetic and geometric sums, closed forms
- Video: Solving recurrence equations
- Video: Solving recurrence equations (cont.)
Mathematical ReasoningEdit
CountingEdit
- 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
GraphsEdit
- Lesson 7.1: Introduction to graphs
Number TheoryEdit
Problems SetsEdit
ADUni problem sets:
ExamsEdit
ADUni 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).
TextbooksEdit
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.
InstructorsEdit
- AFriedman 23:24, 11 January 2009 (UTC)
Online CoursesEdit
Art of Problem Solving:
Related WebsitesEdit
- 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