CSCI B609: A Theorist's Toolkit
Fall 2016
Tuesday, Thursday 2:30pm - 3:45pm, BH 236
Description
The aim of the course is to give students a flavor of theoretical
research, teach them necessary tools to prove mathematical statements,
which will be helpful to their future research in theory and related
fields such as machine learning and operations research.
Students are expected to have a solid undergraduate background in
mathematics (e.g., elementary combinatorics, graph theory, discrete
probability, basic algebra/calculus) and algorithms design and
analysis (running time analysis, big-O/Omega/Theta, P and NP, basic
fundamental algorithms). Mathematical maturity is a must.
Course Information
-
Instructor: Yuan Zhou.
Office Hours: By appointment.
Associate Instructor: Yuan Xie.
Office Hours: Monday 2-3pm, Tuesday 4-5pm, at LH 406.
-
Online disucssion. We will use Canvas (at One.IU) for course announcements and discussion.
-
References. The course will mainly follow the lecture notes of the great course by Ryan O'Donnell.
-
Evaluation scheme.
The solutions to the problem sets count towards 60% of the final score. Scribing notes count towards 25% of the final score. Additionally, there will be grades for in-class participation (15%).
-
Problem sets.
There are 4~5 problem sets for students to solve throughout the semester. The answers to the problem sets must be typesetted in PDF format (and preferably via LaTeX) and submitted via Canvas. A LaTeX template for your answers can be found here.
-
Problem set late policy.
Full credit will be given for solutions turned in on (or before) the due date. 90% credit will be given for one-day (24-hour) late.
70% credit will be given for two-day (48-hour) late.
50% credit will be given for three-day (72-hour) late.
NO credit will be given after three days.
-
Problem set collaboration policy.
Students are encouraged to discuss and work in groups on problem sets.
However students must state the people they discussed with in the acknowledgement section of their written assignment.
Students are not allowed to take detailed notes in any group discussion that will appear verbatim in assignment write-ups. Every student has to turn in answers that are written solely by himself/herself.
-
Scribe notes.
Students will be asked to take turns preparing "scribe notes" for posting on the course web site.
Starting from the second week (equivalently, the third class meeting), each class, one student will be the designated "scribe",
taking careful notes during class, writing them up using this latex template, and sending them to me within a week after the lecture.
Each student will be resposible for scribing 1 or 2 classes throughout the semester.
The notes should be written out in the way so that would be understandable even by a student who might have missed class, not merely a transcription of the telegraphic notes that you took during class.
Lecture Notes
(Disclaimer: the lecture notes scribed by students have not been proofread.)