Skip to content
Skip to navigation
# Engineering & Computer Science

##
Algorithms: Design and Analysis, Part 2

## About the Course

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## FAQ

##
Mining Massive Datasets

## About the Course

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## Instructors

##
Surveillance Law

## [[{"fid":"22191","view_mode":"default","fields":{"format":"default"},"type":"media","attributes":{"height":"390","width":"640","alt":"Welcome","class":"panopoly-image-video media-element file-default"}}]]

## About the Course

## Course Syllabus

## Suggested Readings

## Course Format

## Instructors

##
Machine Learning

## [[{"fid":"21601","view_mode":"default","fields":{"format":"default"},"type":"media","attributes":{"height":"390","width":"640","alt":"Machine Learning: About the class","class":"panopoly-image-video media-element file-default"}}]]

## About the Course

##
Archaeology and Ancient Engineering

## THIS COURSE IS OFFERED THROUGH STANFORD CONTINUING STUDIES.

## ABOUT THIS COURSE

## INSTRUCTOR

#### Patrick Hunt, Former Director, Stanford Alpine Archaeology Project; Research Associate in Archeoethnobotany, Institute for EthnoMedicine

##
Algorithms: Design and Analysis, Part 1

## About the Course

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## FAQ

##
Quantum Mechanics for Scientists and Engineers 2

##
Energy: Chemical Transformations for Production, Storage, and Use (CHEMENG25E) (SCPD)

## ABOUT THE COURSE

## Topics Include

## Instructors

##
Biochemical Engineering (CHEMENG150) (SCPD)

## About the Course

## Topics Include

## Instructors:

##
Game Theory II: Advanced Applications

## About the Course

## Course Syllabus

## Recommended Background

## Suggested Readings

## Course Format

## Pages

Topic Image:

Date:

Monday, March 23, 2015 to Saturday, May 16, 2015

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!

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.

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.- 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. While Part 2 is designed for students who have already taken Part 1, some students have successfully completed Part 2 without taking Part 1.

Instructor(s):

Tim Roughgarden

Date:

Saturday, January 31, 2015 to Tuesday, March 24, 2015

Course topic:

This course teaches algorithms for extracting models and other information from very large amounts of data, with an emphasis on techniques that are efficient and scale well.

We introduce course participants 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 athttp://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.

FAQ:

**Will I get a Statement of Accomplishment after completing this class?**

Yes. Course participants who successfully complete the class will receive a Statement of Accomplishment signed by the instructors. A level disignated "distinction" will also be offered.

Date:

Tuesday, January 20, 2015 to Monday, March 9, 2015

Course topic:

It’s easy to be cynical about government surveillance. In recent years, a parade of Orwellian disclosures have been making headlines. The FBI, for example, is hacking into computers that run anonymizing software. The NSA is vacuuming up domestic phone records. Even local police departments are getting in on the act, tracking cellphone location history and intercepting signals in realtime.

Perhaps 2014 is not quite 1984, though. This course explores how American law facilitates electronic surveillance—but also substantially constrains it. You will learn the legal procedures that police and intelligence agencies have at their disposal, as well as the security and privacy safeguards built into those procedures. The material also provides brief, not-too-geeky technical explanations of some common surveillance methods.

I. Introduction

We will begin with a brief overview of how surveillance fits into the American legal system. We will also discuss how surveillance issues can be litigated.

II. The Basics of Surveillance Law

Next, we will review established police surveillance procedures. Using telephone technology as a simple starting point, we will work through various sorts of data that investigators might seek to access—and the constitutional and statutory safeguards on that data.

III. Applying Surveillance Law to Information Technology

Having learned the basics, we will turn to more modern technologies. We will discuss snooping on email, web browsing, and mobile phone location, as well as hacking into devices.

IV. Compelled Assistance to Law Enforcement

What happens when data is technically protected? In this section, we will talk about the government’s (limited) ability to mandate backdoors and to require decryption.

V. The Structure of Foreign Intelligence Surveillance Law

The law that applies to foreign intelligence activities runs parallel to the law that applies to police activities. We will compare the two systems of law and review key distinctions. The section places particular emphasis on Section 215 of the USA PATRIOT Act,Section 702 of the FISA Amendments Act, and Executive Order 12333.

VI. Controversial NSA Programs

