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 
TA 
Branka Lakic email: blakic AT cs dot duke dot edu 
UTA 
Alessio Santoro email: alessio DOT santoro AT duke dot edu Nicholas Gordon email: nick dot gordon AT duke dot edu 
Lectures 
Physics 130, Tue.Thu 10:05AM11:20AM 
Recitations 
Soc Psy 126, Fri 11:45AM1:00PM 
Office Hours 
Chittu: North 306, Tue.Wed 4:00PM5:00PM Branka: LSRC D301, Tue.Wed 6:00PM7:00PM 
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  Jan 10, Thursday  —  Introduction and Overview Administrativia Two Problems Cutting a Pizza Lighting the rooms 
Lecture 01 [LLM: 1.1], [R: 1.1] 

R02  Jan 11, Friday  —  Propositional Logic Truth Tables 
Lecture 02 [LLM: 1.1, 3.13.5] [R: 1.1] 

Week 2  L03  Jan 15, Tuesday  —  Propositional Logic Applications Logic Gates Propositional Equivalence Satisfiability 
Lecture 03 [LLM: 1.1, 3.13.5] [R: 1.21.3] 

L04  Jan 17, Thursday  Homework 01 out  Predicate Logic Quantifiers Nesting of Quantifiers 
Lecture 04 [LLM: 1.2,3.6] [R: 1.41.5] 

R05  Jan 18, Friday  —  Rules of Inference  Lecture 05 [LLM: 1.31.4] [R: 1.6] 

Week 3  L06  Jan 22, Tuesday  —  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  Jan 24, Thursday  Homework 01 due Homework 02 out 
Structures Sets and Operations on Sets Functions, Binary Relations 
Lecture 07 [LLM: 4.14.4] [R: 2.12.3] 

R08  Jan 25, Friday  —  Sequences and Summations Finite Sets Matrices 
Lecture 08 (appended to Lecture 07) [LLM: 2] [R: 2.42.6] 

Week 4  L09  Jan 29, Tuesday  —  Infinite Sets  Lecture 09 [LLM: 7] [R: 2.5] 

L10  Jan 31, Thursday  Homework 02 due Homework 03 out 
Induction Ordinary Induction Strong Induction 
Lecture 10 [LLM: 5.15.3] [R: 5.15.2] 

R11  Feb 01, Friday  —  Induction Continued Recursive Definitions and Structural Induction Recursive Algorithms 
Lecture 11 [LLM: 6] [R: 5.35.4] 

Week 5  L12  Feb 05, Tuesday  —  Algorithms Counting the Number of Reflected Rays Fibonacci Number 
Lecture 12 [LLM: ] [R: 3] 

L13  Feb 07, Thursday  Homework 03 due Homework 04 out 
Algorithms Continued Models of Computational Complexity of Algorithms 
Lecture 13 [LLM: ] [R: 3] 

R14  Feb 08, Friday  —  Algorithms Continued Asymptotic Notation 
Lecture 14 [LLM: ] [R: 3] 

Week 6  L15  Feb 12, Tuesday  —  Algorithms Continued Asymptotic Notation Continued (examples) 
Lecture 15 [LLM: ] [R: 3] 

L16  Feb 14, Thursday  Homework 04 due  Algorithms Continued Fibonacci Number Revisited Selection Sort Setting up Recurrences 
Lecture 16 [LLM: ] [R: 3] 

R17  Feb 15, Friday  —  Algorithms Continued: Two recursive algorithms Merge Sort Binary Search Setting up Recurrences 
Lecture 17 [LLM: ] [R: 3] 

Week 7  L18  Feb 19, Tuesday  —  Midterm 01  [Exam Information and Cheat Sheet]  
L19  Feb 21, Thursday  Homework 05 out  Solving Recurrences Substitution Method The Recursion Tree Method 
Lecture 19 [LLM: ] [R: 3] 

R20  Feb 22, Friday  —  Solving Recurrences The DivideandConquer Recurrence The Master Method Examples 
Lecture 20 [LLM: ] [R: 3] 

Week 8  L21  Feb 26, Tuesday  —  Solving Linear Recurrences Linear Homogeneous Recurrences Linear Inhomogeneous Recurrences 
Lecture 21 [LLM: ] [R: 3] 

L22  Feb 28, Thursday  Homework 05 due Homework 06 out 
Counting The Sum Rule The Product Rule The Subtraction (2Set InclusionExclusion) Rule The Division Rule and Tree Diagrams 
[LLM: ] [R: 6.1]  
R23  Mar 01, Friday  —  Counting The Pigeonhole (aka Dirichlet drawer) Principle Some Applications 
Lecture 23 [LLM: 14] [R: 6.2] 

Week 9  L24  Mar 05, Tuesday  —  Counting Permutations and Combinations Binomial Theorems and Binomial Coefficients 
Lecture 24 [LLM: ] [R: 6.3, 6.4] 

L25  Mar 07, Thursday  Homework 06 due  Counting Permutations with Repetition 
Lecture 25 [LLM: ] [R: 6.5] 

R26  Mar 08, Friday  —  Counting The InclusionExclusion Principle Generating Functions 
——  
Week 10  —  Mar 12, Tuesday  —  Spring Break  ——  
—  Mar 14, Thursday  —  Spring Break  ——  
—  Mar 15, Friday  —  Spring Break  ——  
Week 11  L27  Mar 19, Tuesday  —  Introduction to Discrete Probability  Lecture 27 [LLM: 16, 17] [R: 7] 

L28  Mar 21, Thursday  Homework 07 out  Conditional Probability Independence 
Lecture 2830 [LLM: 18] [R: 7] 

R30  Mar 22, Friday  —  Conditional Probability Independence Continued... 
Lecture 2830 [LLM: 18] [R: 7] 

Week 12  L31  Mar 26, Tuesday  —  Random Variables and Expectations  Lecture 3135 [LLM: 18] [R: 7] 

L32  Mar 28, Thursday  Homework 07 due Homework 08 out 
More Expectations  Lecture 3135 [LLM: 18] [R: 7] 

R33  Mar 29, Friday  —  Distributions Uniform Bernoulli Binomial Geometric 
Lecture 3135 [LLM: 18] [R: 7] 

Week 13  L34  Apr 02, Tuesday  —  Variance  Lecture 3135 [LLM: 18] [R: 7] 

L35  Apr 04, Thursday  Homework 08 due Homework 09 out 
Bayes' Theorem and Applications 
Lecture 3135 [LLM: 18] [R: 7] 

R36  Apr 05, Friday  —  Relations Properties of Relations Representations Closures 
[R: 9.1, 9.3, 9.4 (NO Warshall algo)]  
Week 14  L37  Apr 09, Tuesday  —  Equivalence Relations  [R: 9.5]  
L38  Apr 11, Thursday  Homework 09 due  Number Theory  LectureNumberTheory [R: 4.1 4.3] 

R39  Apr 12, Friday  Homework 10 out  Number Theory  [R: 4.4]  
Week 15  —  Apr 16, Tuesday  —  Midterm 02  [Exam Information and Cheat Sheet]  
L41  Apr 18, Thursday  —  Graph Theory  [R 10.110.4]  
R42  Apr 19, Friday  —  Graph Theory  [R 10.110.4]  
Week 15  L43  Apr 23, Tuesday  Homework 10 due  ——  ——  
Week 16  —  Wednesday, May 1 7:00 PM  10:00 PM Also see this 
Final Exam  Covers Everything  [Exam Information and Cheat Sheet]  
[Ve] D. J. Velleman. How to Prove It: A Structured Approach. 2nd Edition; Cambridge University Press; 2006. (a nice book on logic and proofs)