Randomized Algorithms (COMPSCI 630)

Spring
2016 Spring
2018

Randomization
is a key technique in many settings, and is becoming more important in
both theory and practice. It does not only lead to algorithms
with better performance/fast running time, in some settings it also
makes impossible things feasible. In this course we will see examples
of the power of randomness. This will include basic techniques like
linearity of expectation, union bounds and concentration of measure. We
will also focus on the applications related to dimension reduction (in
different settings) and Markov Chains.

Algorithmic Aspects of Machine
Learning (COMPSCI 590) 
Fall
2015, Fall 2016 
Many
machine learning problems (like sparse coding or topic modeling) are
hard in the worstcase, but nevertheless solved in practice by
algorithms whose convergence properties are not understood.
In
this course we will see many instances where we can design algorithms
for machine learning problems that have rigorous guarantees. The course
will cover topics such as: nonnegative matrix factorization, topic
models, matrix completion and tensor decomposition. Although all these
problems are NPhard in the worstcase, we will see what properties
reallife instances may satisfy and why these properties allow us to
design efficient algorithms with provable guarantees.

Design and Analysis of Algorithms
(COMPSCI 330) 
Fall 2016, Fall 2017, Spring 2019 
Algorithms
are one of the foundations of computer science. Designing efficient
algorithms under different resource constraint is a ubiquitous problem.
In this course, we will study basic principals of designing and
analyzing algorithms. In the class we will see classical examples of
algorithms design including graph algorithms, data structures, Linear
Programming and gradient descent. The goal of this course is to
familiarize undergraduate students with algorithm design techniques
that can be generalized to many application areas. 