Computability, Complexity & Algorithms
assignment Level : Introductive
chat_bubble_outline Language : English
card_giftcard 1 point
Users' reviews
-
starstarstarstarstar

Key information

credit_card Free access

About the content

This class is offered as CS6505 at Georgia Tech where it is a part of the [Online Masters Degree (OMS)](http://www.omscs.gatech.edu/). Taking this course here will not earn credit towards the OMS degree. In this course, we will ask the big questions, “What is a computer? What are the limits of computation? Are there problems that no computer will ever solve? Are there problems that can’t be solved quickly? What kinds of problems can we solve efficiently and how do we go about developing these algorithms?” Understanding the power and limitations of algorithms helps us develop the tools to make real-world computers smarter, faster and safer.

more_horiz Read more
more_horiz Read less
dns

Syllabus

Lesson 1: Computability

* Languages & Countability * Turing Machines * The Church-Turing Thesis * Universality * Undecidability

Lesson 2: Complexity

* P and NP * NP-Completeness * NP-Complete Problems * The Golden Ticket

Lesson 3: Algorithms

* Dynamic Programming * Fast Fourier Transform * Maximum Flow * Maximum Bipartite Matching * Linear Programming * Duality * Randomized Algorithms * Approximation Algorithms
record_voice_over

Instructors

  • Charles Brubaker - Charles Brubaker earned his PhD in Computer Science from Georgia Tech in 2009. He then taught high school computer science and coached basketball at Pace Academy in Atlanta for 4 years. In 2012, inspired by Udacity, he began recording his lectures on a tablet, creating online quizzes, and automatically grading assignments to give his students instant feedback. The success of this enterprise convinced him that Udacity represented the wave of the future in education, and he joined the company in the summer of 2013.
  • Lance Fortnow - Lance Fortnow is professor and chair of the School of Computer Science of the College of Computing at the Georgia Institute of Technology. His research focuses on computational complexity and its applications to economic theory. Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Georgia Tech in 2012, Fortnow was a professor at Northwestern University, the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam. Since 2007, Fortnow holds an adjoint professorship at the Toyota Technological Institute at Chicago.
  • Hariharan Venkateswaran - H. Venkateswaran obtained his Ph.D. in Computer Science from the University of Washington in 1986. He then joined the faculty of Georgia Institute of Technology as an Assistant Professor, where he has pursued his research interests in Complexity Theory, Information Security, and Parallel Computation. A renowned teacher on campus, he was awarded "The William A “Gus” Baird Faculty Teaching Award" in 2008.
store

Content designer

Georgia Institute of Technology
The Georgia Institute of Technology is one of the nation's top research universities, distinguished by its commitment to improving the human condition through advanced science and technology. Georgia Tech's campus occupies 400 acres in the heart of the city of Atlanta, where more than 20,000 undergraduate and graduate students receive a focused, technologically based education.
assistant

Platform

Udacity

Udacity is a for-profit educational organization founded by Sebastian Thrun, David Stavens, and Mike Sokolsky offering massive open online courses (MOOCs). According to Thrun, the origin of the name Udacity comes from the company's desire to be "audacious for you, the student". While it originally focused on offering university-style courses, it now focuses more on vocational courses for professionals.

You are the designer of this MOOC?
What is your opinion on this resource ?
Content
0/5
Platform
0/5
Animation
0/5