Skip to content Skip to navigation

Engineering & Computer Science

Topic Image: 
Engineering and Computer Science
Monday, January 4, 2016 to Wednesday, March 16, 2016
Go to Course


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

  • 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

  • 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 ProfessorComputer Science and Electrical Engineering




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.

Tuition & Fees

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


Introduction to Cryptography

View All Courses

Access learning material from upcoming, self-study, and completed courses...

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

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.


Topics Include

  • 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.

View All Courses

Access learning material from upcoming, self-study, and completed courses...

Wednesday, October 28, 2015
Go to Course


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

Topics Include

  • 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.


View All Courses

Access learning material from upcoming, self-study, and completed courses...

Sunday, April 19, 2015
Go to Course

Course Description

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.

Course Schedule

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

Session 1Basics And Setup 
Basics: Network protocols, audio signals + soundcards and network audio.
Session 2Jacktrip Application + Connection 
Things that go wrong with Jacktrip: Network & Audio. P2P Sessions and Multi-site setups.
Session 3Debugging 
Debug examples of typical problems.
Session 4Polish And Practice 
Polish techniques and spawn more practice sessions.
Session 5Future 
Future of the art and practice of network audio, alternative platforms for network audio.


Chris Chafe, Professor of Music and Director of CCRMA

    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


    Online Jamming and Concert Technology

    View All Courses

    Access learning material from upcoming, self-study, and completed courses...

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

    Course Description

    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.


    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 
    a) Wavelets (just for completeness) b) Granular Synthesis c) Particle Models, Statistical Modal Synthesis d) Wind, Water, Surf, and Other Whooshing Sounds
    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

    • 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 Cook

      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 Smith

        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.


        Physics Based Sound Synthesis

        View All Courses

        Access learning material from upcoming, self-study, and completed courses...

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

        About the Course

        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.

        View All Courses

        Access learning material from upcoming, self-study, and completed courses...

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

        About the Course

        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.

        Course Syllabus

        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.

        Recommended Background

        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).

        Suggested Readings

        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.), 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.

        Course Format

        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.




        Matthew O. Jackson, Stanford University

        Kevin Leyton-Brown, The University of British Columbia

        Yoav Shoham, Stanford University


        Game Theory II : Advanced Applications

        View All Courses

        Access learning material from upcoming, self-study, and completed courses...

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

        About This Course

        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.

        Course syllabus

        Introduction to quantum mechanics

        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.

        Schroedinger’s wave equation

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

        Getting "quantum" behavior

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

        Quantum mechanics of systems that change in time

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

        Measurement in quantum mechanics

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

        Writing down quantum mechanics simply

        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.

        The hydrogen atom

        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.

        How to solve real problems

        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.

        Course Staff

        David Miller

        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.

        Frequently Asked Questions

        Required text

        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.


        Quantum Mechanics for Scientists and Engineers 2  Course Image

        View All Courses

        Access learning material from upcoming, self-study, and completed courses...

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

        About the Course

        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.

        Course Syllabus

        Week 1:
        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:
        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

        Recommended Background

        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.

        Suggested Readings

        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  Hardcopies can be purchased from Cambridge Univ. Press.

        Course Format

        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.


        Jure Leskovec, Stanford University

        Anand Rajaraman, Stanford University

        Jeff Ullman, Stanford University


        Mining course feature image

        View All Courses

        Access learning material from upcoming, self-study, and completed courses...

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

        About the Course

        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.

        Why Study Automata Theory?

        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.

        Course Syllabus

        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)

        Recommended Background

        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 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.

        Suggested Readings

        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.

        Course Format

        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.


        • 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.

        Jeff Ullman

        View All Courses

        Access learning material from upcoming, self-study, and completed courses...


        Subscribe to RSS - Engineering & Computer Science