Duke Logo

Chittaranjan Tripathy
[ Announcements | Administration | Lecture Schedule and Homeworks | Solutions | Additional Readings]

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

    Administration

    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:05AM-11:20AM
    Recitations

    		Soc Psy 126, Fri 11:45AM-1:00PM
    Office Hours

    		Chittu: North 306, Tue.Wed 4:00PM-5:00PM
    Branka: LSRC D301, Tue.Wed 6:00PM-7:00PM
    Textbooks

    		Required:
            [R] Discrete Mathematics and its Applications, 7th Edition, 2011. Kenneth H. Rosen.  
    Optional but Highly-Recommended (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 In-class Closed-book Midterm Exam. [15 points]
    Second In-class Closed-book Midterm Exam. [15 points]
    In-class Closed-book 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 hand-write them, then write the solutions clearly and legibly. Please note that short and to-the-point 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.

    (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 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.1-3.5] [R: 1.1]
     
    Week 2 L03 Jan 15, Tuesday — Propositional Logic
    Applications
    Logic Gates
    Propositional Equivalence
    Satisfiability    		 Lecture 03
    [LLM: 1.1, 3.1-3.5] [R: 1.2-1.3]
    L04 Jan 17, Thursday Homework 01 out Predicate Logic
    Quantifiers
    Nesting of Quantifiers    		 Lecture 04
    [LLM: 1.2,3.6] [R: 1.4-1.5]
    R05 Jan 18, Friday — Rules of Inference Lecture 05
    [LLM: 1.3-1.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.3-1.9, 2] [R: 1.7-1.8]
    L07 Jan 24, Thursday Homework 01 due
    Homework 02 out     		Structures
    Sets and Operations on Sets
    Functions, Binary Relations     		Lecture 07
    [LLM: 4.1-4.4] [R: 2.1-2.3]
    R08 Jan 25, Friday — Sequences and Summations
    Finite Sets
    Matrices    		 Lecture 08 (appended to Lecture 07)
    [LLM: 2] [R: 2.4-2.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.1-5.3] [R: 5.1-5.2]
    R11 Feb 01, Friday — Induction Continued
    Recursive Definitions and Structural Induction
    Recursive Algorithms     		Lecture 11
    [LLM: 6] [R: 5.3-5.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 Divide-and-Conquer 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 (2-Set Inclusion-Exclusion) 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 Inclusion-Exclusion 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 28-30
    [LLM: 18] [R: 7]
    R30 Mar 22, Friday — Conditional Probability
    Independence Continued...    		 Lecture 28-30
    [LLM: 18] [R: 7]
     
    Week 12 L31 Mar 26, Tuesday — Random Variables and Expectations Lecture 31-35
    [LLM: 18] [R: 7]
    L32 Mar 28, Thursday Homework 07 due
    Homework 08 out     		More Expectations Lecture 31-35
    [LLM: 18] [R: 7]
    R33 Mar 29, Friday — Distributions
    Uniform
    Bernoulli
    Binomial
    Geometric    		 Lecture 31-35
    [LLM: 18] [R: 7]
     
    Week 13 L34 Apr 02, Tuesday — Variance Lecture 31-35
    [LLM: 18] [R: 7]
    L35 Apr 04, Thursday Homework 08 due
    Homework 09 out     		Bayes' Theorem and Applications
    		Lecture 31-35
    [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 Lecture-Number-Theory
    [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.1-10.4]
    R42 Apr 19, Friday — Graph Theory [R 10.1-10.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]
     

    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)