UI Wordmark

CS 598 TMC - Special Topics - Fine-Grained Algorithms

Campus: Urbana-Champaign

Description:

Subject offerings of new and developing areas of knowledge in computer science intended to augment the existing curriculum. See Class Schedule or departmental course information for topics and prerequisites. Course Information: May be repeated in the same or separate terms if topics vary.

Special Instructions:

All class meetings will be online and synchronous. Algorithms from the Fine-Grained Perspective. In undergraduate algorithms classes, you have studied classical problems such as all-pairs shortest paths, longest common subsequence, edit distance, 3SUM, subset sum, triangles in graphs, etc. Have you ever wondered whether the textbook algorithms you have learned could be improved, or whether they are in fact the best possible- Here, we are interested not just in determining whether the problems are polynomial-time solvable, but in their ""fine-grained"" complexity (quadratic time- cubic time- etc.). We will describe the latest theoretical techniques for obtaining (slightly) improved algorithms for these classical problems and their variants (in general as well as important special cases). We will also prove conditional lower bounds via reductions that relate the fine-grained complexity of one problem to another. For up-to-date information about CS course restrictions, please see

Option 1

Number of Required Visit(s): 0

Course Level: Graduate

Credit: 4

Term(s): Fall


Home

Bachelor's Degree

Master's Degree

Doctoral Degree

Certificates

Continuing Education

Search Programs

Search Courses

FAQ

Contact Us


University of Illinois Online
Phone: (866) 633-8465 - Join Us  Facebook
© Copyright 2015 - University of Illinois

Cookie Settings