In the final section, we will review the conduct and legality of controversial National Security Agency programs. We will discuss in detail the domestic phone metadata program, PRISM, and “upstream” Internet monitoring.

There is no required textbook for the course. All readings will be provided online.

Several tomes discuss electronic surveillance in detail. For further reading, you might consider *Dragnet Nation* and *No Place to Hide*. If you'd like a more lawyerly take, we highly recommend the (free and public) Department of Justice manual on electronic evidence. A number of casebooks also touch on government surveillance, including*Computer Crime Law*, *Criminal Procedure: Investigation*, *Information Privacy Law*, and*Internet Law*.

Much of the best legal writing on electronic surveillance is posted to blogs. You might also take a look at The Volokh Conspiracy, Lawfare, and Just Security.

Keep in mind that this area of law is evolving rapidly. If you encounter an explanation that seems outdated, it probably is. When this material was last offered at Stanford, for example, the law changed multiple times during the course.

The class will consist primarily of lectures, each about 5-10 minutes long. There will be occasional assigned quizzes; they are intended to make sure you understand the material and should not be too tricky. You will also be expected to participate in forum discussions.

Jonathan Mayer,Stanford University

FAQ:

**Why are you offering this course?**

Understanding government surveillance requires a blend of arcane law and computer science; even senior policymakers routinely botch specifics. We want to provide a comprehensive, accurate, and accessible explanation of current practices. Our aim is to raise the level of discourse on government surveillance.**What background is expected for enrolling in this course?**

None! Just be willing to learn some law. And a little computer science.**Is the course technically robust against surveillance?**

It can be! If you’d prefer to follow along without creating an account, you can access the “preview” version of the course. For even greater protection, you can load the preview using the Tor anonymizing network.**Can I suggest material for the course?**

Absolutely, feedback is very welcome. Please reach out to @jonathanmayer.**What areas of law does this course cover?**

Most of the material draws on the Fourth Amendment to the United States Constitution, the Electronic Communications Privacy Act (ECPA), theCommunications Assistance for Law Enforcement Act (CALEA), and the Foreign Intelligence Surveillance Act (FISA). We will also briefly discuss the Federal Rules of Criminal Procedure and the Fifth Amendment.**Does the course advocate for or against government surveillance?**

Neither. Course staff have worked with law enforcement agencies and civil liberties groups. Our aim is to present the law as it stands, with the best articulation of competing views. We expect there will be vibrant accompanying discussion.**Why is the best (i.e. the NSA) saved for last?**

The course begins with police surveillance for several reasons. First, the surrounding law is much better developed—it’s much older, much more transparent, and much more frequently litigated. Second, foreign intelligence law builds upon the framework of police surveillance law; understanding the latter is essential to understanding the former.**Is Continuing Legal Education (CLE) credit available to attorneys?**

We're working on it, stay tuned!**Will the course include discussion of current events?**

Definitely. Surveillance practices frequently make headlines; we will share our thoughts throughout the course.**What if the law changes during the course?**

We will post an update. There is a good chance that it will happen.**Can I repurpose the course materials?**

Absolutely. The entire course is offered under a Creative Commons Attribution 4.0 International License.**Does the course remix work by others?**

Yes. We have compiled a table of remixed content, with sources and licenses.**Can you help me with a legal problem?**

Course staff are not acting as your lawyers and do not provide legal advice. If you need legal assistance, you should retain an attorney.

Date:

Monday, January 19, 2015 to Sunday, April 19, 2015

Course topic:

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

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

FAQ:

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

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

**How much programming background is needed for the course?**

The course includes programming assignments and some programming background will be helpful.

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

No, it is self-contained.

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

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

Instructor(s):

Andrew Ng

Date:

Monday, January 12, 2015 to Friday, February 20, 2015

Course topic:

Many of the world’s most famous, monumental, and staggering engineering projects or inventions are in fact ancient, some even prehistoric. Stonehenge and related megaliths date back thousands of years. Found off Greece in a shipwreck, the enigmatic Antikythera bronze is an astonishing invention dating before the Roman empire. Even if Hero of Alexandria’s 1st century ce steam engines were only theoretical, they deserve mention alongside his pneumatics and mechanics innovations. Some of the most remarkable achievements in antiquity include Roman roads and bridges, and the advent of concrete and hydrological technology such as aqueducts. Add to this the qanat canals and irrigation system of Persia, the pyramids of Egypt, the stone cities and road networks of the Incas and their ancestors in South America, and the urban and sculptural stoneworking of the Aztecs in Central America. All of these feats of engineering, occurring long before the Industrial Revolution, will be the subject of this course.

