Skip to content
Skip to navigation
# Engineering & Computer Science

Go to Course## Overview

Cryptography is an indispensable tool for protecting information in computer systems. This introduction to the basic theory and practice of cryptographic techniques used in computer security will explore the inner workings of cryptographic primitives and how to use them correctly. ## Topics Include

## Grading

## Instructors

## Units

## Prerequisites

### Tuition & Fees

## Certificates and Degrees

Go to Course## Overview

## Instructors

## Topics Include

## Prerequisites

Go to Course## Instructors

## Topics Include

## Prerequisites

Go to Course## Course Description

## Course Schedule

#### Course runs through November 3, 2015 - February 2, 2016

**Session 1**: *Basics And Setup *

Basics: Network protocols, audio signals + soundcards and network audio.**Session 2**: *Jacktrip Application + Connection *

Things that go wrong with Jacktrip: Network & Audio. P2P Sessions and Multi-site setups.**Session 3**: *Debugging *

Debug examples of typical problems.**Session 4**: *Polish And Practice *

Polish techniques and spawn more practice sessions.**Session 5**: *Future *

Future of the art and practice of network audio, alternative platforms for network audio.## Instructor

**Chris Chafe**, Professor of Music and Director of CCRMA## Requirements

Go to Course## Course Description

## Schedule

**Session 1:** *The Time Domain: Sound, Digital Audio, PCM Files, Noise Vs. Pitch, A Hint Of Spectra *

a) Sound in Air, Traveling Waves b) Digital Audio, Sampling, Quantization, Aliasing c) Soundfiles, Wavetables, Manipulating PCM d) Pitch (vs. Noise), Spectral Analysis 0.1 e) Time-domain Pitch/Noise Detection: ZeroXings, AMDF, Autocorrelation **Session 2:** *Physics, Oscillators, Sines & Spectra, Spectral/Additive Synthesis *

a) Mass-Spring-Damper system, also simple Pendulum b) Fourier analysis/synthesis, Spectrum Analysis 1.0 c) More on additive Sine-wave synthesis **Session 3:** *Digital Filters, Modal Synthesis *

a) Digital Filters, Finite Impulse Response (FIR) b) Linearity, Time-invariance, Convolution c) Infinite Impulse Response (IIR) Digital Filters d) BiQuad Resonator Filter, Modal Synthesis **Session 4:** *Physical Modeling Synthesis: 1D Systems *

a) 1-D systems, Strings, Modal (Fourier) Solution b) Strings II: Waveguide (D’Alembert) Solution c) 1-D systems, Bars, Tubes, solutions d) Advanced Waveguide Synthesis for 1-D systems **Session 5:** *Physical Modeling II: 2 And 3-D Systems *

a) 2-D systems, plates, drums, higher-order modes Fourier (Sine and/or Modal) Solutions, Waveguide Solutions b) 3-D systems, rooms, resonators, Meshes, Waveguide synthesis c) Resonator/Modal view and solution of 3-D systems Pop bottles and other lumped resonators **Session 6:** *Subtractive Synthesis, Vocal Sounds And Models *

a) Subtractive Synthesis, Voice Synthesis, Formants b) Linear Prediction, LPC c) FOFs d) FM Synthesis: Horns, Bells, Voices**Session 7:** *Grains, Particles And Statistical Models * **Session 8:** *Extending And Refining Physical Synthesis Models *

a) Waveshaping Synthesis, Distortion Modeling b) Time-Varying Systems c) Stiffness, All-Pass Filters, Banded Waveguides d) Commuted Synthesis e) JULIUS on KS, strings, demos **Session 9:** *Tying It All Together: Applications, Sonification, Interactions, And Control *

a) Scanned Synthesis b) Don’t forget the laptop!!! SMELT: c) Controlling Synthesis with game controllers (Wii, mobile TouchOSC, more) d) Walking Synthesis, a complete system e) Procedural Audio: Driving synthesis from process, game state, etc. f) Data set Sonification## What you need to take this course

## Instructors

### Perry Cook

### Julius Smith

Go to Course## About the Course

## FAQ

Go to Course## About the Course

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## FAQ

##

## Instructors

####

#### Matthew O. Jackson, Stanford University

#### Kevin Leyton-Brown, The University of British Columbia

#### Yoav Shoham, Stanford University

Go to Course## About This Course

## Course syllabus

**Introduction to quantum mechanics**

