Chittaranjan Tripathy 
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 areaspecific 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 indepth:
Instructor 
Chittaranjan Tripathy (please call me Chittu) email: chittu AT cs dot duke dot edu 
Lectures 
Allen 103, Mon.Tue.Wed.Thu.Fri 9:30AM10:45AM 
Recitations 
We will use one of the lectures as recitation. 
Office Hours 
Chittu: LSRC D301, Tue.Wed 11:00AM12:00Noon 
Textbooks 
Required: [R] Discrete Mathematics and its Applications, 7th Edition, 2011. Kenneth H. Rosen. Optional but HighlyRecommended (and free PDF!): [LLM] Mathematics for Computer Science, 2012. Eric Lehman, F. Thomson Leighton, Albert R. Meyer. Some of the lectures will be based on this book! 
Workload and Grading 
Class Interaction. [5 points] Weekly Homework Assignments. [30 points] First Inclass Closedbook Midterm Exam. [15 points] Second Inclass Closedbook Midterm Exam. [15 points] Inclass Closedbook Final Exam. [35 points] 
Late Homework Policy 
No credits for late submissions. 
Collaboration on Homework Assignments and the Duke University Honor Code 
You will learn the most if you solve as many extra problems as you can. All homework assignment solutions submitted for grading purpose should be your own. You are encouraged to form small groups to discuss and solve the problems from the textbooks or homework assignments, but you must write up your own solutions. Please indicate clearly in your solution sheet who you collaborated with, or what other written material (not listed in the course website) you have consulted, in order to solve each homework problem. You may not consult solutions on the internet or any other electronic sources. Duke Honor Code applies to all the work you submit for evaluation. 
Writing and Submitting Assignments 
You are strongly encouraged to use LaTeX or other good word processor for typing the solutions to the assignments, and submit them in PDF or PS file format. If you prefer to handwrite them, then write the solutions clearly and legibly. Please note that short and tothepoint answers often get more credits than long and rambling answers. 
Course Page, Email, Feedback 
Please check the course homepage frequently for any announcements, supplemental notes, readings, homework, etc. Important announcements will be sent by email. The following email id reaches every one in the class including the TAs and the instructor: compsci230 AT cs dot UniversityName dot edu. Please use this for posting general comments meant to be read by everyone in the class. Please use the instructor's or the TA's email id for specific questions. We welcome your suggestions and feedback on all aspects of the course. Your suggestions will improve the quality of the course. Please do not hesitate to provide your suggestions. 
Piazza 
Click here. 
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/reprioritized weekly as the course progresses. Please check back often to get the latest schedule.
Week, Lecture(L)/Recitation(R) 
Homework Due 
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.13.5] [R: 1.1] 

R03  May 17, Friday  —  Propositional Logic Applications Logic Gates Propositional Equivalence Satisfiability 
Lecture 03 [LLM: 1.1, 3.13.5] [R: 1.21.3] 

Week 2  L04  May 20, Monday  —  Predicate Logic Quantifiers Nesting of Quantifiers 
Lecture 04 [LLM: 1.2,3.6] [R: 1.41.5] 

R05  May 21, Tuesday  —  Rules of Inference  Lecture 05 [LLM: 1.31.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.31.9, 2] [R: 1.71.8] 

L07  May 23, Thursday  Homework 01 out  Structures Sets and Operations on Sets Functions, Binary Relations 
Lecture 07 [LLM: 4.14.4] [R: 2.12.3] 

R08  May 24, Friday  —  Sequences and Summations Finite Sets Matrices Infinite Sets 
Lecture 08 A [LLM: 2] [R: 2.42.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.15.3] [R: 5.15.2] 

L10  May 29, Wednesday  —  Induction Continued Recursive Definitions and Structural Induction Recursive Algorithms 
Lecture 10 [LLM: 6] [R: 5.35.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 (2Set InclusionExclusion) Rule The Division Rule and Tree Diagrams The 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 Repetition The InclusionExclusion 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 Bernoulli Binomial Geometric 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  LectureNumberTheory [R: 4.1 4.3] 

L26  June 20, Thursday  —  Number Theory  [R: 4.4]  
R27  June 21, Friday  —  Graph Theory  [R 10.110.4]  
Week 6  L28  Jun 24, Monday  Homework 04 due  Graph Theory  [R 10.110.4] 
[Ve] D. J. Velleman. How to Prove It: A Structured Approach. 2nd Edition; Cambridge University Press; 2006. (a nice book on logic and proofs)