*Thanks to the flexibility of the online format, this course can be taken anywhere, anytime—a plus for students who lead busy lives or for whom regular travel to the Stanford campus is not possible. While necessarily structured differently from an on-campus classroom course, this course maintains a similar level of instructor engagement through videos, interactive exercises, and discussion with fellow students, as well as optional online video conferencing sessions.*

**Tuition Applies.**

Patrick Hunt has taught at Stanford since 1993 and is also an associate at the UCLA Center for Medieval and Renaissance Studies. He is the author of fourteen books, including *Ten Discoveries That Rewrote History, Myth and Art in Ekphrasis*, and *Critical Insights: The Inferno*. Hunt was the director of the National Geographic Society Hannibal Expedition. He received a PhD from the Institute of Archaeology, UCL. - See more at: http://continuingstudies.stanford.edu/courses/detail/20142_ARC-122-W#sth...

Date:

Monday, January 19, 2015 to Saturday, March 14, 2015

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.

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

Instructor(s):

Tim Roughgarden

Date:

Tuesday, January 13, 2015 to Wednesday, March 18, 2015

Course topic:

**ABOUT THIS COURSE**

This course covers key topics in the use of quantum mechanics in many modern applications in science and technology, introduces core advanced concepts such as spin, identical particles, the quantum mechanics of light, the basics of quantum information, and the interpretation of quantum mechanics, and covers the major ways in which quantum mechanics is written and used in modern practice. It follows on directly from the QMSE-01 "Quantum Mechanics for Scientists and Engineers" course, and is also accessible to others who have studied some quantum mechanics at the equivalent of a first junior or senior college-level physics quantum mechanics course. All of the material for the QMSE-01 course is also provided as a resource. The course should prepare the student well to understand quantum mechanics as it is used in a wide range of current applications and areas and provide a solid grounding for deeper studies of specific more advanced areas.

**COURSE SYLLABUS**

**Quantum mechanics in crystals**

Crystal structures, the Bloch theorem that simplifies quantum mechanics in crystals, and other useful concepts for understanding semiconductor devices, such as density of states, effective mass, quantum confinement in nanostructures, and important example problems like optical absorption in semiconductors, a key process behind all optoelectronics.

**Methods for one-dimensional problems**

How to understand and calculate tunneling current. The transfer matrix technique, a very simple and effective technique for calculating quantum mechanical waves and states.

**Spin and identical particles**

The purely quantum mechanical idea of spin, and how to represent and visualize it. The general ideas of identical particles in quantum mechanics, including fermions and bosons, their properties and the states of multiple identical particles.

**Quantum mechanics of light**

Representing light quantum mechanically, including the concept of photons, and introducing the ideas of annihilation and creation operators.

**Interaction of different kinds of particles**

Describing interactions and processes using annihilation and creation operators for fermions and bosons, including the important examples of stimulated and spontaneous emission that correctly explain all light emitters, from lasers to light bulbs.

**Mixed states and the density matrix**

Introducing the idea of mixed states to describe how quantum mechanical systems interact with the rest of the complex world around us, and the notation and use of the density matrix to describe and manipulate these.

**Quantum measurement and quantum information**

Introducing the no-cloning theorem, quantum cryptography, quantum entanglement and the basic ideas of quantum computing and teleportation, and returning to the idea of measurement in quantum mechanics, including the surprising results of Bell’s inequalities.

**Interpretation of quantum mechanics**

A brief introduction to some of the different approaches to the difficult problem of understanding what quantum mechanics really means!

**PREREQUISITES**

The course is designed to build on a first course on quantum mechanics at the junior or senior college level, so students should have at least that background. The material here is specifically matched to follow on from the Stanford Online QMSE-01 "Quantum Mechanics for Scientists and Engineers" class, and all the material from that class is provided as background in the online course materials here. No additional background beyond that class is presumed here.

FAQ:

**Do I need to buy a textbook?**

