﻿ COMPSCI 230: Discrete Mathematics for Computer Science, Summer 2013, Chittaranjan Tripathy

## Chittaranjan Tripathy

### Course Description and Syllabus

This undergraduate course covers the basic techniques for powerful thinking and solving computational problems. The emphasis of this course is on problem solving, understanding and construction of mathematical proofs, and basic mathematical structures that are extremely useful in Electrical Engineering and Computer Science. It is expected that this course with help the students build a strong mathematical foundation, enhance their problem solving skills, and help them prepare for solving challenging area-specific computational problems in Electrical Engineering, Computer Science, and other related areas. In addition, this course is a prerequisite to many other upper division undergraduate courses and graduate courses. This course covers the following topics in-depth:

• Logic and Proofs: Logical formulas, propositions, predicates, proof techniques, the well ordering principle
• Basic Mathematical Structures: Sets, Functions, Sequences, Integers, Matrices
• Algorithms: Basics of Algorithm Analysis, Number Theory, Applications of Number Theory - Cryptography
• Counting: Basics, Cardinality Rules, Recurrence Relations, Solving Recurrences, Generating Functions
• Relations: Properties, Representing Relations, Closures, Equivalence Relations, Partial Ordering and Directed Graphs
• Graphs and Trees: Representing Graphs, Isomorphism, Euler and Hamiltonian Graphs, Bipartite Graphs and Matchings, The Stable Marriage Problem, Coloring, Planar Graphs
• Probability: Basics, Conditional Probability, Random Variables, Deviation from the Mean, Random Walks
• Computability Theory: A brief overview of the basics of computability and complexity theory

• ### Announcements

• [May 15] Welcome!

### (Weekly) Lecture Schedule and Homeworks

The schedule below is tentative (clearly not final before the day of the corresponding lecture). We will plan the individual lectures on weekly basis. The individual lectures will be added/modified/re-prioritized weekly as the course progresses. Please check back often to get the latest schedule.

 Week, Lecture(L)/Recitation(R) and Date Homework Due & Exams Topics Covered/To be Covered References/Readings Week 1 L01 May 15, Wednesday — Introduction and Overview Administrativia Two Problems Cutting a Pizza Lighting the rooms Lecture 01 [LLM: 1.1], [R: 1.1] L02 May 16, Thursday — Propositional Logic Truth Tables Lecture 02 [LLM: 1.1, 3.1-3.5] [R: 1.1] R03 May 17, Friday — Propositional Logic Applications Logic Gates Propositional Equivalence Satisfiability Lecture 03 [LLM: 1.1, 3.1-3.5] [R: 1.2-1.3] Week 2 L04 May 20, Monday — Predicate Logic Quantifiers Nesting of Quantifiers Lecture 04 [LLM: 1.2,3.6] [R: 1.4-1.5] R05 May 21, Tuesday — Rules of Inference Lecture 05 [LLM: 1.3-1.4] [R: 1.6] L06 May 22, Wednesday — Proofs Direct Proof Proof by Contraposition Proof by Contradiction Proof by Cases False Proofs, Counter Examples, Conjectures The Well Ordering Principle Lecture 06 [LLM: 1.3-1.9, 2] [R: 1.7-1.8] L07 May 23, Thursday Homework 01 out Structures Sets and Operations on Sets Functions, Binary Relations Lecture 07 [LLM: 4.1-4.4] [R: 2.1-2.3] R08 May 24, Friday — Sequences and Summations Finite Sets Matrices Infinite Sets Lecture 08 A [LLM: 2] [R: 2.4-2.6] Lecture 08 B [LLM: 7] [R: 2.5] Week 3 May 27, Monday — Memorial Day L09 May 28, Tuesday — Induction Ordinary Induction Strong Induction Lecture 09 [LLM: 5.1-5.3] [R: 5.1-5.2] L10 May 29, Wednesday — Induction Continued Recursive Definitions and Structural Induction Recursive Algorithms Lecture 10 [LLM: 6] [R: 5.3-5.4] L11 May 30, Thursday Homework 01 due Homework 02 out Algorithms Models of Computation Setting up Recurrences Binary Search Counting the Number of Reflected Rays Fibonacci Number Complexity of Algorithms Lecture 11 [LLM: ] [R: 3] R12 May 31, Friday — Algorithms Continued Asymptotic Notation Lecture 12 [LLM: ] [R: 3] Week 4 L13 June 03, Monday — Solving Recurrences Substitution Method The Recursion Tree Method The Master Method Examples Lecture 13 [LLM: ] [R: 3] L14 June 04, Tuesday — Solving Linear Recurrences Linear Homogeneous Recurrences Linear Inhomogeneous Recurrences Lecture 14 [LLM: ] [R: 3] L15 June 05, Wednesday — Counting The Sum Rule The Product Rule The Subtraction (2-Set Inclusion-Exclusion) Rule The Division Rule and Tree DiagramsThe Pigeonhole (aka Dirichlet drawer) Principle Some Applications Lecture 15 [LLM: 14] [R: 6.2] L16 June 06, Thursday Homework 02 due Homework 03 out The Pigeonhole (aka Dirichlet drawer) Principle (Continued) More Applications Lecture 16 [LLM: 14] [R: 6.2] R17 June 07, Friday — Midterm 01 [Exam Information and Cheat Sheet] Week 5 L18 June 10, Monday — Counting Permutations and Combinations Binomial Theorems and Binomial Coefficients Lecture 18 [LLM: ] [R: 6.3, 6.4] L19 June 11, Tuesday — Counting Permutations with RepetitionThe Inclusion-Exclusion Principle Lecture 19 [LLM: ] [R: 6.5] L20 June 12, Wednesday — Introduction to Discrete Probability Conditional Probability Independence Lecture 20 A [LLM: 16, 17] [R: 7] Lecture 20 B [LLM: 18] [R: 7] L21 June 13, Thursday — Random Variables and Expectations Distributions Uniform BernoulliBinomialGeometric Variance Lecture 21 A [LLM: 18] [R: 7] Lecture 21 B [LLM: 18] [R: 7] R22 June 14, Friday Homework 03 due Homework 04 out Bayes' Theorem and Applications Lecture 22 [LLM: 18] [R: 7] Week 6 L23 June 17, Monday — Midterm 02 [Exam Information and Cheat Sheet] L24 June 18, Tuesday — Relations Properties of Relations Representations Closures Equivalence Relations [R: 9.1, 9.3, 9.4 (NO Warshall's algo), 9.5] R25 June 19, Wednesday — Number Theory Lecture-Number-Theory [R: 4.1 4.3] L26 June 20, Thursday — Number Theory [R: 4.4] R27 June 21, Friday — Graph Theory [R 10.1-10.4] Week 6 L28 Jun 24, Monday Homework 04 due Graph Theory [R 10.1-10.4]

### Solutions to Homework Assignments and Exam Problems

Graded homeworks and exams, and sample solutions will be provided in class.

### Readings: Reference Books, Lecture Notes and Videos

[Ve] D. J. Velleman. How to Prove It: A Structured Approach. 2nd Edition; Cambridge University Press; 2006. (a nice book on logic and proofs)