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)