Digital Geometry Algorithms

CSC

80050

Digital Geometry Algorithms

This course addresses algorithmic problems in a world of big data, i.e., problems in settings where the algorithm's input data is too large to fit within a single computer's memory. In previous decades, DBMS (DataBase Management System) settings, in which the data fits on a machine's disk but not in memory, motivated the external memory or I/O models (e.g. external mergesort and B-trees). Models such as MapReduce/Hadoop have appeared for computing on data distributed across many machines (e.g. PageRank computation or matrix multiplication). Finally, streaming and sketching algorithms solve problems in linear or sublinear time, on sequences (e.g. finding missing, random, or frequent elements) and on graphs (e.g. finding matchings and counting triangles, deciding bipartiteness and connectivity). The above topics, from old to new, will be covered in this course. Other topics also include approximate matrix multiplication, the secretary problem, and compressed sensing.

Offer as needed

Graduate School Graduate

Yes