Notes on Discrete Mathematics

Author : Miguel A. Lerma, Department of Mathematics, Northwestern University
Publication Date : 2005

Excerpts from the Course Description:

These notes are intended to be a summary of the main ideas in course CS 310: Mathematical Foundations of Computer Science which covers fundamental concepts and tools in discreet mathematics with emphasis on their applications to computer science. Topics include logic and Boolean circuits; sets, functions, relations, databases, and finite automata: deterministic algorithms, randomized algorithms, and analysis techniques based on counting methods and recurrence equations; trees and more general graphs.

Learning Goals:

At the end of the course, the student should be able to formulate logic expressions for a variety of applications; convert a logic expression into a Boolean circuit, and vice versa; design relational databases; design finite automata to recognize string patterns; apply, adapt, and design elementary deterministic and randomized algorithms to solve computational problems; analyze the running time of non-recursive algorithms with loops by means of counting; analyze the running time of divide-and-conquer recursive algorithms by means of recurrence equations; and use trees and graphs to formulate computational problems.

View/Download Notes on Discrete Mathematics | Course webpage