Skip to content
Skip to navigation
# Engineering & Computer Science

Go to Course
Go to Course## Prerequisites

### Aneesh Nainani

Go to Course
## CONCEPTS

Go to Course## FAQ

Go to Course## Course Syllabus

**Weeks 1 and 2**: The greedy algorithm design paradigm. Applications to optimal caching and scheduling. Minimum spanning trees and applications to clustering. The union-find data structure. Optimal data compression.

**Weeks 3 and 4**: The dynamic programming design paradigm. Applications to the knapsack problem, sequence alignment, shortest-path routing, and optimal search trees.

**Weeks 5 and 6**: Intractable problems and what to do about them. NP-completeness and the P vs. NP question. Solvable special cases. Heuristics with provable performance guarantees. Local search. Exponential-time algorithms that beat brute-force search.## Recommended Background

## Suggested Readings

## Course Format

## FAQ

Go to Course## FAQ

Go to Course## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## FAQ

Go to Course## Recommended Background

Go to Course## Why Study Compilers?

Go to Course
## Pages

Topic Image:

Date:

Monday, June 16, 2014 to Monday, August 25, 2014

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:

Tuesday, July 1, 2014 to Friday, August 8, 2014

Course topic:

We are all too familiar with ours iPhones, iPads, and other smartphones and tablets that we use every day. Have you ever wondered what are the chips and components inside them? how much they cost ? And how they are manufactured? In this course we will learn about ‘Nanomanufacturing’ which is the underlying technology to make the different semiconductor chips and components that enable these devices.

We will ponder upon issues like: how the post-PC era is changing the semiconductor industry? What’s ailing Moore’s law? I will combine my experience from teaching this course at Stanford and my work in the industry to make you aware of the ‘state of art’ in the semiconductor and display industry. We will lots of fun too! I will take you on field trips where you can check out some of the action with me.

What we will cover in each of the 6 weeks is described in more details below; if that piques your interest, please sign up. I look forward to seeing you in class!

Working knowledge of process technology and semiconductors.

FAQ:

**Will I get a statement of accomplishment after completing this class??**

Yes. Students who successfully complete the class will receive a statement of accomplishment

**What is the format of the class?**

The class will consist of screencast videos (read Khan Academy style videos), which are usually between eight and thirteen minutes each. Many of these will contain integrated quiz questions. I prefer to not use slides in my videos, and most of them are unscripted and minimally produced.

**Is there a project involved?**

Yes, there is a cool project as part of the class. The project will involve making a video (similar to the ones you see as part of the course). You will submit a link to the video which will be graded by your peers. We will post of list of topics from which you can chose from for the video or you can chose a topic of your interest as long as it has some co-relation with the course.

**Do I need to buy a textbook for the course?**

No, since the course covers contemporary topics and recent advances in the field of nanomanufacturing we won't be following any one book in particular. We will supplement the class videos with web links, articles and white papers, when needed. We have also supplemented the screencast videos with field trips, guest lectures and videos from other sources to give you a comprehensive picture of the topic.

**Do I need to know a lot about semiconductors or process technology or electronics industry to take this course?**

No, we have designed the course to be pretty broad such that minimal prior knowledge is required. An enthusiasm for electronics and gadgets is must though!

**What is the coolest thing I'll learn if I take this class?**

Among other things, You will know why a 16GB iPhone / iPad are more value for money as compared to a 32GB model. You will have a better understanding of the display, chips and other components that go inside your smartphone / tablet.

**How much time I am expected to spend on the course?**

3 – 4 hours per week.

**Instructor:**

Aneesh Nainani was born in Rajasthan, India. He received his B.Tech and M.Tech degrees in electrical engineering from the Indian Institute of Technology Bombay and Ph.D. degree in electrical engineering from Stanford University. He has worked with CEA-LETI, IBM, SEMATECH, and Applied Materials. He is currently a Senior Technologist with Applied Materials in Santa Clara, CA, and also holds an Assistant Professor (Consulting) appointment at Stanford University.

