CS607 | Jan-Apr 2024

CS607. Combinatorics with Applications in Computer Science

2024

About the Course

Just as arithmetic deals with integers (with the standard operations), algebra deals with operations in general, analysis deals with functions, geometry deals with rigid shapes, and topology deals with continuity, so does combinatorics deal with configurations. Combinatorics counts, enumerates, examines, and investigates the existence of configurations with certain specified properties. With combinatorics, one looks for their intrinsic properties, and studies transformations of one configuration into another, as well as “subconfigurations” of a given configuration.

Claude Berge, Principles of Combinatorics, Dunod, Paris, 1968 (English translation: Academic Press, New York, 1971)

Mathematics is the art of reducing any problem to linear algebra.

William Stein

This course will delve into some special highlights from the field of combinatorics, with a broad emphasis on applications to computer science. We will frequently encounter the use of linear algebraic methods. We will roughly have four major themes: extremal set systems, randomized algorithms, geometry, graphs. Every now and then, we’ll work through “puzzles”, which are questions that have a recreational flavor.

Target Audience

Did you enjoy Discrete Mathematics? That’s a sign: there’s a good chance you’ll like this too! You might find a slight change of pace and style in the offering, but it will be just as fun and full of awe-inspiring discovery.

If you haven’t done Discrete Mathematics, but you enjoy discret-ey puzzles and questions, you’ll probably also like this.

That said, I am not a recommender algorithm, so please join us for a class or two during the add/drop period to decide if this course is for you :)

Prerequisites

The course is mostly self-contained, but a general degree of comfort with proofs and some elementary linear algebra would be useful.

References

List of References

1. Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra by Jiří Matoušek
2. Extremal Combinatorics: With Applications in Computer Science (Texts in Theoretical Computer Science. An EATCS Series) by Stasys Jukna

Additional pointers (papers, articles, videos, etc.) specific to each lecture will be provided in the summaries of the course plans. Some lectures may have additional notes linked to from the course plan as well.

Timings and Venue

Venue: 7/110

Timings: 15:30 - 16:50 on Mondays and 14:00 - 15:20 on Thursdays.

TAs and Office hours

Office Hours: By email.

TA: Aditi Sethia

Evaluation policy

• Each of the three quizzes account for 10% of the grade.
• The midsem exam accounts for 15% of the grade.
• The endsem exam accounts for 20% of the grade.
• There will be worksheets accompanying each lecture, due at midnight on the day of the lecture. Each worksheet is worth two points, and your total points from the worksheets is capped at 35 points, which contributes to 35% of the grade.

Logistics

• 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 ebtcrf2.
• If you are not from IITGN and are interested in taking up the course, then please send us an email.

Lectures

Worksheets

Coming Soon.

Quizzes

Coming Soon.

Exams

Coming Soon.