You do not need to buy a textbook; the course is self-contained. My book “Quantum Mechanics for Scientists and Engineers” (Cambridge, 2008) is an optional additional resource for the course. 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.

**How much of a time commitment will this course be?**

You should expect this course to require 7 – 10 hours of work per week.

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

No.

**Will I get a Statement of Accomplishment?**

Yes, students who score at least 70% will pass the course and receive a Statement of Accomplishment. Students who score at least 90% will receive a Statement of Accomplishment with distinction.

We recommend taking this course on a standard computer using Google Chrome as your internet browser. We are not yet optimized for mobile devices.

**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 Laboratories 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, holds over 70 US Patents, is a Fellow of many major professional societies in science and engineering, including IEEE, APS, OSA, the Royal Society of London, and the Royal Society of Edinburgh, 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.

Date:

Monday, January 6, 2014 to Thursday, March 19, 2015

Course topic:

Chemical transformations research provides an opportune platform for discovering the entrepreneurial opportunities and challenges of energy supply and consumption. Through exposure to unbiased inquiry of energy production alternatives you will have the tools needed to move forward and examine the composite of future large energy production systems. This course contributes to the online Molecular Engineering of Energy Technologies Graduate Certificate. Enrollment is open for winter quarter.* (Fee Applies)*

- Solar thermal systems
- Biofuels
- Photovoltaics
- Electrochemical devices (batteries and fuel cells)
- Energy production technologies

- Thomas Jaramillo
*Assistant Professor, Chemical Engineering*

Date:

Monday, January 5, 2015 to Friday, March 20, 2015

Course topic:

Combine essential chemical engineering concepts and biological principles to address the needs of the biotech industry. Investigate recombinant DNA technology, synthetic biology and metabolic engineering. Develop processes and effective solutions to navigate regulatory policies and the manufacturing of products. This course contributes to the online Biotechnology Graduate Certificate. Enrollment is open for winter quarter. (*Fee Applies)*

- Elemental stoichiometry of metabolism
- Fermentation development and control
- Product isolation and purification
- Protein folding and formulation

- Lisa Hwang
*Lecturer*,*Chemical Engineering* - James Swartz
*Professor*,*Chemical Engineering and Bioengineering*

Date:

Friday, January 8, 2016 to Saturday, February 20, 2016

Course topic:

This advanced course considers how to design interactions between agents in order to achieve good social outcomes. Three main topics are covered: social choice theory (i.e., collective decision making), mechanism design, and auctions.

Popularized by movies such as "A Beautiful Mind", game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Over four weeks of lectures, this advanced course considers how to design interactions between agents in order to achieve good social outcomes. Three main topics are covered: social choice theory (i.e., collective decision making), mechanism design, and auctions.

In the first week we consider the problem of aggregating different agents' preferences, discussing voting rules and the challenges faced in collective decision making. We present some of the most important theoretical results in the area: notably, Arrow's Theorem, which proves that there is no "perfect" voting system, and also the Gibbard-Satterthwaite and Muller-Satterthwaite Theorems. We move on to consider the problem of making collective decisions when agents are self interested and can strategically misreport their preferences. We explain "mechanism design" -- a broad framework for designing interactions between self-interested agents -- and give some key theoretical results. Our third week focuses on the problem of designing mechanisms to maximize aggregate happiness across agents, and presents the powerful family of Vickrey-Clarke-Groves mechanisms. The course wraps up with a fourth week that considers the problem of allocating scarce resources among self-interested agents, and that provides an introduction to auction theory.

There will be four weeks of materials consisting of online videos and problem sets. We recommend that you complete the problem set for each week within that week, although the hard deadline is two weeks from the release date. On the fifth week, we will have a final exam.

Week 1. Social Choice

Week 2. Mechanism Design

Week 3. Efficient Mechanisms

Week 4. Auctions

Week 5-6. Final exam and final problem set.

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:

Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, by Yoav Shoham and Kevin Leyton-Brown; Cambridge University Press, 2009. This book has the same structure as the course, and covers most of the same material. It is available as a free PDF download from the link above or for sale as a physical book from (e.g.) amazon.com.

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.

· **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.** We will hold occasional online chats where we answer questions and discuss topics relevant to the course.

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 signed by the instructors.

Instructor(s):

Kevin Leyton-Brown