Skip to content
Skip to navigation
# Engineering & Computer Science

Go to Course## Why Study Automata Theory?

## Recommended Background

## Suggested Readings

## FAQ

Go to Course## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## FAQ

Go to Course
Go to Course
Go to Course
Go to Course## Course Structure

Go to Course## Recommended Background

Go to Course## About the Course

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

Grading will be based on class participation (10%), homework (40%), and the final project (50%). The best final projects in each category (e.g. genomics, transportation, law, etc.) will qualify for prizes sponsored by startups.##

Go to Course
Go to Course
## Pages

Topic Image:

Date:

Monday, November 4, 2013

Course topic:

Automata Theory is a course based on the material has been taught periodically at Stanford in the course CS154. Students have access to screencast lecture videos, are given quiz questions, assignments and exams, receive regular feedback on progress, and can participate in a discussion forum. Those who successfully complete the course will receive a statement of accomplishment. You will need a decent Internet connection for accessing course materials, but should be able to watch the videos on your smartphone.

The course covers four broad areas: (1) Finite automata and regular expressions, (2) Context-free grammars, (3) Turing machines and decidability, and (4) the theory of intractability, or NP-complete problems.

This subject is not just for those planning to enter the field of complexity theory, although it is a good place to start if that is your goal. Rather, the course will emphasize those aspects of the theory that people really use in practice. Finite automata, regular expressions, and context-free grammars are ideas that have stood the test of time. They are essential tools for compilers. But more importantly, they are used in many systems that require input that is less general than a full programming language yet more complex than "push this button."

The concepts of undecidable problems and intractable problems serve a different purpose. Undecidable problems are those for which no computer solution can ever exist, while intractable problems are those for which there is strong evidence that, although they can be solved by a computer, they cannot be solved sufficiently fast that the solution is truly useful in practice. Understanding this theory, and in particular being able to prove that a problem you are facing belongs to one of these classes, allows you to justify taking another approach — simplifying the problem or writing code to approximate the solution, for example.

During the course, I'm going to prove a number of things. The purpose of these proofs is not to torture you or confuse you. Neither are the proofs there because I doubt you would believe me were I merely to state some well-known fact. Rather, understanding how these proofs, especially inductive proofs, work, lets you think more clearly about your own work. I do not advocate proofs that programs are correct, but whenever you attempt something a bit complex, it is good to have in mind the inductive proofs that would be needed to guarantee that what you are doing really works in all cases.

You should have had a second course in Computer Science — one that covers basic data structures (e.g., lists, trees, hashing), and basic algorithms (e.g., tree traversals, recursive programming, big-oh running time). In addition, a course in discrete mathematics covering propositional logic, graphs, and inductive proofs is valuable background.

If you need to review or learn some of these topics, there is a free on-line textbook Foundations of Computer Science, written by Al Aho and me, available at http://i.stanford.edu/~ullman/focs.html. Recommended chapters include 2 (Recursion and Induction), 3 (Running Time of Programs), 5 (Trees), 6 (Lists), 7 (Sets), 9 (Graphs), and 12 (Propositional Logic). You will also find introductions to finite automata, regular expressions, and context-free grammars in Chapters 10 and 11. Reading Chapter 10 would be good preparation for the first week of the course.

The course includes two programming exercises for which a knowledge of Java is required. However, these exercises are optional. You will receive automated feedback, but the results will not be recorded or used to grade the course. So if you are not familiar with Java, you can still take the course without concern for prerequisites.

The course is built around the material in Automata Theory, Languages, and Computation 3rd edition (2007), by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Addison-Wesley. However, you do not have to buy a copy of this book. The course is self-contained, and all homeworks and exams are based solely on concepts taught in the video lectures.

**Will I get a statement of accomplishment after completing this class?**Yes. Students who successfully complete the class will receive a statement of accomplishment signed by the instructor.

**What is the format of the class?**The class will consist of lecture videos, which are between 15 and 45 minutes in length. These contain integrated quiz questions. There will also be standalone homeworks that are not part of video lectures, optional programming assignments, and a (not optional) final exam.

**How much work will I be expected to do in this class?**You need to work about 5-10 hours per week to complete the course. About 2 hours of video segments each week, containing inline ungraded quiz questions. A weekly, graded multiple choice homework.

