Algorithms: Techniques and Theory

(CS 388G)

Request Info

Modern computational applications often involve massive data sets. In this setting, it is crucial to employ asymptotically efficient algorithms. This course presents techniques for the design and analysis of polynomial-time algorithms. Unfortunately, many optimization problems that arise in practice are unlikely to be polynomial-time solvable. This course presents techniques for establishing evidence of such computational intractability, especially NP-hardness. Even if a given optimization problem is NP-hard, it may be possible to compute near-optimal solutions efficiently. This course presents techniques for the design and analysis of efficient approximation algorithms.

Topics include growth of functions, divide-and-conquer algorithms, dynamic programming, greedy algorithms, basic graph algorithms, network flow, minimum-cost matching, linear program-ming, randomized algorithms, data structures (hashing, amortized analysis, splay trees, union-find, and Fibonacci heaps), online algorithms for paging, P, NP, NP-completeness, and approximation algorithms.

What You Will Learn

  • Techniques for the design and analysis of efficient algorithms
  • Techniques for establishing evidence of computational intractability
  • Techniques for coping with computational intractability

Syllabus

  • Growth of functions, divide-and-conquer algorithms (1 week)
  • Dynamic programming (0.5 weeks)
  • Greedy algorithms (1 week)
  • Basic graph algorithms (0.5 weeks)
  • Network flow algorithms (1.5 weeks)
  • Minimum-cost matching (0.5 weeks)
  • Linear programming (0.5 weeks)
  • Randomized algorithms (0.5 weeks)
  • Hashing (1 week)
  • Amortized analysis, splay trees, union-find, Fibonacci heaps (1.5 weeks)
  • Online algorithms (0.5 weeks)
  • P, NP, NP-completeness (1.5 weeks)
  • Approximation algorithms (1.5 weeks)

Estimated Effort

10-12 hours/week

Course Category

Theory Course

Course Availability

Spring 2020

Meet Your Instructors

Take the Next Step

Advance your computer science career with UT Austin's Master of Computer Science Online.