Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

ES 214 | Aug-Nov 2023

ES214. Discrete Mathematics

August — November 2023

(co-instructor with Prof. Anirban Dasgupta.)

About the Course

This is a first course in discrete mathematics and has a broad scope: we introduce elementary concepts in logic, set theory, combinatorics, graph theory, number theory, and probability. The course is designed to be accessible to students from all disciplines, and is a core course for the B.Tech. program at IITGN. We hope that students taking this course discover the beauty of mathematical methods and their applications.

Target Audience

You will find this course interesting if:

  • you think counting the number of ways in which you can complete your graduation requirements is a fun problem to think about,
  • you enjoy logic puzzles like this one or probability puzzles like this one, or
  • you like box-stacking challenges, or
  • you are enrolled in a program for which this course is in the core.
Prerequisites

This course is self-contained and involves no pre-requisites.

References
  1. Discrete Mathematics and Its Applications by Kenneth Rosen
  2. Open Textbook on Discrete Mathematics
  3. Proofs: A Long-Form Mathematics Textbook by Jay Cummings
  4. Playing with Discrete Math by Kyle Burke and Craig Tennenhouse
  5. Online Course (with lecture videos): Math 4190, Summer I 2019
Timings and Venue

Venue: 1/101

Lectures:

  • Tuesdays 3:30PM — 5:00PM
  • Wednesdays 11:30 — 12:50

Tutorials

  • Thursdays 3:30PM — 5:00PM
TAs and Office hours

Office Hours: By email.

TAs:

  1. Harshil Mittal
  2. Saraswati Nanoti
  3. Eshwar Dhande
Evaluation policy
  • Each of the three exams account for 20% of the grade.
  • Each of the eleven tutorials will have a quiz worth 5 points. The total number of points you can earn through quizzes is capped at 40, and accounts for 40% of the grade.
  • There will be weekly assignments that are not graded but are recommended for practice.
Register
  • For IITGN students, (pre-)register through IMS as usual.
  • All quizzes and exams will be on Mathmatize; please sign up here.
  • For announcements, please sign up on Google classroom with this link or use the invite code nzl3hkr.
  • If you are not from IITGN and are interested in taking up the course, then please send us an email.
  • Lectures
  • Assignments
  • Quizzes
  • Exams

All slides for the initial lectures can be found here.

Date Lecture Slides Notes Video
02 Aug, 2023 1. Intro to Proofs - I

General Methods • Chessboard Tilings • Game of Chomp

03 Aug, 2023 2. Intro to Proofs - II

Pigeonhole Principle • Illustrative Examples

08 Aug, 2023 3. Sets

Definitions • Operations • Showing Containment • Showing Equality

09 Aug, 2023 4. Functions and Relations

Injections, Surjections, Bijections • Compositions • Equivalence Classes

16 Aug, 2023 5. Induction

Dominoes, Ladders, and Chips • Examples • Non-Examples • Strong Induction

22 Aug, 2023 6. Propositional and Predicate Logic

Syntax • Truth Tables • Quantifiers

23 Aug, 2023 7. Inference Systems

Inference Rules (e.g, Modus Ponens, Modus Tollens, Resolution, etc) • Paradoxes

29 Aug, 2023 8. Elementary Counting Methods

Permutations • Combinations • Binomial Coefficients

30 Aug, 2023 9. The Method of Double Counting

Examples of proofs by double-counting

12 Sep, 2023 10. Intro to Graphs: Euler Tours

Necessary and Sufficient Conditions for Euler Tours • Computing Euler Tours

13 Sep, 2023 11. Hall's Theorem

Matchings • Congestion in Bipartite Graphs • Hall's Theorem • Applications

19 Sep, 2023 12. Graph Coloring

Map Coloring • Greedy Algorithms • Bipartite Graphs • k-Degenerate Graphs

20 Sep, 2023 13. Planarity

Planar Graphs are Five-Colorable • Obstructions to Planarity

26 Sep, 2023 14. Graphs Recap

~

27 Sep, 2023 15. Probability Intro

Basics of Discrete Probability • Monty Hall • Conditional Probability

03 Oct, 2023 16. The Probabilistic Method - I

An Introduction to the Method • Applications in Graph Theory

04 Oct, 2023 17. The Probabilistic Method - II

Ramsey Number • Sum-Free Sets

10 Oct, 2023 18. Recap

~

17 Oct, 2023 19. The Linear Algebra Method - I

OddTown and EvenTown

18 Oct, 2023 20. The Linear Algebra Method - II

VC Dimension of a Set System • Sauer's Lemma

31 Oct, 2023 21. Intro to Groups: Rotations and Symmetries

TBA

01 Nov, 2023 22. Permutation and Cyclic Groups

TBA

07 Nov, 2023 23. Homomorphisms

TBA

08 Nov, 2023 24. Quotient Groups and First Isomorphism Theorem

TBA

14 Nov, 2023 25. Intro to Number Theory: Extended Euclid's Algorithm

TBA

15 Nov, 2023 26. Chinese Remainder Theorem

TBA

21 Nov, 2023 27. Applications I: RSA

TBA

22 Nov, 2023 28. Applications II: PageRank

TBA

23 Nov, 2023 29. Recap

~

No matching items

Weekly practice problems are posted to Google Classroom. There is no need to submit these assignments, but please make sure to get feedback from your peers, instructors and TAs as you go along. We also strongly encourage you to explore the problems from the courses available through Brilliant (access details have been shared on Google Classroom as well).

Problems and solutions for weekly quizzes are available from within Mathematize.

Issued Assessment Problems Solutions Due
TBA Exam 1

Syllabus: topics in lectures 1 to 9 (inclusive)

-
TBA Exam 2

Syllabus: topics in lectures 10 to 18 (inclusive)

-
TBA Exam 3

Syllabus: topics in lectures 21 to 26 (inclusive)

-
No matching items

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×