Instructor(s):

Jeff Ullman

Date:

Monday, October 14, 2013

Course topic:

Popularized by movies such as "A Beautiful Mind", game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Beyond what we call 'games' in common language, such as chess, poker, soccer, etc., it includes the modeling of conflict among nations, political campaigns, competition among firms, and trading behavior in markets such as the NYSE. How could you begin to model eBay, Google keyword auctions, and peer to peer file-sharing networks, without accounting for the incentives of the people using them? The course will provide the basics: representing games and strategies, the extensive form (which computer scientists call game trees), Bayesian games (modeling things like auctions), repeated and stochastic games, and more. We'll include a variety of examples including classic games and real-world applications.

Week 1. Introduction: Introduction, overview, uses of game theory, some applications and examples, and formal definitions of: the normal form, payoffs, strategies, pure strategy Nash equilibrium, dominated strategies.

Week 2. Mixed-strategy Nash equilibria: Definitions, examples, real-world evidence.

Week 3. Alternate solution concepts: iterative removal of strictly dominated strategies, minimax strategies and the minimax theorem for zero-sum game, correlated equilibria.

Week 4. Extensive-form games: Perfect information games: trees, players assigned to nodes, payoffs, backward Induction, subgame perfect equilibrium, introduction to imperfect-information games, mixed versus behavioral strategies.

Week 5. Repeated games: Repeated prisoners dilemma, finite and infinite repeated games, limited-average versus future-discounted reward, folk theorems, stochastic games and learning.

Week 6. Coalitional games: Transferable utility cooperative games, Shapley value, Core, applications.

Week 7. Bayesian games: General definitions, ex ante/interim Bayesian Nash equilibrium.

You must be comfortable with mathematical thinking and rigorous arguments. Relatively little specific math is required; the course involves lightweight probability theory (for example, you should know what a conditional probability is) and very lightweight calculus (for instance, taking a derivative).

The following background readings provide more detailed coverage of the course material:

- Essentials of Game Theory, by Kevin Leyton-Brown and Yoav Shoham; Morgan and Claypool Publishers, 2008. This book has the same structure as the course, and covers most of the same material. It is free if you access the link from a school that subscribes to the Morgan & Claypool Synthesis Lectures, and otherwise costs $5 to download. You can also get it as a printed book from (e.g.) amazon.com, or as an ebook for Kindle or Google devices.
- A Brief Introduction to the Basics of Game Theory, by Matthew O. Jackson. These notes offer a quick introduction to the basics of game theory; they are available as a free PDF download.

The course consists of the following materials:

- Videos. The lectures are delivered via videos, which are broken into small chunks, usually between five and fifteen minutes each. There will be approximately one and a half hours of video content per week. You may watch the lecture videos at your convenience. Lower-resolution videos are also available for those with slow internet connections.
- Slides. We have made available pdf files of all the lecture slides.
- Quizzes. There will be non-graded short "quiz" questions that will follow some of the videos to help you gauge your understanding.
- Online Lab Exercises After some of the videos, we will ask you to go online to play some games. These are entirely optional, and are designed to illustrate some of the concepts from the course.
- Problem Sets. There will also be graded weekly problem sets that you will also answer online, but may work through offline; those must be completed within two weeks of the time that they are posted in order to be graded for full credit. If you miss a problem set deadline, you may complete it before the end of the course for half credit. You may discuss problems from the problem sets with other students in an online forum, without providing explicit answers.
- Final Exam. There will be an online final exam that you will have to complete within two weeks of its posting. Once you begin the exam, you will have four hours to complete it.
- Screen-side Chats. A couple of times during the course, we will hold a brief online chat where we answer questions and discuss topics relevant to the course.

**Will I get a statement of accomplishment after completing this class?**Yes. Students who successfully complete the class will receive a statement of accomplishment signed by the instructors.

Date:

Monday, October 14, 2013

Course topic:

Machine learning is the science of getting computers to act without being explicitly programmed. In the past decade, machine learning has given us self-driving cars, practical speech recognition, effective web search, and a vastly improved understanding of the human genome. Machine learning is so pervasive today that you probably use it dozens of times a day without knowing it. Many researchers also think it is the best way to make progress towards human-level AI. In this class, you will learn about the most effective machine learning techniques, and gain practice implementing them and getting them to work for yourself. More importantly, you'll learn about not only the theoretical underpinnings of learning, but also gain the practical know-how needed to quickly and powerfully apply these techniques to new problems. Finally, you'll learn about some of Silicon Valley's best practices in innovation as it pertains to machine learning and AI.

This course provides a broad introduction to machine learning, datamining, and statistical pattern recognition. Topics include: (i) Supervised learning (parametric/non-parametric algorithms, support vector machines, kernels, neural networks). (ii) Unsupervised learning (clustering, dimensionality reduction, recommender systems, deep learning). (iii) Best practices in machine learning (bias/variance theory; innovation process in machine learning and AI). The course will also draw from numerous case studies and applications, so that you'll also learn how to apply learning algorithms to building smart robots (perception, control), text understanding (web search, anti-spam), computer vision, medical informatics, audio, database mining, and other areas.

FAQ:

**What is the format of the class?**The class will consist of lecture videos, which are broken into small chunks, usually between eight and twelve minutes each. Some of these may contain integrated quiz questions. There will also be standalone quizzes that are not part of video lectures, and programming assignments.

**How much programming background is needed for the course?**The course includes programming assignments and some programming background will be helpful.

**Do I need to buy a textbook for the course?**No, it is self-contained.

**Will I get a statement of accomplishment after completing this class?**Yes. Students who successfully complete the class will receive a statement of accomplishment signed by the instructor.

Instructor(s):

Andrew Ng

Date:

Monday, September 30, 2013

Course topic:

Logic is one of the oldest intellectual disciplines in human history. It dates back to the times of Aristotle; it has been studied through the centuries; and it is still a subject of active investigation today.

This course is a basic introduction to Logic. It shows how to formalize information in form of logical sentences. It shows how to reason systematically with this information to produce all logical conclusions and only logical conclusions. And it examines logic technology and its applications - in mathematics, science, engineering, business, law, and so forth.

The course differs from other introductory courses in Logic in two important ways. First of all, it teaches a novel theory of logic that improves accessibility while preserving rigor. Second, the material is laced with interactive demonstrations and exercises that suggest the many practical applications of the field.

FAQ:

**Will I get a statement of accomplishment after completing this class?**Yes. Participants who successfully complete the course will receive a statement of accomplishment signed by the instructor.

**What is the format of the class?**The class consists of videos, notes, and a few background readings. The videos include interactive demonstrations and exercises. There are also standalone quizzes that are not part of video lectures. Workload: one to two hours of video content per week.

**What should I know to take this class?**The course has no prerequisites beyond high school mathematics. You should be comfortable with symbolic manipulation techniques, as used, for example, in solving simple algebra problems. And you need to understand sets, functions, and relations. However, that's all. If you have this background, you should be fine.

**Do I need to buy any textbooks?**None is required, as the course is self-contained.

Date:

Monday, September 16, 2013

Course topic:

This course introduces the fundamentals of technology entrepreneurship, pioneered in Silicon Valley and now spreading across the world. You will learn the process technology entrepreneurs use to start companies. It involves taking a technology idea and finding a high-potential commercial opportunity, gathering resources such as talent and capital, figuring out how to sell and market the idea, and managing rapid growth. To gain practical experience alongside the theory, students form teams and work on startup projects in those teams.

This is the second offering of the class. Last time, nearly 40,000 students from around the world participated and worked in teams together. The top teams were matched with Silicon Valley mentors, and the best teams at the end of the class pitched their ideas to investors. Many of the alumni of the last class are continuing to build their startups and will be mentoring teams this time.

By the conclusion of the course, it is our hope that you understand how to:

- Articulate a process for taking a technology idea and finding a high-potential commercial opportunity (high performing students will be able to discuss the pros and cons of alternative theoretical models).
- Create and verify a plan for gathering resources such as talent and capital.
- Create and verify a business model for how to sell and market an entrepreneurial idea.
- Generalize this process to an entrepreneurial mindset of turning problems into opportunities that can be used in larger companies and other settings.