**Schroedinger’s wave equation**

**Getting "quantum" behavior**

**Quantum mechanics of systems that change in time**

**Measurement in quantum mechanics**

**Writing down quantum mechanics simply**

**The hydrogen atom**

**How to solve real problems**

## Prerequisites

## Course Staff

### David Miller

## Frequently Asked Questions

### Required text

Go to Course## About the Course

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## FAQ

## Instructors

#### Jure Leskovec, Stanford University

#### Anand Rajaraman, Stanford University

#### Jeff Ullman, Stanford University

Go to Course## About the Course

## Why Study Automata Theory?

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## Pages

Topic Image:

Date:

Monday, January 4, 2016 to Wednesday, March 16, 2016

- Encryption (single and double key)
- Pseudo-random bit generation
- Authentication
- Electronic commerce (anonymous cash, micropayments)
- Key management, PKI, zero-knowledge protocols

There will be three written homework assignments and two programming projects. Final placement in the class will be determined by the following formula:

0.35 H + 0.35 P + 0.3 F

where:- H is your average score on the four written homework assignments.
- P is the weighted average grade on the two programming projects.
- F is your final exam score.

- Dan Boneh
*Professor*,*Computer Science and Electrical Engineering*

3.0

The course is self-contained, however a basic understanding of probability theory and modular arithmetic will be helpful. The course is intended for advanced undergraduates and masters students.

For course tuition, reduced tuition (SCPD member companies and United States Armed forces), and fees, please click Tuition & Fees.

Date:

Monday, January 4, 2016 to Wednesday, March 16, 2016

Now Open! (Fee Applies.)

New techniques have emerged for both predictive and descriptive learning that help us make sense of vast and complex data sets. The particular focus of this course will be on regression and classification methods as tools for facilitating machine learning. In-class problem solving and discussion sessions will be used and computing will be done in R.

- Lester Mackey
*Assistant Professor*,*Statistics*

- Introduction to supervised learning
- Resampling, cross-validation and the bootstrap
- Model selection and regularization methods
- Tree-based methods, random forests and boosting
- Support-vector machines
- Nonlinear methods and generalized additive models
- Principal components and clustering

First courses in statistics and/or probability, linear algebra, and computer programming.

Date:

Wednesday, October 28, 2015

Course topic:

Overview

Recent cutting-edge, translational research in diagnostics and nano-therapies is having a major influence on how we treat and prevent cancer and cardiovascular diseases. This course covers state-of-the-art and emerging bio-sensors, bio-chips, imaging modalities and nano-therapies studied in the context of human physiology—the nervous system, circulatory system and immune system.

- Shan Wang
*Professor of Electrical Engineering* - Adam de la Zerda
*Assistant Professor, Electrical Engineering*

- 3D and 4D body images
- Cancer
- Cardiovascular disease
- In-vitro diagnostics
- In-vivo imaging
- Ultrasounds
- X-rays

None, however, a basic knowledge of electromagnetism, optics, chemistry, thermodynamics, or human biology will be complementary.

Date:

Sunday, April 19, 2015

Course topic:

Today's vast amount of streaming and video conferencing on the Internet lacks one aspect of musical fun and that's what this course is about: high-quality, near-synchronous musical collaboration. Under the right conditions, the Internet can be used for ultra-low-latency, uncompressed sound transmission. The course teaches open-source (free) techniques for setting up city-to-city studio-to-studio audio links. Distributed rehearsing, production and split ensemble concerts are the goal. Setting up such links and debugging them requires knowledge of network protocols, network audio issues and some ear training.

Basics: Network protocols, audio signals + soundcards and network audio.

Things that go wrong with Jacktrip: Network & Audio. P2P Sessions and Multi-site setups.

Debug examples of typical problems.

Polish techniques and spawn more practice sessions.

Future of the art and practice of network audio, alternative platforms for network audio.

Chris Chafe is a composer, improviser, and cellist, developing much of his music alongside computer-based research. He is Director of Stanford University's Center for Computer Research in Music and Acoustics (CCRMA). At IRCAM (Paris) and The Banff Centre (Alberta), he pursued methods for digital synthesis, music performance, and real-time internet collaboration. CCRMA's SoundWIRE project involves live concertizing with musicians the world over. Online collaboration software including jacktrip and research into latency factors continue to evolve. An active performer either on the net or physically present, his music reaches audiences in dozens of countries and sometimes at novel venues. A simultaneous five-country concert was hosted at the United Nations in 2009. Chafe's works are available from Centaur Records and various online media. Gallery and museum music installations are into their second decade with "musifications" resulting from collaborations with artists, scientists and MD's. Recent work includes the Brain Stethoscope project, PolarTide for the 2013 Venice Biennale, Tomato Quintet for the transLife:media Festival at the National Art Museum of China and Sun Shot played by the horns of large ships in the port of St. Johns, Newfoundland.