His research interests are in the physics, technology and economics of semiconductors and nanoscience. More recently he has been tinkering with digital education and content delivery. He is a firm believer in Minimally Invasive Education.

He has published more than 50 papers on nanocrystal flash memory, III-V CMOS, and thin-film solar cells. Aneesh was a recipient of several awards, including the Intel PhD Fellowship, the School of Engineering Fellowship from Stanford University, and the National Talent Scholarship from the Government of India.

Date:

Tuesday, June 17, 2014

Course topic:

How to Learn Math is a class for learners of all levels of mathematics. It combines really important information on the brain and learning with new evidence on the best ways to approach and learn math effectively. Many people have had negative experiences with math, and end up disliking math or failing. This class will give learners of math the information they need to become powerful math learners, it will correct any misconceptions they have about what math is, and it will teach them about their own potential to succeed and the strategies needed to approach math effectively. If you have had past negative experiences with math this will help change your relationship to one that is positive and powerful.

The course will feature Jo and a team of undergraduates, as well as videos of math in action - in dance, juggling, snowflakes, soccer and many other applications. It is designed with a pedagogy of active engagement.The course will run from May/June to the end of December, 2014.

**Part 1: The Brain and Math Learning**.

*Knocking Down the Myths About Math*.

Everyone can learn math well. There is no such thing as a “math person”. This session give stunning new evidence on brain growth, and consider what it means for math learners.*Math and Mindset*

When individuals change their mindset from fixed to growth their learning potential increases drastically. In this session participants will be encouraged to develop a growth mindset for math.*Mistakes and Speed*

Recent brain evidence shows the value of students working on challenging work and even making mistakes. But many students are afraid of mistakes and think it means they are not a math person. This session will encourage students to think positively about mistakes. It will also help debunk myths about math and speed.

**Part 2: Strategies for Success**.

*Number Flexibility, Mathematical Reasoning, and Connections*

In this session participants will engage in a “number talk” and see different solutions of number problems to understand and learn ways to act on numbers flexibility. Number sense is critical to all levels of math and lack of number sense is the reason that many students fail courses in algebra and beyond. Participants will also learn about the value of talking, reasoning, and making connections in math.*Number Patterns and Representations*

In this session participants will see that math is a subject that is made up of connected, big ideas. They will learn about the value of sense making, intuition, and mathematical drawing. A special section on fractions will help students learn the big ideas in fractions and the value of understanding big ideas in math more generally.*Math in Life, Nature and Work*

In this session participants will see math as something valuable, exciting, and present throughout life. They will see mathematical patterns in nature and in different sports, exploring in depth the mathematics in dance and juggling. This session will review the key ideas from the course and help participants take the important strategies and ideas they have learned into their future.

FAQ:

**Who is this course for?**

This course is designed for any learner of math and anyone who wants to improve their relationship with math. The ideas should be understandable by students of all levels of mathematics.

