COURSE FACTS
Who is the instructor? Cris Moore, Professor, Santa Fe Institute
PROGRAM SUPPORT
How much does it cost? Nothing. The course is completely free.
How is the course funded? The course is funded by the Santa Fe Institute (SFI) through a combination of grants, foundation funding, and by donations from users. If you would like to donate more information can be found here.
COURSE DESIGN & USE
How does the course work?
Each unit consists of a series of short videos corresponding to several subtopics within the main topic of the unit. The course site and YouTube playlist present the videos in a fixed order, but you are welcome to skip, repeat and otherwise watch the videos in whatever order you prefer. Some units contain interactive excercises or simulations to illustrate certain concepts.
Each unit also contains quizzes (introduced in the videos) and understanding checks. These exercises are intended to help you assess your understanding of the material and are not graded.
COURSE OUTLINE
The course consists of 5 units which cover the following topics:
Unit 1: Easy & Hard
1. Course introduction
2. Two kinds of paths
a. Eulerian & Hamiltonian paths
3. Polynomials vs. exponents
4. Divide & conquer algorithms
5. Big O notation
6. When the details don't matter
Unit 2: Algorithms & Landscapes
1. Divide & conquer redux
2. Dynamic programming
3. Greedy algorithms
4. Landscapes
5. Reductions & translations
6. Lessons so far
7. The best of all possible algorithms
8. Complexity wrap-up
Unit 3: P vs NP
1. Finding vs. checking
2. Circuits & formulas
3. More NP-complete problems
a. Graph coloring, two coloring, etc.
4. P vs. NP problem
5. Existence vs. nonexistence
6. Above & beyond
a. Is a problem NP?
b. PSPACE
c. Complexity hierarchy
Unit 4: Worst-case, Natural, and Random
1. Real world problems
2. Phase transitions
a. XY model, Ising model, percolation
3. Randomness problems
4. Solvability threshold
5. Modeling differential equations
a. Unit clauses
6. Landscapes, clustering, freezing, and hardness
Unit 5: Computation Everywhere
1. Recursive functions
2. Partial recursive functions
3. λ calculus
4. Turing machines
5. The halting problem
6. The grand unified theory of computation
7. The analytical engine
8. Cellular automata
9. Tile-based computation
10. Dynamical systems
a. Beaker's map
COURSE LENGTH
How long is the course designed to take to complete? 6 weeks. We expect that participants will complete about one-half to one unit per week; some will move through the material more quickly, and some more slowly.
CERTIFICATES
Are certificates available for this course? A certificate of completion is not available for this course.
Can I get university credit for this course? No, Complexity Explorer does offer credit for completion of our courses.
COURSE MATERIALS
Is there a required textbook? There is no textbook for this course. Students wishing to continue their study of computation may enjoy Cris' textbook The Nature of Computation, co-authored with Stephan Mertens.
RESOURCES
In what ways am I allowed to use these resources? All the materials on this site are available for your use for any non-commercial purpose. All materials (videos, code, write-ups, etc.) are covered by the Creative Commons Attribution-NonCommercial-ShareAlike License ( http://creativecommons.org/licenses/by-nc-sa/4.0/ ). This states that you may copy, distribute, and transmit the work under the condition that you give attribution to ComplexityExplorer.org, and your use is for non-commercial purposes.
SUBTITLES AND TRANSCRIPTS
Are subtitles available? The Complexity Explorer Project has an on-going project in which users volunteer to create subtitles in different languages. If subtitles are available for a given video they can be accessed in the following way. First, start and pause the video. A tool bar will now be visible along the bottom of the video. Second, click on the gear-shaped button located directly to the right of the “CC” button. A list of available languages will be shown in the middle drop-down menu located in the box the opens after hitting the gear-shaped button. Select the language you would like to use for subtitles and click on it.
How do I download and use subtitles offline? You can download videos and available subtitles to watch offline if you wish. Information on downloading videos is located below under technical requirements.
Can I download a plain text transcript of the video? For any video that has subtitles available, there will also be a plain text transcript (in .txt format) available for download, for each subtitle language available. When you click on Subtitles & Transcripts you will be given all of the language options available, and you can choose to download either the subtitle or the transcript, or both.
ENROLLMENT
Do I have to enroll to take the course? Yes, you need to enroll in order to access the course materials. However, enrollment is easy, quick, and free!
How do I enroll? Go to http://complexityexplorer.org, then to Online Courses, and click the “Enroll” button next to this course. You will be guided through the short enrollment process, and then can immediately begin taking the course.
TIME COMMITMENT
How much time does the course require? Participants should expect to spend about 5-8 hours per week watching lectures, working through problems, quizzes, and understanding checks.
COLLABORATION
What are the rules on collaboration? You are free, and encouraged, to discuss anything with anyone! The course website hosts an online forum for students to discuss the course material, homework, etc.
What is this Forum you've been talking about? The course website hosts a forum in which course participants can post questions, answers, and otherwise discuss the course materials. The forum is your space to get to know and work collaboratively with your fellow students.
TECHNICAL REQUIREMENTS
How do I get the videos to play at a faster rate (e.g., 2x)? Our videos are streamed through YouTube. You can opt in on YouTube for their html5 player, which allows you to speed up or slow down videos. To opt in, go to http://www.youtube.com/html5.
Can I download the videos directly, rather than watching them via YouTube? Yes, just click on the "Download" button that appears above the video screen on the page for each video. We will also make all the videos for each unit available as zip files on the Supplementary Materials page.
ADDITIONAL INFORMATION
What if I have more questions? Please address any other questions you have to admin@complexityexplorer.org.