Search This Blog

Loading...

Discrete Mathematics Study Materials

Discrete Mathematics

Lectures Ppt

Click on the blue colored links to download the lectures.

Course Description

This course covered the mathematical topics most directly related to computer science. Topics included: logic, relations, functions, basic set theory, countability and counting arguments, proof techniques, mathematical induction, graph theory, combinatorics, discrete probability, recursion, recurrence relations, and number theory. Emphasis will be placed on providing a context for the application of the mathematics within computer science. The analysis of algorithms requires the ability to count the number of operations in an algorithm. Recursive algorithms in particular depend on the solution to a recurrence equation, and a proof of correctness by mathematical induction. The design of a digital circuit requires the knowledge of Boolean algebra. Software engineering uses sets, graphs, trees and other data structures. Number theory is at the heart of secure messaging systems and cryptography. Logic is used in AI research in theorem proving and in database query systems. Proofs by induction and the more general notions of mathematical proof are ubiquitous in theory of computation, compiler design and formal grammars. Probabilistic notions crop up in architectural trade-offs in hardware design.

Text: Discrete Mathematics and its Applications, Rosen.

Syllabus

Week 1: Introduction, Proofs, Logic, Boolean Algebra and applications, Sets and applications, Basic sums and functions.

Reading: Rosen 1.1-1.8, 3.1-3.2, 5.5, 9.1-9.3 How to Read Mathematics (http://academics.stonehill.edu/compsci/History_Math/math-read.htm), Polya, How to Solve It.

Lecture 1: What kinds of problems are solved in discrete math? What are proofs? Examples of proofs by contradiction, and proofs by induction: Triangle numbers, irrational numbers, and prime numbers. (3.1-3.2)

Lecture 2: Boolean Algebra and formal logic. Applications in algorithms, complexity theory, AI, digital logic design and computer architecture. (1.1-1.2, 9.1-9.3)

Lecture 3: More logic: quantifiers and predicates. Sets, operations on sets, using logic to prove identities on sets. (1.3-1.5)

Lecture 4: Sets. Applications in counting (the inclusion-exclusion theorem), theory of computation and data structures. (5.5)

Lecture 5: Growth rate of functions, Big-O notation, Countability, 1-1 correspondence. Applications to algorithms and theory of computation. (1.6-1.8)

Week 2: Induction, recursion, recurrence equations, graphs.

Reading: Rosen 3.3-3.5, 5.1-5.3, 7.1-7.5

Lecture 1: Basic arithmetic and geometric sums, closed forms. Compound Interest – a simple recurrence. Binary search – recursion, induction and complexity. Towers of Hanoi – recursion, induction, and graphs. (3.3-3.5)

Lecture 2: Chinese rings puzzle – Grey codes, graphs, hypercubes, Hamiltonian and Euler circuits, planar graphs, Euler’s theorem. (7.1-7.5)

Lecture 3: Solving recurrence equations – repeated substitution, the Master Theorem with applications to algorithms, change of variable technique. (5.1, 5.3)

Lecture 4: Solving recurrence equations – guessing and proving correct by induction, linear homogeneous types. The Josephus Problem. (5.2)

Lecture 5: Mathematical induction – a flexible and useful tool. Many examples and the idea of strong induction. (3.2)

Week 3: Counting and discrete probability. Combinations, permutations, pigeonhole principle, inclusion/exclusion revisited.

Reading: Rosen 4.1-4.7, 5.6, How to Read Math (re-read from week 1)

Lecture 1: Combinations and permutations. Pascal’s triangle and binomial coefficients. (4.1, 4.3)

Lecture 2: Counting problems using combinations, distributions and permutations. (4.6)

Lecture 3: The pigeonhole principle and examples. The inclusion/exclusion theorem and advanced examples. A combinatorial card trick. (4.2, 4.7, 5.6)

Lecture 4: Discrete probability, the birthday paradox, and many examples. (4.4)

Lecture 5: Conditional probability, and more counting. Generating Functions. (4.5, 5.4)

Week 4: Generating functions, Number theory for cryptography and computer science, equivalence relations, partial orders, trees.

Reading: Rosen 2.1-2.5, 5.4, 6.1-6.6, 8.1-8.2

Lecture 1: Generating functions. (5.4)

Lecture 2: Partial orders, trees and equivalence relations. Applications to algorithms. (8.1-8.2)

Lecture 3: Primes, Greatest Common Divisors and the Euclidean Algorithm. (2.1-2.5)

Lecture 4: The two-jug puzzle as demonstrated by Bruce Willis in Die Hard III.

Lecture 5: Congruences and Fermat’s little theorem. Applications to Cryptography. (6.1-6.6)

Lecture Notes

Lecture_Notes.doc Lecture_Notes.pdf

Lecture Videos

11-01-00: What kinds of problems are solved in discrete math? 11-02-00: Boolean Algebra and formal logic 11-03-00: More logic: quantifiers and predicates 11-06-00: Sets 11-07-00: Diagonalization, functions and sums review 11-08-00: Basic arithmetic and geometric sums, closed forms. 11-09-00: Chinese rings puzzle 11-10-00: Solving recurrence equations 11-13-00: Solving recurrence equations (cont.) 11-14-00: Mathematical induction 11-15-00: Combinations and permutations 11-16-00: Counting Problems 11-17-00: Counting problems 11-20-00: Counting problems using combinations, distributions 11-21-00: Counting problems using combinations, distributions 11-22-00: The pigeonhole principle and examples. The inclusion/exclusion theorem and advanced examples. A combinatorial card trick. 11-26-00: Equivalence Relations and Partial Orders 11-27-00: Euclid's Algorithm 11-27-00: Recitation -- a combinatorial card trick 11-28-00: Cryptography

Problem Sets

Card_Trick_Problem_Set.doc Card_Trick_Problem_Set.pdf Card_Trick_Problem_Set_Solutions.pdf Card_Trick_Problem_Set_Solutions.scm Card_Trick_Problem_Set_Solutions.tex Card_Trick_Problem_Set_Solutions_Trial_Data.txt Problem_Set_01.doc Problem_Set_01.pdf Problem_Set_01.tex Problem_Set_01_Solutions.pdf Problem_Set_01_Solutions.tex Problem_Set_01_Solutions_Code.scm Problem_Set_02.doc Problem_Set_02.pdf Problem_Set_02.tex Problem_Set_02_Solutions.pdf Problem_Set_02_Solutions.tex Problem_Set_03.doc Problem_Set_03.pdf Problem_Set_03.tex Problem_Set_03_Solutions.pdf Problem_Set_03_Solutions.tex Problem_Set_03_Solutions_Code.scm Problem_Set_04.doc Problem_Set_04.pdf Problem_Set_04.tex Problem_Set_04_Plus.doo Problem_Set_04_Plus.pdf Problem_Set_04_Solutions.pdf Problem_Set_04_Solutions.tex Problem_Set_05.doc Problem_Set_05.pdf Problem_Set_05_Solutions.pdf Problem_Set_05_Solutions.tex Problem_Set_05_Solutions_Code.scm Problem_Set_06.doc Problem_Set_06.pdf Problem_Set_06_Solutions_Code.scm Problem_Set_07.doc Problem_Set_07.pdf Problem_Set_07_Solutions.txt Problem_Set_07_Solutions_Code.scm

Exams

Exam_01.doc Exam_01.pdf Exam_02.doc Exam_02.pdf Exam_03.pdf Final_Exam.doc Final_Exam.pdf

Links

Textbook site Interactive Mathematics Miscellany and Puzzles The Euclidean Algorithm

No comments:

Post a Comment