Parents who have children under age 13 and who think their children would benefit from some of the course materials should register themselves (i.e., parent's name, email, username) for the course. The parent may then choose to share course materials with their child at their own discretion.

**What is the course structure?**

The course will consist of six short lessons, taking approximately 20 minutes each. The lessons will combine presentations from Dr. Boaler and a team of undergraduates, interviews with members of the public, cutting edge research ideas, interesting visuals and films, and explorations of math in nature, sport and design.

**What is the pace of the course?**

The course will be self-paced, and you can start and end the course at any time in the months it is open. It is recommended that you take no more than one session a week, to allow the ideas to be processed and understood.

**How will I be assessed?**

There will be no formal assessment. Participants will be asked to complete a pre-and post-survey. The course will include quizzes that combine opportunities to write, work on math and reflect. These will not be graded.

**Does this course carry any kind of Stanford University credit?**

No.

Instructor(s):

Jo Boaler

Date:

Monday, June 16, 2014

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.

- 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, June 30, 2014 to Sunday, August 24, 2014

Course topic:

In this course you will learn several fundamental principles of advanced algorithm design. You'll learn the greedy algorithm design paradigm, with applications to computing good network backbones (i.e., spanning trees) and good codes for data compression. You'll learn the tricky yet widely applicable dynamic programming algorithm design paradigm, with applications to routing in the Internet and sequencing genome fragments. You’ll learn what NP-completeness and the famous “P vs. NP” problem mean for the algorithm designer. Finally, we’ll study several strategies for dealing with hard (i.e., NP-complete problems), including the design and analysis of heuristics. Learn how shortest-path algorithms from the 1950s (i.e., pre-ARPANET!) govern the way that your Internet traffic gets routed today; why efficient algorithms are fundamental to modern genomics; and how to make a million bucks in prize money by “just” solving a math problem!

How to program in at least one programming language (like C, Java, or Python); and familiarity with proofs, including proofs by induction and by contradiction. At Stanford, a version of this course is taken by sophomore, junior, and senior-level computer science majors. The course assumes familiarity with some of the topics from Algo 1 --- especially asymptotic analysis, basic data structures, and basic graph algorithms.

No specific textbook is required for the course. Much of the course material is covered by the well-known textbooks on algorithms, and the student is encouraged to consult their favorite for additional information.

The class will consist of lecture videos, generally between 10 and 15 minutes in length. These usually have integrated quiz questions. There will also be standalone homeworks and programming assignments that are not part of video lectures, and a final exam.

**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.**How does Algorithms: Design and Analysis differ from the Princeton University algorithms course?**The two courses are complementary. That one emphasizes implementation and testing; this one focuses on algorithm design paradigms and relevant mathematical models for analysis. In a typical computer science curriculum, a course like this one is taken by juniors and seniors, and a course like that one is taken by first- and second-year students.

Instructor(s):

Tim Roughgarden

Date:

Tuesday, April 1, 2014

Course topic:

Cryptography is an indispensable tool for protecting information in computer systems. This course explains the inner workings of cryptographic primitives and how to correctly use them. Students will learn how to reason about the security of cryptographic constructions and how to apply this knowledge to real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two or more parties generate a shared secret key. We will cover the relevant number theory and discuss public-key encryption and basic key-exchange. Throughout the course students will be exposed to many exciting open problems in the field.

The course will include written homeworks and programming labs. The course is self-contained, however it will be helpful to have a basic understanding of discrete probability theory.

**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 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. There will be approximately two hours worth of video content per week.

**How much programming background is needed for the course?**The course includes programming assignments and some programming background will be helpful. However, we will hand out lots of starter code that will help students complete the assignments. We will also point to online resources that can help students find the necessary background.

**What math background is needed for the course?**The course is mostly self contained, however some knowledge of discrete probability will be helpful. The wikibooks article on discrete probability should give sufficient background.

Instructor(s):

Dan Boneh

Date:

Tuesday, April 29, 2014 to Sunday, June 29, 2014

Course topic:

In this course you will learn several fundamental principles of algorithm design. You'll learn the divide-and-conquer design paradigm, with applications to fast sorting, searching, and multiplication. You'll learn several blazingly fast primitives for computing on graphs, such as how to compute connectivity information and shortest paths. Finally, we'll study how allowing the computer to "flip coins" can lead to elegant and practical algorithms and data structures. Learn the answers to questions such as: How do data structures like heaps, hash tables, bloom filters, and balanced search trees actually work, anyway? How come QuickSort runs so fast? What can graph algorithms tell us about the structure of the Web and social networks? Did my 3rd-grade teacher explain only a suboptimal algorithm for multiplying two numbers?

Week 1: Introduction. Asymptotic analysis including big-oh notation. Divide-and-conquer algorithms for sorting, counting inversions, matrix multiplication, and closest pair.

Week 2: Running time analysis of divide-and-conquer algorithms. The master method. Introduction to randomized algorithms, with a probability review. QuickSort.

Week 3: More on randomized algorithms and probability. Computing the median in linear time. A randomized algorithm for the minimum graph cut problem.

Week 4: Graph primitives. Depth- and breadth-first search. Connected components in undirected graphs. Topological sort in directed acyclic graphs. Strongly connected components in directed graphs.

Week 5: Dijkstra's shortest-path algorithm. Introduction to data structures. Heaps and applications.

Week 6: Further data structures. Hash tables and applications. Balanced binary search trees.

Week 2: Running time analysis of divide-and-conquer algorithms. The master method. Introduction to randomized algorithms, with a probability review. QuickSort.

Week 3: More on randomized algorithms and probability. Computing the median in linear time. A randomized algorithm for the minimum graph cut problem.

Week 4: Graph primitives. Depth- and breadth-first search. Connected components in undirected graphs. Topological sort in directed acyclic graphs. Strongly connected components in directed graphs.

Week 5: Dijkstra's shortest-path algorithm. Introduction to data structures. Heaps and applications.

Week 6: Further data structures. Hash tables and applications. Balanced binary search trees.

How to program in at least one programming language (like C, Java, or Python); and familiarity with proofs, including proofs by induction and by contradiction. At Stanford, a version of this course is taken by sophomore, junior, and senior-level computer science majors.

No specific textbook is required for the course. Much of the course material is covered by the well-known textbooks on algorithms, and the student is encouraged to consult their favorite for additional information.

The class will consist of lecture videos, generally between 10 and 15 minutes in length. These usually integrated quiz questions. There will also be standalone homeworks and programming assignments that are not part of video lectures, and a final exam.

**Will I get a statement of accomplishment after completing this class?****What is the format of the class?**The class consists 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. There will be approximately two hours worth of video content per week.

**What should I know to take this class?**How to program in at least one programming language (like C, Java, or Python); familiarity with proofs, including proofs by induction and by contradiction; and some discrete probability, like how to compute the probability that a poker hand is a full house. At Stanford, a version of this course is taken by sophomore, junior, and senior-level computer science majors.

**How does Algorithms: Design and Analysis differ from the Princeton University algorithms course?**The two courses are complementary. That one emphasizes implementation and testing; this one focuses on algorithm design paradigms and relevant mathematical models for analysis. In a typical computer science curriculum, a course like this one is taken by juniors and seniors, and a course like that one is taken by first- and second-year students.

Instructor(s):

Tim Roughgarden

Date:

Monday, March 31, 2014

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, March 17, 2014 to Monday, June 2, 2014

Course topic:

This course will discuss the major ideas used today in the implementation of programming language compilers, including lexical analysis, parsing, syntax-directed translation, abstract syntax trees, types and type checking, intermediate languages, dataflow analysis, program optimization, code generation, and runtime systems. As a result, you will learn how a program written in a high-level language designed for humans is systematically translated into a program written in low-level assembly more suited to machines. Along the way we will also touch on how programming languages are designed, programming language semantics, and why there are so many different kinds of programming languages.

The course lectures will be presented in short videos. To help you master the material, there will be in-lecture questions to answer, quizzes, and two exams: a midterm and a final. There will also be homework in the form of exercises that ask you to show a sequence of logical steps needed to derive a specific result, such as the sequence of steps a type checker would perform to type check a piece of code, or the sequence of steps a parser would perform to parse an input string. This checking technology is the result of ongoing research at Stanford into developing innovative tools for education, and we're excited to be the first course ever to make it available to students.

An optional course project is to write a complete compiler for COOL, the Classroom Object Oriented Language. COOL has the essential features of a realistic programming language, but is small and simple enough that it can be implemented in a few thousand lines of code. Students who choose to do the project can implement it in either C++ or Java.

I hope you enjoy the course!

Everything that computers do is the result of some program, and all of the millions of programs in the world are written in one of the many thousands of programming languages that have been developed over the last 60 years. Designing and implementing a programming language turns out to be difficult; some of the best minds in computer science have thought about the problems involved and contributed beautiful and deep results. Learning something about compilers will show you the interplay of theory and practice in computer science, especially how powerful general ideas combined with engineering insight can lead to practical solutions to very hard problems. Knowing how a compiler works will also make you a better programmer and increase your ability to learn new programming languages quickly.

Instructor(s):

Alex Aiken

Date:

Monday, March 3, 2014

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

Instructor(s):

Andrew Ng