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
    Lectures

    Allen 103, Mon.Tue.Wed.Thu.Fri 9:30AM-10:45AM
    Recitations

    We will use one of the lectures as recitation.
    Office Hours

    Chittu: LSRC D301, Tue.Wed 11:00AM-12:00Noon
    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 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 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 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
    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 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)