(2406) Fundamental Algorithms Chee Yap
Office Hours M 5:10-7:00PM 60 Fifth Ave 110
Reviews a number of important algorithms, with emphasis on correctness and efficiency. The topics covered include solution of recurrence equations, sorting algorithms, selection, binary search trees and balanced-tree strategies, tree traversal, partitioning, graphs, spanning trees, shortest paths, connectivity, depth-first and breadth-first search, dynamic programming, and divide-and-conquer techniques.
Prerequisites: At least one year of experience with a high-level language such as Pascal, C, C++, or Java; and familiarity with recursive programming methods and with data structures (arrays, pointers, stacks, queues, linked lists, binary trees).
(2408) Programming Languages Cory Plock
Office Hours M 5:10-7:00PM CIWW 101
Discusses the design, use, and implementation of imperative, object-oriented, and functional programming languages. The topics covered include scoping, type systems, control structures, functions, modules, object orientation, exception handling, and concurrency. A variety of languages are studied, including C++, Java, Ada, Lisp, and ML, and concepts are reinforced by programming exercises.
Prerequisites: Students taking this class should already have substantial programming experience.
(2410) Compiler Construction Alexander Alekseyev
Office Hours M 7:10-9:00PM CIWW 202
This is a capstone course based on compilers and modern programming languages. The topics covered include structure of one-pass and multiple-pass compilers; symbol table management; lexical analysis; traditional and automated parsing techniques, including recursive descent and LR parsing; syntax-directed translation and semantic analysis; run-time storage management; intermediate code generation; introduction to optimization; and code generation. The course includes a special compiler-related capstone project, which ties together concepts of algorithms, theory (formal languages), programming languages, software engineering, computer architecture, and other subjects covered in the MS curriculum. This project requires a substantial semester-long programming effort, such as construction of a language compilation or translation system that includes lexical and syntactic analyzers, a type checker, and a code generator.
Prerequisites: CSCI-GA 1170, CSCI-GA 2110, and CSCI-GA 2250.
(2411) Operating Systems Hubertus Franke
Office Hours M 7:10-9:00PM CIWW 109
The topics covered include a review of linkers and loaders and the high-level design of key operating systems concepts such as process scheduling and synchronization; deadlocks and their prevention; memory management, including (demand) paging and segmentation; and I/O and file systems, with examples from Unix/Linux and Windows. Programming assignments may require C, C++, Java, or C#.
(2415) Software Engineering Jean-Claude Franchitti
Office Hours M 7:10-9:00PM CIWW 317
This is a capstone course focusing on large-scale software development. This course presents modern software engineering techniques and examines the software life cycle, including software specification, design, implementation, testing, and maintenance. Object-oriented design methods are also considered. Software engineering projects involve creation of a large-scale software system and require some or all of the following elements: formation of a small team, project proposal, literature review, interim report, project presentation, and final report.
Prerequisites: CSCI-GA 1170, CSCI-GA 2110, and CSCI-GA 2250
(3147) Artificial Intelligence Ernest Davis
Office Hours M 5:10-7:00PM CIWW 102
There are many cognitive tasks that people do easily and almost unconsciously but that have proven extremely difficult to program on a computer. Artificial intelligence is the problem of developing computer systems that can carry out these tasks. This course covers problem solving and state space search; automated reasoning; probabilistic reasoning; planning; and knowledge representation.
(3437) Deep Learning Yann LeCun M 4:55-6:35PM GCASL C95
This course concerns the latest techniques in deep learning and representation learning, focusing on supervised and unsupervised deep learning, embedding methods, metric learning, convolutional net and recurrent nets, with applications to computer vision, natural language understanding, and speech recognition.
Prerequisites: DS-GA 1001 Intro to Data Science or a graduate-level machine learning course.
(2417) Advanced Topics in Numerical Analysis: Convex and Nonsmooth Optimization Michael Overton
Office Hours M 5:10-7:00PM CIWW 1302
Convex optimization problems have many important properties, including a powerful duality theory and the property that any local minimum is also a global minimum. Nonsmooth optimization refers to minimization of functions that are not necessarily convex, usually locally Lipschitz, and typically not differentiable at their minimizers. Topics in convex optimization that will be covered include duality, linear and semidefinite programming, CVX ("disciplined convex programming"), gradient and Newton methods, Nesterov's complexity bound, the alternating direction method of multipliers, the nuclear norm and matrix completion, the primal barrier method, primal-dual interior-point methods for linear and semidefinite programs. Topics in nonsmooth optimization that will be covered include subgradients and subdifferentials, Clarke regularity, and algorithms, including gradient sampling and BFGS, for nonsmooth, nonconvex optimization. Homework will be assigned, both mathematical and computational. Students may submit a final project on a pre-approved topic or take a written final exam.
Prerequisites: Undergraduate Linear Algebra and Multivariable Calculus.
(2418) Advanced Topics in Numerical Analysis: High Performance Computing Benjamin Peherstorfer
Office Hours M 1:25-3:15PM CIWW 512
This class will be an introduction to the fundamentals of parallel scientific computing. We will establish a basic understanding of modern computer architectures (CPUs and accelerators, memory hierarchies, interconnects) and of parallel approaches to programming these machines (distributed vs. shared memory parallelism: MPI, OpenMP, OpenCL/CUDA). Issues such as load balancing, communication, and synchronization will be covered and illustrated in the context of parallel numerical algorithms. Since a prerequisite for good parallel performance is good serial performance, this aspect will also be addressed. Along the way you will be exposed to important tools for high performance computing such as debuggers, schedulers, visualization, and version control systems. This will be a hands-on class, with several parallel (and serial) computing assignments, in which you will explore material by yourself and try things out. There will be a larger final project at the end. You will learn some Unix in this course, if you don't know it already.
Prerequisites: (Serial) programming experience with C/C++ (I will use C in class) or FORTRAN, and some familiarity with numerical method.
(23764) Special Topics: Hardness of Approximation: PCP Theorem to 2-to-2 Games Theorem Subhash Khot M 7:10-9:00PM CIWW 102
Researchers firmly believe that no algorithm can efficiently compute optimal solutions to computationally complex problems called NP-hard problems. For many NP-hard problems, even computing an approximately-optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.
The course will provide an overview of these connections. In particular, it will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. It will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 GamesTheorem.
Prerequisites: Basic knowledge of algorithms, NP-hardness, discrete math, analysis.
*Indicates controlled enrollment (permission number required for registration). Contact your program advisor.
**Indicates controlled enrollment (permission number required for registration). Contact Santiago Pizzini (firstname.lastname@example.org).
***Indicates controlled enrollment (permission number required for registration). Contact the instructor.