• **Equipment**: Computer (Mac or Linux) with installation privileges

• **Software**: ChucK, Jacktrip

Date:

Friday, October 16, 2015 to Monday, February 1, 2016

Course topic:

This course introduces the basics of Digital Signal Processing and computational acoustics, motivated by the vibrational physics of real-world objects and systems. We will build from a simple mass-spring and pendulum to demonstrate oscillation, how to simulate those systems in the computer, and also prove that simple oscillation behaves as a sine wave. From that we move to plucked strings and struck bars, showing both solutions as combined traveling waves and combined sine wave harmonics. We continue to build and simulate more complex systems containing many vibrating objects and resonators (mandolin, drum, plate), and also learn how to simulate echos and room reverberation. Through this process, we will learn about digital signals, filters, oscillators, harmonics, spectral analysis, linear and non-linear systems, particle models, and all the necessary building blocks to synthesize essentially any sound. The free open-source software provided make it possible for anyone to use physical models in their art-making, game or movie sound, or any other application.

a) Sound in Air, Traveling Waves b) Digital Audio, Sampling, Quantization, Aliasing c) Soundfiles, Wavetables, Manipulating PCM d) Pitch (vs. Noise), Spectral Analysis 0.1 e) Time-domain Pitch/Noise Detection: ZeroXings, AMDF, Autocorrelation

a) Mass-Spring-Damper system, also simple Pendulum b) Fourier analysis/synthesis, Spectrum Analysis 1.0 c) More on additive Sine-wave synthesis

a) Digital Filters, Finite Impulse Response (FIR) b) Linearity, Time-invariance, Convolution c) Infinite Impulse Response (IIR) Digital Filters d) BiQuad Resonator Filter, Modal Synthesis

a) 1-D systems, Strings, Modal (Fourier) Solution b) Strings II: Waveguide (D’Alembert) Solution c) 1-D systems, Bars, Tubes, solutions d) Advanced Waveguide Synthesis for 1-D systems

a) 2-D systems, plates, drums, higher-order modes Fourier (Sine and/or Modal) Solutions, Waveguide Solutions b) 3-D systems, rooms, resonators, Meshes, Waveguide synthesis c) Resonator/Modal view and solution of 3-D systems Pop bottles and other lumped resonators

a) Subtractive Synthesis, Voice Synthesis, Formants b) Linear Prediction, LPC c) FOFs d) FM Synthesis: Horns, Bells, Voices

a) Wavelets (just for completeness) b) Granular Synthesis c) Particle Models, Statistical Modal Synthesis d) Wind, Water, Surf, and Other Whooshing Sounds

a) Waveshaping Synthesis, Distortion Modeling b) Time-Varying Systems c) Stiffness, All-Pass Filters, Banded Waveguides d) Commuted Synthesis e) JULIUS on KS, strings, demos

a) Scanned Synthesis b) Don’t forget the laptop!!! SMELT: c) Controlling Synthesis with game controllers (Wii, mobile TouchOSC, more) d) Walking Synthesis, a complete system e) Procedural Audio: Driving synthesis from process, game state, etc. f) Data set Sonification

- Software: ChucK (also optionally STK, PeRColate for Max/MSP, Processing, GL/Glut)
- Recommended (highly) Textbook:

Real Sound Synthesis for Interactive Applications (Kadenze discount available soon!)

- Familiarity with ChucK programming language

Introduction to Programming for Musicians and Digital Artists (Kadenze ChucK course)

Programming for Musicians and Digital Artists (ChucK book, Kadenze Discount)

- Operating system: Mac OS X, Windows, or Linux (Planet CCRMA recommended)
- Desired: familiarity with algebra. no calculus required.
- Helpful to have: some personal sound-making things: a guitar or other stringed instrument, a drum, a kitchen pan, a prayer bowl, glasses, bowls, voice...

