At some point in your life, addition was difficult. Then you learned how to do it, and now it’s not! This concept of difficulty, at least on the surface, seems to be a subjective one.

But is it? What if we could invent the ultimate computer? One that made today’s best supercomputer look like an abacus. Surely then a skilled programmer with superstar abilities could solve any problem! Right?

Well… no. Some problems, as it turns out, are fundamentally difficult and some are truly impossible for any computer to solve. As computer programmers, it is our duty to delve deep into this realm of computational capability. In Udacity’s new course, Introduction to Theoretical Computer Science: Dealing with Challenging Problems (CS 313), which begins on October 1, you will do exactly this.

As Sebastian Wernicke, the instructor for this course, puts it, “Theoretical computer science is about what computers can and cannot do. It shows us the fundamental capabilities and limitations of computation itself. Simple problems no computer can ever solve. Complicated problems that are actually easy. Anyone serious about computer science should know this.”

But if some problems really are impossible, why bother learning about them? Sebastian puts it nicely: “One of the most exciting things for me is that theoretical computer science often sounds ‘depressing’ because many famous results will tell you ‘a computer cannot do that. Ever.’ Yet when you look closely at these results and try to understand them, you can often find pretty neat ‘loopholes’ that will tell you ‘yes, a computer CAN do that as long as you tread carefully and put some thought into the process.’ Not many people know this.”

Even if you’ve taken a course on computational theory, this will still offer something new. In designing this course, Sebastian took a fresh approach. He believes that “many courses on theoretical computer science are very formal and focus on the theoretical insights and ‘depressing’ results, i.e., things a computer cannot do.” In this course, you will learn the practical side of theory: how to recognize and quantify the difficulty of a problem and what you can do to solve it.

This course assumes a knowledge of computer programming and a familiarity with algorithms. If you’re intimidated by such a theoretical course, don’t be! In the strictest sense of the word, it won’t be difficult.

So what are you waiting for? Sign up now!

I'm really looking forward to this class. I am curious though, since theory classes are largely about doing proofs and such, about how we'll be quizzed and tested on the material.

I've been waiting so long for this course I hope that some more unconventional models like BSS model or Wang machine will be touched in this class.

Hi Isabel!This class is definitely going to be introductory, so I don't believe Sebastian planned on covering anything terribly unconventional. It's designed primarily to interest programmers new to theory, and make them aware of how a knowledge of these subjects can help them.

Hi Isabel!the course is an introduction to Theoretical Computer Science and as such it focuses on the science of "hard"/"intractable" problems (i.e., NP-completeness and a bit of computability) and what to do with these problems in practice (other than just giving up). We won't cover many machine models besides a RAM, there also won't be any automata or grammars.

Hi Sebastian,Thank you for your answer. I already took a course on theoretical CS at my Uni but it was mainly about automata and grammars. I really love automata but 99% of the other students hated it. 😉 Our class about complexity is a elective course for master students but since most students already hated the introductory course, only very few (or none) want to chose the complexity

This comment has been removed by a blog administrator.

This comment has been removed by a blog administrator.