Special Topics in Algorithms - Matroid Theory

Course code	COL866
Instructor	Ashish Chiplunkar (ashishc@iitd...)
Classes	LH313.2; Tuesday and Friday 14:00 - 15:30 (Slot AC)

Eligibility

COL202 or MTL180 or an equivalent course is a hard prerequisite (for UG students). Having background in algorithm design and analysis (one of COL351, MTL342, COL702, ELL781) is strongly recommended. It is extremely important that you recall everything taught in the prerequisite courses, specifically:

Proof techniques - construction, contradiction, induction
Sets and set operations, relations -- equivalences and partial orders, functions -- injections, surjections, and bijections; cardinality
Graph Theory -- connectivity, acyclicity, spanning tree algorithms, maxflow-mincut, bipartite graphs, matchings, Hall's an König's theorems

Content (tentative)

Matroids and Kruskal's algorithm
Independent sets, circuits, bases, rank, span
Duals and minors
Graphic and representable matroids, and their characterization
Algorithms for matroid intersection and union problems

Reference books

"Matroid Theory" by James Oxley
"Matroid Theory" by D. J. A. Welsh

It is not mandatory to buy any of the above books if you plan to attend classes regularly.

Useful Platforms

Microsoft Teams for announcements, discussion forum, course material
Gradescope for exam feedback

Grading and Attendance Policy

The grade will be decided on the basis of the total of the following.

Quizzes	60 marks	3 of 4 quizzes; 20 marks each
End-semester exam	40 marks
Scribes	2 marks	per satisfactorily written scribe submitted within 72 hours of the lecture

Quizzes will be announced a week in advance.
Quiz 4 will be a compensatory / improvement quiz intended for students who miss or perform poorly in Quizzes 1-3. If Quiz 4 is not attempted, marks of Quizzes 1-3 will be counted. If Quiz 4 is attempted, its marks will be counted with the marks of the best 2 of Quizzes 1-3. The decision about whether to attempt Quiz 4 must be taken before the quiz (it cannot be taken after reading the question paper). Beyond this, no compensation for missed quizzes will be given.
In every exam, students will be allowed to use only their own handwritten notes; no other reference material is allowed.
Passing criterion: 30 marks over all evaluation components
Audit-passing criterion: 30 marks over all evaluation components, 30 marks in the end-semester exam.
Penalty for insufficient attendance: students with insufficient attendance (< 75%) will not be allowed to write the re-major exam (in case they get an E grade), and their I grade requests will be turned down (in case they miss the end-semester exam and apply for an I grade). Auditing students with insuficient attendance get the NF grade irrespective of their performance. Other than this, there is no pentalty for insufficient attendance. Assuming you pass the course, grade and attendance will be conditionally independent given marks. (However, rest assured that unconditionally, grade and attendance will be heavily correlated!) Marking attendance in lectures is nevertheless mandatory. Marking attendance without attending will be treated as academic dishonesty.
Penalty for academic dishonesty: D/F/NF grade, or disco, or both, depending on the severity of the offence, at the instructor's discretion.