Perry R. Cook is Emeritus Professor of Computer Science (also Music) at Princeton University, founding advisor/consultant to social music company SMule, and consulting professor at CalArts, Stanford CCRMA, and University of Arizona. With Dan Trueman, he co-founded the Princeton Laptop Orchestra, which received a MacArthur Digital Learning Initiative Grant in 2005. With Ge Wang, Cook is co-author of the ChucK Programming Language. His newest book is “Programming for Digital Musicians and Artists,” with Ajay Kapur, Spencer Salazar, and Ge Wang. The recipient of a 2003 Guggenheim Fellowship, Cook is (still) working on a new book, "La Bella Voce e La Macchina (the Beautiful Voice and the Machine), A History of Technology and the Expressive Voice." Perry is also co-founder of Kadenze.

Julius O. Smith normally teaches a music signal-processing course sequence and supervises related research at the Center for Computer Research in Music and Acoustics (CCRMA). He is formally a professor of music and (by courtesy) electrical engineering. In 1975, he received his BS/EE degree from Rice University, where he got started in the field of digital signal processing and modeling for control. In 1983, he received the PhD/EE degree from Stanford University, specializing in techniques for digital filter design and system identification, with application to violin modeling. His work history includes the Signal Processing Department at Electromagnetic Systems Laboratories, Inc., working on systems for digital communications, the Adaptive Systems Department at Systems Control Technology, Inc., working on research problems in adaptive filtering and spectral estimation, and NeXT Computer, Inc., where he was responsible for sound, music, and signal processing software for the NeXT computer workstation. Prof. Smith is a Fellow of the Audio Engineering Society and the Acoustical Society of America. He is the author of four online books and numerous research publications in his field.

Date:

Monday, September 28, 2015 to Saturday, November 21, 2015

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.

**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:

Friday, September 11, 2015 to Saturday, November 7, 2015

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:

Tuesday, September 29, 2015 to Thursday, December 24, 2015

Course topic:

This 9 week course aims to teach quantum mechanics to anyone with a reasonable college-level understanding of physical science or engineering. Quantum mechanics was once mostly of interest to physicists, chemists and other basic scientists. Now the concepts and techniques of quantum mechanics are essential in many areas of engineering and science such as materials science, nanotechnology, electronic devices, and photonics. This course is a substantial introduction to quantum mechanics and how to use it. It is specifically designed to be accessible not only to physicists but also to students and technical professionals over a wide range of science and engineering backgrounds.

How quantum mechanics is important in the everyday world, the bizarre aspects and continuing evolution of quantum mechanics, and how we need it for engineering much of modern technology.

Getting to Schroedinger’s wave equation. Key ideas in using quantum mechanical waves — probability densities, linearity. The "two slit" experiment and its paradoxes.

The "particle in a box", eigenvalues and eigenfunctions. Mathematics of quantum mechanical waves.

Time variation by superposition of wave functions. The harmonic oscillator. Movement in quantum mechanics — wave packets, group velocity and particle current.

Operators in quantum mechanics — the quantum-mechanical Hamiltonian. Measurement and its paradoxes — the Stern-Gerlach experiment.

A simple general way of looking at the mathematics of quantum mechanics — functions, operators, matrices and Dirac notation. Operators and measurable quantities. The uncertainty principle.

Angular momentum in quantum mechanics — atomic orbitals. Quantum mechanics with more than one particle. Solving for the the hydrogen atom. Nature of the states of atoms.

Approximation methods in quantum mechanics.

The course is approximately at the level of a first quantum mechanics class in physics at a third-year college level or above, but it is specifically designed to be suitable and useful also for those from other science and engineering disciplines.

The course emphasizes conceptual understanding rather than a heavily mathematical approach, but some amount of mathematics is essential for understanding and using quantum mechanics. The course presumes a mathematics background that includes basic algebra and trigonometry, functions, vectors, matrices, complex numbers, ordinary differential and integral calculus, and ordinary and partial differential equations.

In physics, students should understand elementary classical mechanics (Newton’s Laws) and basic ideas in electricity and magnetism at a level typical of first-year college physics. (The course explicitly does not require knowledge of more advanced concepts in classical mechanics, such as Hamiltonian or Lagrangian approaches, or in electromagnetism, such as Maxwell’s equations.) Some introductory exposure to modern physics, such as the ideas of electrons, photons, and atoms, is helpful but not required.

