COL863: Special Topics in Theoretical Computer Science
(Also listed as CSL863 for those following the old curriculum)
Topic: Mathematics of Data Science
II semester: 2015-16
Class Timings:Monday Wednesday 3:30PM to 4:50PM.
Room: Bharti 201.
TA: Guntash Arora. IIT LDAP id: cs5110279.
Core topics: High-dimensional space and its properties; Linear algebra and Singular Value Decomposition; Spectral methods; Random walks and their applications.
Other topics (to be covered if time is available and based on interest): Random graphs and network models; Algorithms for massive data sets and space-efficient data structures, Convex optimisation, Clustering.
Background required: graph theory, linear algebra.
- Kannan and Hopcroft's book draft, Chapters 2, 3 and maybe 7. Download here.
Download revised version of chapter 2 here.
- D. A. Levin, Y. Peres, and E. Wilmer, Markov Chains and Mixing Times, relevant chapters to be announced. Download here.
- The proof of the Perron-Frobenius theorem presented in class is from Chapter 9 of the book Dynamical Systems by Shlomo Sternberg (2010, Dover Publications, ISBN-13: 978-0486477053). The entire book can be downloaded at this link.
- The volume of high dimensional solids. Handwritten lecture notes. 25th January 2016. Download here.
Evaluation will be through homeworks and exams.
- Latex only. All exams are to be submitted as a pdf file
created from latex source. No handwritten exams will be accepted.
- Moodle submission only. If you are registered in this
course you are registered in this course on moodle. Please only submit
your exam there the the appropriate upload link. If you
are not registered in the course and wish to submit the exam
you may email it to the TA Guntash Arora with cc to me.
- Collaboratation and Plagiarism
- You are expected to attempt all problems on your own.
- You may consult online resources. However if you find the solution
to one of the problems online you are expected to not look at the
- You may discuss solution ideas. However if you have the entire
solution it is incumbent on you to not reveal the solution to
your fellow students.
- You may not copy or cut and paste any text from any source
whatsoever (your friends, the textbook, online, anything).
- If you need to
quote anything from anywhere a complete citation should be provided,
i.e., it should be possible for the grader to look up the source
- A violation of the copying rule (previous two bullet points) will
lead to very stringent action with no excuse for even a
minor-seeming violation and no opportunity to make up. This is an
800-level class and a high degree of integrity should beconsidered a prerequisite.