You're not currently signed in. Sign in »

Provably Efficient Algorithms for Numerical and Combinatorial Problems (CS 598 EVS) Spring 2020

What Where
Time/place Tu/Th 3:30pm-4:45pm, 1131 Siebel Center
Office Hours After class, Tu/Th 4:45-5:30 (please arrive no later than 5:10), 4229 Siebel Center
Class URL
Web forum View Piazza »
Calendar View Calendar »

Bridging the theory and practice of algorithms requires going beyond computational complexity to more sophisticated models of computer architecture and algorithmic cost. This course covers multiple analytical techniques that quantify the efficacy of an algorithm: parallel scalability, memory traffic, interprocessor communication, and numerical stability. General representations of algorithms (dependency graphs, bilinear algorithms) will be introduced as well as techniques for communication lower bound analysis. The course will look at problems from a variety of application domains, ranging from sorting and graph algorithms to numerical solvers and optimization. Special focus will be given to tensor computations.

The learning objective of the course is to develop techniques for mathematical representation and analysis of algorithms. Focus will be on numerical algorithms for matrix and tensor computations, but miscellaneous problems and algorithmic models will be considered. Topics of consideration will incorporate student interest/presentations.

Students will be expected to give a presentation relevant to the course, which may involve a discussion/activity, as well as to complete some assignments The assignments are planned to be given as in-class activities, but can also be completed offline. The presentation will comprise 70% and assignments 30% of the overall grade.

Quizzes (in-class activities)

Quiz 1: Interest Survey »

Quiz 2: Computing the Maximum Ritz Value »

Quiz 3: Finding Minimum of Quadratic Function in a Subspace »

Quiz 4: Bilinear Algorithms »

Quiz 5: Bitonic Sort »

Quiz 6: Algebraic Graph Algorithms »

Quiz 7: Bilinear Algorithms for Convolution »

Quiz 8: Triangular Matrix Inversion with Poly-Logarithmic Depth »

Course Outline

Related Courses

CS 598 EVS: Communication Cost Analysis of Algorithms, Fall '16

CS 554: Parallel Numerical Algorithms, Fall '19

CS 450: Numerical Analysis, Fall '18

Related Texts

Python Help

We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments.

Python Workshop Material

Numpy Help