The course includes an optional and ungraded “refresher” background mathematics section that reviews and gives students a chance to practice all the necessary math background background. Introductory background material on key physics concepts is also presented at the beginning of the course.

David Miller is the W. M. Keck Foundation Professor of Electrical Engineering and, by Courtesy, Professor of Applied Physics, both at Stanford University. He received his B. Sc. and Ph. D. degrees in Physics in Scotland, UK from St. Andrews University and Heriot-Watt University, respectively. Before moving to Stanford in 1996, he worked at AT&T Bell Laboratores for 15 years. His research interests have included physics and applications of quantum nanostructures, including invention of optical modulator devices now widely used in optical fiber communications, and fundamentals and applications of optics and nanophotonics. He has received several awards and honorary degrees for his work, is a Fellow of many major professional societies in science and engineering, including the Royal Society of London, and is a member of both the National Academy of Sciences and the National Academy of Engineering in the US. He has taught quantum mechanics at Stanford for more than 10 years to a broad range of students ranging from physics and engineering undergraduates to graduate engineers and scientists in many disciplines.

The text “Quantum Mechanics for Scientists and Engineers” (Cambridge, 2008) is recommended for the course, though it is not required. It follows essentially the same syllabus, has additional problems and exercises, allows you to go into greater depth on some ideas, and also contains many additional topics for further study.

Date:

Saturday, September 12, 2015 to Saturday, October 31, 2015

Course topic:

We introduce the participant to modern distributed file systems and MapReduce, including what distinguishes good MapReduce algorithms from good algorithms in general. The rest of the course is devoted to algorithms for extracting models and information from large datasets. Participants will learn how Google's PageRank algorithm models importance of Web pages and some of the many extensions that have been used for a variety of purposes. We'll cover locality-sensitive hashing, a bit of magic that allows you to find similar items in a set of items so large you cannot possibly compare each pair. When data is stored as a very large, sparse matrix, dimensionality reduction is often a good way to model the data, but standard approaches do not scale well; we'll talk about efficient approaches. Many other large-scale algorithms are covered as well, as outlined in the course syllabus.

Week 1:

MapReduce

Link Analysis -- PageRank

Week 2:

Locality-Sensitive Hashing -- Basics + Applications

Distance Measures

Nearest Neighbors

Frequent Itemsets

Week 3:

Data Stream Mining

Analysis of Large Graphs

Week 4:

Recommender Systems

Dimensionality Reduction

Week 5:

Clustering

Computational Advertising

Week 6:

Support-Vector Machines

Decision Trees

MapReduce Algorithms

Week 7:

More About Link Analysis -- Topic-specific PageRank, Link Spam.

More About Locality-Sensitive Hashing

A course in database systems is recommended, as is a basic course on algorithms and data structures. You should also understand mathematics up to multivariable calculus and linear algebra.

There is a free book "Mining of Massive Datasets, by Leskovec, Rajaraman, and Ullman (who by coincidence are the instructors for this course :-). You can download it at http://www.mmds.org/ Hardcopies can be purchased from Cambridge Univ. Press.

There will be about 2 hours of video to watch each week, broken into small segments. There will be automated homeworks to do for each week, and a final exam.

**Will I get a Statement of Accomplishment after completing this class?**Yes. Participants who successfully complete the class will receive a Statement of Accomplishment signed by the instructors. A level designated "distinction" will also be offered.

Date:

Saturday, September 12, 2015 to Thursday, November 5, 2015

Course topic:

I am pleased to be able to offer free over the Internet a course on Automata Theory, based on the material I have taught periodically at Stanford in the course CS154. Participants 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.

Week 1: Finite Automata

Week 2: Regular Expressions and Properties of Regular Languages

Week 3: Context-Free Grammars and Languages

Week 4: Properties of Context-Free Languages, plus introduction to Turing Machines

Week 5: Turing Machines and Undecidability

Week 6: Intractable Problems (NP-Completeness)

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 or Python 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 familiar with neither Java nor Python, 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.

3-4 lecture videos each week. Many of these videos are longer than the typical MOOC video, so feel free to pause them and view them in several sessions of your own choice.

There will be 1-2 problem sets each week, which together count for 50% of the marks. You can repeat them until you get them all correct, and they are due two Mondays after release of the videos on which they are based.

There are also two optional programming challenges.

FAQ:

**Will I get a statement of accomplishment after completing this class?**Yes. Participants 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