# Assignments

**Homework policy**: You may work and submit in pairs, but each student is responsible for understanding the entire solution. I will occasionally ask you to explain your solution in class; an inability to justify a solution you handed in will be taken as evidence of copying. Please cite all sources: people, papers, books, internet.

Significant thought and effort is put into crafting exercises so as to maximally facilitate understanding of the material. Solutions will be graded for clarity and correctness. You are encouraged to write them up in LaTeX – mastering this now will greatly help you later on when writing papers.

- Assignment 1 due 04.04.2013
- Assignment 2 due 18.04.2013
- Assignment 3 due 02.05.2013
- Assignment 4 due 13.06.2013

# Project topics

- Multiclass, multilabel classification
- PCA, Johnson-Lindenstrauss and other dimensionality reduction techniques
- Clustering: K-means, spectral, other kinds, Kleinberg's impossibility theorem
- multiplicative updates, winnow algorithm; related: this and this
- scale-sensitive dimensions; also this (a very technical topic)
- learning boolean functions with Fourier analysis
- model selection
- locally-linear embeddings and manifold techniques
- nonnegative matrix factorization
- Markov Decision Processes
- convex loss as a surrogate for 0-1 loss
- statistical queries and learning with noise