TTIC 31010 - Algorithms

Chuzhoy, J. Makarychev, Y.

This is a graduate level course on algorithms with the emphasis on central combinatorial optimization problems and advanced methods for algorithm design and analysis. Topics covered include asymptotic analysis, greedy algorithms, dynamic programming, amortized analysis, randomized algorithms and probabilistic methods, combinatorial optimization and approximation algorithms, linear programming, and advanced data structures.

The course textbook is "Introduction to Algorithms" by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.

TTIC 31020 - Introduction to Statistical Machine Learning

Shakhnarovich, G. Srebro, N. OR McAllester, D.

A systematic introduction to machine learning, covering theoretical as well as practical aspects of the use of statistical methods. Topics include linear models for classification and regression, support vector machines, regularization and model selection, and introduction to graphical models. Application examples are taken from areas like information retrieval, natural language processing, computer vision and others.

Prerequisites: Probability, Linear Algebra, Undergraduate Algorithms.

TTIC 31030 - Mathematical Foundations

McAllester, D.

This course covers the foundations of mathematics from a classical nonconstructive) type-theoretic perspective. The course covers the general notion of a mathematical structure, the general notion of isomorphism, and the role of axiomatizations and constructions in mathematical definitions. The definition of the real numbers used as a fundamental example. The course also covers the notion of definability in well-typed formalisms. A primary example is the non-definability of a linear bijection between a vector space and its dual. Ontologies (types) relevant to machine learning are emphasized such as the type theory of PCA, CCA and Banach spaces (norms and dual norms).

TTIC 31040 - Introduction to Computer Vision

Shakhnarovich, G. Urtasun, R.

Introduction to techniques in computer vision, with emphasis on fundamental principles and efficient algorithms. Topics include: digital image formation and processing; detection and analysis of visual features; representation of two- and three-dimensional shape; recovery of 3D information from images and video; analysis of motion. Applications covered in depth include stereo, structure from motion, segmentation, instance and category level object detection and recognition.

TTIC 31050 - Introduction to Bioinformatics and Computational Biology

Xu, J.

TTIC 31060 - Computability and Complexity Theory

Razborov, A.

Part one consists of models for defining computable functions: primitive recursive functions, (general) recursive functions, and Turing machines; the Church-Turing Thesis; unsolvable problems; diagonalization; and properties of computably enumerable sets. Part two deals with Kolmogorov (resource bounded) complexity: the quantity of information in individual objects. Part three covers functions computable with time and space bounds of the Turing machine: polynomial time computability, the classes P and NP, NP- complete problems, polynomial time hierarchy, and P-space complete problems.

TTIC 31070 - Convex Optimization

Srebro, N.

The course will cover techniques in unconstrained and constrained convex optimization and a practical introduction to convex duality. The course will focus on (1) formulating and understanding convex optimization problems and studying their properties; (2) understanding and using the dual; and (2) presenting and understanding optimization approaches, including interior point methods and first order methods for non-smooth problems. Examples will be mostly from data fitting, statistics and machine learning.

Prerequisites: Linear Algebra, Multidimensional Calculus, Undergraduate Algorithms

TTIC 31090 - Signals, Systems and Random Processes

Livescu, K.

Introduction to analysis of signals and linear time-invariant systems at a graduate level. Topics include: Continuous and discrete-time transforms (Fourier and others); linear filtering; sampling and aliasing; random processes and their interaction with linear systems; applications in areas such as speech and image processing and robotics.

Prerequisites: Probability, linear algebra.

TTIC 31100 - Computational Geometry

Chuzhoy, J. Makarychev, Y. Sidiropoulos, A.

The course covers fundamental concepts and algorithms in computational geometry. Topics covered include: convex hulls, polygon triangulations, range searching, segment intersection, Voronoi diagrams, Delaunay triangulations, motion planning, binary space partitions, geometric polynomial-time approximations schemes, locality-sensitive hashing, metric embeddings and applications.

The course textbooks are "Computational Geometry" by M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, and "Lectures on Discrete Geometry" by J. Matousek.

TTIC 31110 - Speech Technologies

Livescu, K.

Introduction to techniques used in speech technologies, mainly focusing on speech recognition. Topics include: Feature extraction, phonetic classification, acoustic modeling with hidden Markov models, pronunciation modeling, language modeling, expectation-maximization for learning, large-vocabulary recognition, discriminative models, graphical models.

Prerequisite: Introductory probability.

TTIC 31120 - Statistical and Computational Learning Theory

Srebro, N.

Rigorous mathematical treatment of statistical learning theory (understanding the sample complexity required to get good generalization) and computational learning theory (understanding what can be learned efficiently). Topics may include: Models of learning, including online learning, Valiant's PAC model, agnostic PAC, Vapnik's general model, and relationship with Stochastic Optimization; Classical results in hardness of learning, hardness of proper learning vs hardness of generalization; Parametric models: cardinality, description length, VC-dimension and VC-subgraphs; Scale-sensitive control: fat shattering, covering numbers and Radamacher complexity; PAC-Bayes Guarantee; Online and stochastic gradient descent and mirror descent.

Prerequisite: Introduction of Statistical Machine Learning or equivalent graduate level course; Confidence with probability theory.

TTIC 31130 - Visual Recognition

Urtasun, R. Shakhnarovich, G.

TTIC 31140 - Learning and Inference in Graphical Models

Urtasun, R. Srebro, N.

A graphical model is a probabilistic model, where the conditional dependencies between the random variables is specified via a graph. Graphical models provide a flexible framework for modeling large collection of variables with complex interactions, as evidenced by their wide domain of application, including for example machine learning, computer vision, speech and computational biology. This course will provide a comprehensive survey of learning and inference methods in graphical models, including variational methods, primal-dual methods and sampling techniques.

TTIC 31150 - Research at TTIC

Varies

Weekly lectures and discussions by TTIC researchers introducing their research and research problems. Provides a broad view of research carried out at TTIC. Half credit, pass/fail, Instructor Consent Required.

TTIC 31160 - Computer Science Internship

Advisor

In-depth involvement in areas of computer science in a research lab, University or business setting. Internship activities and objectives must be related to the student's program objectives. Required enrollment for F-1 CPT internship. Advisor’s Consent Required.