Open Educational Resources (OER) are freely accessible, openly licensed documents and media that are useful for teaching, learning, educational, assessment and research purposes.

This course covers elementary discrete mathematics for computer science and engineering. It emphasizes mathematical definitions and proofs as well as applicable methods. Topics include formal logic notation, proof methods; induction, well-ordering; sets, relations; elementary graph theory; integer congruences; asymptotic notation and growth of functions; permutations and combinations, counting principles; discrete probability. Further selected topics may also be covered, such as recursive definition and structural induction; state machines and invariants; recurrences; generating functions.

30 hours of lectures.

25 lectures.

Assignments, recitations and exams with solutions.

Tom Leighton is a Professor of Applied Mathematics at the Massachusetts Institute of Technology (MIT), and has served as the Head of theAlgorithms Group in MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) since its inception in 1996.

Prof. Leighton is one of the world's preeminent authorities on algorithms for network applications. He holds numerous patents involving cryptography, digital rights management, and algorithms for networks, and has published more than 100 research papers in the areas of parallel algorithms and architectures, distributed computing, communication protocols for networks, combinatorial optimization, probabilistic methods, VLSI computation and design, sequential algorithms, and graph theory. He is also the author of two books, including a leading text on parallel algorithms and architectures. Source (text and image): CSAIL Bio page.

Marten has over 10 years research experience in system security both in academia and industry: He worked for two and a half years at RSA Laboratories in cybersecurity. Prior to RSA he was a research scientist at MIT CSAIL working together with Prof. Srini Devadas with an emphasis on processor architectures that offer strong security guarantees; most notably, this collaboration led to the design of Aegis, the first single-chip secure processor that verifies integrity and freshness of external memory, and led to the introduction of the first circuit realizations of Physical Unclonable Functions (PUFs) resulting in a commercialization by Verayo and Intrinsic-ID. His work received the NYU-Poly AT&T Best Applied Security Paper Award, 3rd place, 2012, and the ACSAC’02 outstanding student paper award.

Prior to working in system security he was a research scientist at the digital signal processing group at Philips Research where he became the lead inventor of the error correcting codes used in Blu-ray disc. He received a Ph.D. in mathematics, a M.S. in mathematics, and a M.S. in computer science from Eindhoven University of Technology. Source: ucon faculty pages

6.042J Mathematics for Computer Science, Fall 2010. (MIT OpenCourseWare: Massachusetts Institute of Technology), by Leighton, Tom, and Marten Dijk is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.Based on a work at http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010.

#### Lecture 1: Introduction and Proofs

#### Lecture 2: Induction

#### Lecture 3: Strong Induction

#### Lecture 4: Number Theory I

#### Lecture 5: Number Theory II

#### Lecture 6: Graph Theory and Coloring

#### Lecture 7: Matching Problems

#### Lecture 8: Graph Theory II: Minimum Spanning Trees

#### Lecture 9: Communication Networks

#### Lecture 10: Graph Theory III

#### Lecture 11: Relations, Partial Orders, and Scheduling

#### Lecture 12: Sums

#### Lecture 13: Sums and Asymptotics

#### Lecture 14: Divide and Conquer Recurrences

#### Lecture 15: Linear Recurrences

#### Lecture 16: Counting Rules I

#### Lecture 17: Counting Rules II

#### Lecture 18: Probability Introduction

#### Lecture 19: Conditional Probability

#### Lecture 20: Independence

#### Lecture 21: Random Variables

#### Lecture 22: Expectation I

#### Lecture 23: Expectation II

#### Lecture 24: Large Deviations

#### Lecture 25: Random Walks

#### Assignments

#### Recitations

#### Exam(s)