**Workload:** 10 hours per week.

**Technical Requirements: **You need a computer that allows you to watch the video lectures, and the ability to upload your assignments which will be reports and powerpoint/video presentations.

**Statement of Accomplishment:** Subject to satisfactory performance and course completion, you will receive a statement of accomplishment signed by the instructor. This statement will not stand in the place of a course taken at Stanford or an accredited institution.

Instructor(s):

Chuck Eesley

Date:

Tuesday, September 24, 2013

Course topic:

This course focuses on the operating principles and applications of emerging technological solutions to the energy demands of the world. We will begin with discussing the scale of global energy usage and requirements for possible solutions. Basic physics and chemistry of solar cells, fuel cells, and batteries will be discussed in quantitative detail. We will explore performance issues, including economics, from the ideal device to the installed system. Finally, we will end with the promise of materials research for providing next generation solutions.

The course will be delivered in the form of weekly units. Each unit will usually be structured around a particular topic/subtopic and will include videos interspersed with formative exercises and reading resources from the internet or content made available. Each unit will be followed by a graded problem set due that week. The course will also have a final exam. Grades will solely be based on the problem sets and the final exam. An optional home project will also be announced later in the course.

Date:

Monday, September 30, 2013

Course topic:

General game players are computer systems able to play strategy games based solely on formal game descriptions supplied at "runtime". (In other words, they don't know the rules until the game starts.) Unlike specialized game players, such as Deep Blue, general game players cannot rely on algorithms designed in advance for specific games; they must discover such algorithms themselves. General game playing expertise depends on intelligence on the part of the game player and not just intelligence of the programmer of the game player.

This course is an introduction to General Game Playing (GGP). Students will get an introduction to the theory of General Game Playing and will learn how to create GGP programs capable of competing against other programs and humans.

GGP is an interesting application in its own right. It is intellectually engaging and more than a little fun. But it is much more than that. It provides a theoretical framework for modeling discrete dynamic systems and for defining rationality in a way that takes into account problem representation and complexities like incompleteness of information and resource bounds. It has practical applications in areas where these features are important, e.g. in business and law. More fundamentally, it raises questions about the nature of intelligence and serves as a laboratory in which to evaluate competing approaches to artificial intelligence.

This course is an introduction to General Game Playing (GGP). Students will get an introduction to the theory of General Game Playing and will learn how to create GGP programs capable of competing against other programs and humans.

Students should be familiar with Symbolic Logic and should be able to read and understand program fragments written in a modern programming language. This background is sufficient for understanding the presentation and for configuring players to compete in competitions (using software components provided by the instructors). Students who wish to modify the standard components or who wish to build their own players also need the ability to develop programs on their own. This latter ability is desirable but not required.

Date:

Monday, June 17, 2013

Course topic:

Spiritual sequel to Peter Thiel's CS183 course on startups. Bridges the gap between academic computer science and production software engineering. Fast-paced introduction to key tools and techniques (command line, dotfiles, text editor, distributed version control, debugging, testing, documentation, reading code, deployments), featuring guest appearances by senior engineers from successful startups and large-scale academic projects. Over the course of the class, students will build a command line application, expose it as a web service, and then link other students' applications and services together to build an HTML5 mobile app. General principles are illustrated through modern Javascript and the latest web technologies, including Node, Backbone, Coffeescript, Bootstrap, Git, and Github.

The syllabus is optimized to enable students to iterate on their final projects as soon as possible, with technical material in the first half of the class and entrepreneurial considerations in the second half.

- Introduction and Quickstart
- Tools: VMs, IAAS/PAAS, Unix Command Line, Text Editors, DCVS
- Frontend: HTML/CSS/JS, Wireframing, Market Research
- Backend: SSJS, Databases, Frameworks, Data Pipelines
- APIs: Client-side templating, HTTP, SOA/REST/JSON, API as BizDev
- Devops: Testing, Deployment, CI, Monitoring, Performance
- Dev Scaling: DRY, Reading/Reviewing/Documenting Code, Parallelizing
- Founding: Conception, Composition, Capitalization
- Business Scaling: Promotion, CAC/LTV/Funnel, Regulation, Accounting
- Summary and Demo Week

Familiarity with basic programming at the level of Stanford's CS106B is required. Some exposure to HTML, CSS, and Javascript will also be helpful.

To get a sense of the energy humming through Silicon Valley, the following reading will be helpful:

- First, for the big picture read
*Why Software is Eating the World*,*The Rise and Fall of Personal Computing*, and*Internet Trends*. - Next, look at these articles on Stanford's Facebook class,
*The Social Network*, and*Massively Collaborative Mathematics*. - Finally, read
*Startup = Growth*and as much of the CS183 notes as you can.

This class takes up where CS183 left off.

The first half of the course will cover modern software engineering principles with a focus on mobile HTML5 development, taught via 5-10 minute video lectures with in-class questions, programming assignments, and quizzes. Guest lecturers from top Silicon Valley startups will bring these concepts to life with real engineering problems from their work.

In the second half, you will apply these concepts to develop a simple command line application, expose it as a webservice, and then integrate other students' command line apps and webservices together with yours to create an open-source mobile HTML5 app as a final project. Lectures will continue in the second half, but will be focused on the design, marketing, and logistical aspects of creating and scaling a startup. No other homework will be given in the second half to permit full focus on the final project.

Grading will be based on class participation (10%), homework (40%), and the final project (50%). The best final projects in each category (e.g. genomics, transportation, law, etc.) will qualify for prizes sponsored by startups.

FAQ:

**Will I get a certificate after completing this class?**Yes. Students who successfully complete the class will receive a certificate signed by the instructor.**What audiences will benefit most from this class?**

The class will be particularly useful for CS undergrads, grad students or alumni in other STEM disciplines, people looking to found or join a startup, and new startup hires.**What resources will I need for this class?**You will need an internet connection and the ability to sign up for free Amazon Web Servicesand Github accounts.**What is the coolest thing I'll learn if I take this class?**You will learn how to turn knowledge into power.

Instructor(s):

Balaji S. Srinivasan

Vijay S. Pande

Date:

Tuesday, April 23, 2013

Course topic:

In this research-oriented graduate course, we will study algorithms for graph partitioning and clustering, constructions of expander graphs, and analysis of random walks. These are three topics that build on the same mathematical background and that have several important connections: for example it is possible to find graph clusters via random walks, and it is possible to use the linear programming approach to graph partitioning as a way to study random walks.

We will study spectral graph theory, which explains how certain combinatorial properties of graphs are related to the eigenvalues and eigenvectors of the adjacency matrix, and we will use it describe and analyze spectral algorithms for graph partitioning and clustering. Spectral graph theory will recur as an important tool in the rest of the course. We we will also discuss other approaches to graph partitioning via linear programming and semidefinite programming. Then we will study constructions of expander graphs, which are graphs with very strong pseudorandomness properties, which are useful in many applications, including in cryptography, in complexity theory, in algorithms and data structures, and in coding theory. Finally, we will study the mixing time of random walks, a problem that comes up in several applications, including the analysis of the convergence time of certain randomized algorithms, such as the Metropolis algorithm.

**Workload**

about 8 hours per week

**Prerequisites**

linear algebra, discrete probability, and algorithms

Date:

Wednesday, June 13, 2012

Course topic:

This course covers a broad range of topics in natural language processing, including word and sentence tokenization, text classification and sentiment analysis, spelling correction, information extraction, parsing, meaning extraction, and question answering, We will also introduce the underlying theory from probability, statistics, and machine learning that are crucial for the field, and cover fundamental algorithms like n-gram language modeling, naive bayes and maxent classifiers, sequence models like Hidden Markov Models, probabilistic dependency and constituent parsing, and vector-space models of meaning.

We are offering this course on Natural Language Processing free and online to students worldwide, continuing Stanford's exciting forays into large scale online instruction. Students have access to screencast lecture videos, are given quiz questions, assignments and exams, receive regular feedback on progress, and can participate in a discussion forum. Those who successfully complete the course will receive a statement of accomplishment. Taught by Professors Jurafsky and Manning, the curriculum draws from Stanford's courses in Natural Language Processing. You will need a decent internet connection for accessing course materials, but should be able to watch the videos on your smartphone.

Instructor(s):

Dan Jurafsky

Christopher Manning