Skip to content Skip to navigation

Engineering & Computer Science

Topic Image: 
Engineering and Computer Science
Date: 
Wednesday, March 25, 2015
Go to Course
Fee and Application.
This course is offered through the Stanford School of Professional Education as part of the Stanford Advanced Computer Security Certificate.

Applications may be submitted online at anytime. Sample Application

Overview

This course covers 3 specific topic areas:

Computer Security Principles covers security objectives such as authentication, authorization, access control, confidentiality, data integrity, and non-repudiation. The module also covers software design principles including the principles of least privilege, fail-safe stance, and defense-in-depth.

Introduction to Cryptography covers both symmetric encryption and public-key cryptography, discussing how they are used to achieve security goals and build PKI (Public-Key Infrastructure) systems. The module also covers DES, 3DES, AES, RC4, RSA, ECC, MD5, SHA-1, X.509, digital signatures, and all cryptographic primitives necessary to understand PKI. Diffie-Hellman key exchange and man-in-the-middle attacks will also be discussed.

Secure Programming Techniques discusses the threats that worms and hackers present to software and the programming techniques that developers can use to defend against software vulnerabilities such as buffer overflows, SQL injection, and off-line dictionary attacks. The module also covers common mistakes made in using cryptographic libraries and how they can be avoided.

Instructors

Topics Include

  • Computer Security Principles
  • Introduction to Cryptography
  • Secure Programming Techniques

Recommended

We recommend you have the equivalent of a BS in Computer Science and a background in security.

We highly recommend that you take this course, Software Security Foundations (XACS101) as the 1st course within the Stanford ACS certificate program. It provides the fundamentals necessary for the subsequent courses in the program.

Tuition

  • $595 for Software Security Foundations
  • $75 one-time document fee
Security Course Feature Image SCPD

View All Courses

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

Date: 
Monday, April 20, 2015 to Sunday, May 31, 2015
Go to Course

About the Course

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.

A preview of the course, including lectures and homework assignments, is available at this preview site.

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

  • Can I see a preview of the lectures and homework?

    Yes, check out this preview site.

Instructor(s): 
Dan Boneh
Cryptography 1 image

View All Courses

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

Go to Course

About This Course

This is a self-paced introductory course on computer networking, specifically the Internet. It focuses on explaining how the Internet works, ranging from how bits are modulated on wires and in wireless to application-level protocols like BitTorrent and HTTP. It also explains the principles of how to design networks and network protocols. Participants gain experience reading and understanding RFCs (Internet protocol specifications) as statements of what a system should do. The course grounds many of the concepts in current practice and recent developments, such as net neutrality and DNS security. A textbook is recommended, but not required: you can use either Peterson and Davie or Kurose and Ross, any version in the past 5 years will do.

Prerequisites

Students need an introductory course in probability, a strong understanding of bits and bytes, and knowledge of how computers lay out data in memory.

Course Staff

Professor Philip Levis

Philip Levis is an Associate Professor of Computer Science and Electrical Engineering at Stanford University. He received his Sc.B. from Brown University in 1999, his M.S. from the University of Colorado at Boulder in 2001, and his Ph.D. from UC Berkeley in 2005. In 2008 he received an NSF CAREER award and a Microsoft Research New Faculty Fellowship. He researches the design and implementation of networked systems, including operating systems and protocols for embedded wireless devices, wireless mesh protocols, network infrastructure for virtual worlds, and energy efficient computing. The results of his research, including the TinyOS operating system, nesC language, Trickle algorithm, and the collection tree protocol (CTP), have been adopted by tens of thousands of users and researchers worldwide. He is a co-founder and the President of Kumu Networks. He really likes excellent engineering and has a self-destructive aversion to low-hanging fruit.

Professor Nick McKeown

Nick McKeown has been a Professor of Electrical Engineering and Computer Science at Stanford University since 1995. He grew up in the UK and received his BEng from Leeds University in 1986. He moved to the US in 1989 to do an MS and PhD in Electrical Engineering and Computer Science at University of California at Berkeley. His research group works on new Internet architectures, software-defined networks and how to make routers faster. He co-founded several companies based on technology started at Stanford. He is a member of the National Academy of Engineering and recently received the ACM Sigcomm "Lifetime Achievement" Award.

Introduction to Computer Networking

View All Courses

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

Date: 
Monday, April 18, 2016
Go to Course

Accepting Applications 

November 25, 2015 – April 11, 2016 

Course Starts Online: 

April 18, 2016 

Come to Stanford: 

May 31-June 3, 2016 

Fee and Application. 

This course is offered through Worldview Stanford. Worldview Stanford is an innovative Stanford University initiative that creates interdisciplinary learning experiences for professionals to prepare them for the strategic challenges ahead. 

COURSE DESCRIPTION 

What's driving big data? We increasingly live our social, economic, and intellectual lives in the digital realm, enabled by new tools and technologies. These activities generate massive data sets, which in turn refine the tools. How will this co-evolution of technology and data reshape society more broadly? 

Creating new knowledge and value: Big data changes what can be known about the world, transforming science, industries, and culture. It reveals solutions to social problems and allows products and services to be even more targeted. Where will big data create the greatest sources of new understanding and value? 

Shifting power, security, and privacy: The promise of big data is accompanied by perils—in terms of control, privacy, security, reputation, and social and economic disruption. How will we manage these tradeoffs individually and in business, government, and civil society? 

FEATURED EXPERTS 

Learn from a variety of sources and Stanford experts, including: 

Lucy Bernholz, philanthropy, technology, and policy scholar at the Center on Philanthropy and Civil Society 

Sharad Goel, computational scientist studying politics, media, and social networks 

Margaret Levi, political scientist specializing in governance, trust, and legitimacy 

Jennifer Granick, attorney and director of Civil Liberties at the Stanford Center for Internet and Society 

Michal Kosinski, psychologist and computational scientist studying online and organizational behavior at Stanford Graduate School of Business 

Margaret Levi, political scientist specializing in governance, trust, and legitimacy 

John Mitchell, computer scientist, cybersecurity expert, and Vice Provost of Teaching and Learning

Big Data

View All Courses

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

Date: 
Monday, February 23, 2015
Go to Course
This course is offered as part of the Energy Engineering and Technologies Certificate through the Stanford Center for Professional Development.

Overview

This seminar is an interdisciplinary exploration of current energy challenges and opportunities. Talks will be conducted by faculty, visitors, and students.

Upcoming guest speakers listing and an archive of past seminars can be found here: http://energyseminar.stanford.edu

Autumn Speakers:

  • Dian Grueneich, Senior Research Scholar, Stanford University
  • Robert Jackson, Professor, Environmental Earth System Science, Stanford University
  • Bob Litterman, Chairman of the Risk Committee and a Founding Partner, Kepos Capital LP
  • Michael Sivak, Research Professor, University of Michigan Transportation Research Institute
  • Stefan Heck, Consulting Professor, Precourt Institute for Energy
  • Tom Degnan, Manager, Breakthrough Technology, ExxonMobil Research and Engineering Company

Instructors

Seminars

Individuals who wish to view the seminar at no charge are asked to create a mystanfordconnection account. Once you have created an account, you will be able to access videos via mystanfordconnection. Make sure you have Silverlight 1.0 or Windows Media Player 9+ installed to view videos. Seminars are available two hours after the lecture occurs on campus and on-demand for the remainder of the quarter. All seminars can be found in the "Current Courses" section ofmystanfordconnection.

Tuition & Fees

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

Certificates and Degrees

Energy SCPD course image

View All Courses

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

Date: 
Monday, March 30, 2015
Go to Course
This course contributes to the Biotechnology Graduate Certificate through the Stanford Center for Professional Development. Application and fee may apply.

Overview

Gain a fundamental understanding of genetic engineering principles and how they can be applied towards new challenges in the biotechnology industry. Optimize chemical transformations within the cell to produce valuable substances such as biofuels, vaccines, and consumer products. Examine the governmental regulations and ethics surrounding hot topic issues such as cloning, stem cells and genome sequencing.

Instructors

Topics Include

  • Cell culture
  • Protein production
  • Polymerase chain reactions
  • Viruses and gene therapy
  • Pharmaceutical development

Prerequisites

Chemical Principles (Stanford Course:CHEM31) and Calculus (Stanford Course:MATH41) or equivalents

Tuition & Fees

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

Certificates and Degrees

Bio Course Image SCPD

View All Courses

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

Date: 
Monday, March 30, 2015 to Saturday, May 23, 2015
Go to Course

About the Course

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.

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.

Recommended Background

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.
General Game Playing Course IMage

View All Courses

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

Date: 
Wednesday, March 4, 2015
Go to Course

[[{"fid":"25891","view_mode":"default","fields":{"format":"default"},"type":"media","attributes":{"height":"390","width":"640","alt":"Language Proof and Logic Promotional Video H264 020515 March 2015","class":"panopoly-image-video media-element file-default"}}]]

Materials fee

You may access the course lectures for free. However, in order to complete the course and earn a Statement of Accomplishment you must purchase the Language, Proof and Logic courseware package (including the Grade Grinder assessment service). The package contains software applications that you will use to complete exercises during the course. You will also get access to the Grade Grinder, an Internet-based assessment service for these exercises.

You can obtain the courseware package from the Language, Proof and Logic online store for $55 US. You may purchase the courseware package from other online retail sites and their prices may vary. Make sure the courseware package you purchase is new (not used) and includes the software as a CD. The courseware package is required to complete the course.

About This Course

The ability to reason is fundamental to human beings. Whatever the discipline or discourse it is important to be able to distinguish correct reasoning from incorrect reasoning. The consequences of incorrect reasoning can be minor, like getting lost on the way to a birthday party, or more significant, for example launching nuclear missiles at a flock of ducks, or permanently losing contact with a space craft.

The fundamental question that we will address in this course is "when does one statement necessarily follow from another" --- or in the terminology of the course, "when is one statement a logical consequence of another". This is an issue of some importance, since an answer to the question would allow us to examine an argument presented in a blog, for example, and to decide whether it really demonstrates the truth of the conclusion of the argument. Our own reasoning might also improve, since we would also be able to analyze our own arguments to see whether they really do demonstrate their conclusions.

In this course you will be introduced to the concepts and techniques used in logic. We will start right from the beginning, assuming no prior exposure to this or similar material, and progress through discussions of the proof and model theories of propositional and first-order logic.

We will proceed by giving a theory of truth, and of logical consequence, based on a formal language called FOL (the language of First-Order Logic). We adopt a formal language for making statements, since natural languages (like English, for example) are far too vague and ambiguous for us to analyze sufficiently. Armed with the formal language, we will be able to model the notions of truth, proof and consequence, among others.

While logic is technical in nature, the key concepts in the course will be developed by considering natural English statements, and we will focus the relationships between such statements and their FOL counterparts. The goal of the course is to show how natural English statements and arguments can be formalized and analyzed.

Prerequisites

This course has no prerequisites except an interest in the way in which we use language to construct arguments and justify conclusions. If that interests you, then you're all set! Go sign up.

Textbook

In order to complete the course and earn a Statement of Accomplishment you must purchase the Language, Proof and Logic courseware package (including the Grade Grinder assessment service). The package contains software applications that you will use to complete exercises during the course. You will also get access to the Grade Grinder, an Internet-based assessment service for these exercises.

You can obtain it from the Language, Proof and Logic online store for $55US. You may purchase the courseware package from other online retail sites and their prices may vary. Make sure the courseware package you purchase is new (not used) and includes the software as a CD. The courseware package is required to complete the course.

Frequently Asked Questions

Who should take this course?

This course is for you if you are interested in how to use language to construct and analyze arguments. The course has no prerequisites.

How is the course structured?

In addition to watching highly entertaining video lectures, you will complete assignments approximately weekly, using software applications and an automated TA who will give you feedback on your progress whenever you want it.

How will I be assessed?

Assessment is based on a combination of weekly assignments, and midterm and final exams. Most assignments are graded automatically, while some exercises will be assessed by your peers.

Will I receive a Statement of Accomplishment?

Yes. You can earn a Statement of Accomplishment if you score at least 75% on the graded assignments.

Do I need to buy a textbook?

If you do not wish to earn the Statement of Accomplishment, you do not need to purchase the textbook or courseware package. However, in order to complete the course and earn a Statement of Accomplishment you must purchase the Language, Proof and Logic courseware package (including the Grade Grinder assessment service). The package contains software applications that you will use to complete exercises during the course. You will also get access to the Grade Grinder, an Internet-based assessment service for these exercises.

You can obtain it from the Language, Proof and Logic online store for $55US. You may purchase the courseware package from other online retail sites and their prices may vary. Make sure the courseware package you purchase is new (not used) and includes the software as a CD. The courseware package is required to complete the course.

Can I get Stanford University credit for this class?

No.

Course Staff

Your Instructors

Dave Barker-Plummer
Senior Research Scientist

I'm Dave Barker-Plummer. Since 1995 I have managed the Openproof project's work on educational software for teaching logic at Stanford University. I have a background in Artificial Intelligence, and have taught computer science and logic at Stanford, Swarthmore College and Duke University. In my spare time I indulge my rock-star fantasies with PAN!C, a San Franciso based reggae/pop/jazz band.

John Etchemendy
Professor of Philosophy and Symbolic Systems

John Etchemendy has been on the faculty of Princeton University and Stanford University where he was chairman of the Department of Philosophy and is currently Provost. He has has also served as the director of the Center for the Study of Language and Information.

Course Material Developers

JT Chipman

I'm a third year doctoral student in Stanford's Department of Philosophy, with my research focusing on mathematical logic, philosophy of logic, and the history of analytic philosophy. I also like to think about logic pedagogy and, accordingly, am very excited to be a part of the Openproof team at CSLI. I spend my free time reading literature, watching movies, listening to music, and (with less frequency than I'd like) travelling.

Su Su

I received my B.A. in Cognitive Psychology from Stanford University in June 2013. Currently I am a graduate student in the Instructional Technology & Media program at Teachers College, Columbia University. Taking logic courses was the best part of my undergraduate memories at Stanford. My interests include logic and reasoning in education; using technology to spread logic around is the coolest thing I could ever think of!

Evan Liu

Evan Liu is a second-year undergraduate at Stanford University studying mathematics and computer science. The wide range of applications of logic - from writing analysis proofs to deciphering Kant to conversing with a friend - really excites me. My perspective of the world has entirely changed since studying logic. Besides logic, I like to spend my time playing tennis, studying chess, and baking.

For Language, Proof and Logic

Michael Murray

Michael Murray is the lead software developer for the Openproof project, producers of the Language, Proof and Logic courseware package.

Emma Pease

Emma Pease is in charge of operations and systems administration for the Openproof project, producers of the Language, Proof and Logic courseware package.

For Stanford Online

  • Marc Sanders, Kimberly Hayworth and Amy Collier from the office of the Vice Provost for Online Learning, helped with advice on running the course, particularly in the initial planning stages.
  • Brent Itzusu, Wes Choy and Neil Rogers produced the videos, and Greg Maximov worked on the production of their transcripts.  We recorded all of the videos in order, and then realised that the first dozen or so were awful, so we did those again.  Bet you can spot the join...
  • Jane Manning leads the OpenEdX platform team.  She, together with Greg Bruhns and Monica Diaz fielded so many questions from us about the platform with good grace and humor when I am sure they just wanted to tell us to read the manual.  Jason Bau conspired with Mike Murray to allow for the results from the Grade Grinder to magically appear on the OpenEdX platform (most of the time).

Our Research Community

Stanford University pursues the science of learning. Online learners are important participants in that pursuit. The information we gather from your engagement with our instructional offerings makes it possible for faculty, researchers, designers and engineers to continuously improve their work and, in that process, build learning science.

By registering as an online learner, you are also participating in research...
Read Terms of Service and Privacy Policy


View All Courses

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

Date: 
Tuesday, March 31, 2015
Go to Course

[[{"fid":"24921","view_mode":"default","fields":{"format":"default"},"type":"media","attributes":{"height":"390","width":"640","alt":"Zoback ResGeo Promo V3","class":"panopoly-image-video media-element file-default"}}]]

ABOUT THIS COURSE

This interdisciplinary course encompasses the fields of rock mechanics, structural geology, earthquake seismology and petroleum engineering to address a wide range of geomechanical problems that arise during the exploitation of oil and gas reservoirs.

The course considers key practical issues such as prediction of pore pressure, estimation of hydrocarbon column heights and fault seal potential, determination of optimally stable well trajectories, casing set points and mud weights, changes in reservoir performance during depletion, and production-induced faulting and subsidence. The first part of the course establishes the basic principles involved in a way that allows readers from different disciplinary backgrounds to understand the key concepts.

The course is intended for geoscientists and engineers in the petroleum and geothermal industries, and for research scientists interested in stress measurements and their application to problems of faulting and fluid flow in the crust.

RECOMMENDED BACKGROUND:

Introductory Geology and Geophysics
Familiarity with principles of drilling and petroleum production

COURSE FORMAT:

  • 20, 90 minute lectures (in ~20 minute segments). 2 lectures will be made available each week, starting April 1, 2014.
  • Lecture 1 is a course overview to introduce students to the topics covered in the course. Lectures 2-17 follow 12 chapters of Dr. Zoback’s textbook, Reservoir Geomechanics (Cambridge University Press, 2007) with updated examples and applications. Lectures 18 and 19 are on topics related to geomechanical issues affecting shale gas and tight oil recovery. Lecture 20 is on the topic of managing the risk of triggered and induced seismicity.
  • 8 Homework assignments (and associated video modules) are intended to give students hands-on experience with a number of the topics addressed in the course.
  • The course grade will be based solely on homework assignments. There will be no quizzes or exams.
  • Homework assignments will be graded electronically and will consist of multiple choice and numerical entry responses.
  • There will be an online discussion forum where students can discuss the content of the course and ask questions of each other and the instructors.

COURSE STAFF

Dr. Mark D. Zoback

Dr. Mark D. Zoback is the Benjamin M. Page Professor of Geophysics at Stanford University. Dr. Zoback conducts research on in situ stress, fault mechanics, and reservoir geomechanics with an emphasis on shale gas, tight gas and tight oil production. He was one of the principal investigators of the SAFOD project in which a scientific research well was successfully drilled through the San Andreas Fault at seismogenic depth. He is the author of a textbook entitled Reservoir Geomechanics published in 2007 by Cambridge University Press. He is the author/co-author of over 300 technical papers and holds five patents. He was the co-founder of GeoMechanics International in 1996, where he was Chairman of the Board until 2008. Dr. Zoback currently serves as a Senior Executive Adviser to Baker Hughes. Dr. Zoback has received a number of awards and honors, including the 2006 Emil Wiechert Medal of the German Geophysical Society and the 2008 Walter H. Bucher Medal of the American Geophysical Union. In 2011, he was elected to the U.S. National Academy of Engineering and in 2012 elected to Honorary Membership in the Society of Exploration Geophysicists. He is the 2013 recipient of the Louis Néel Medal, European Geosciences Union and named an Einstein Chair Professor of the Chinese Academy of Sciences. He recently served on the National Academy of Engineering committee investigating the Deepwater Horizon accident and the Secretary of Energy’s committee on shale gas development and environmental protection. He currently serves on a Canadian Council of Academies panel investigating the same topic. Dr. Zoback is currently serving on the National Academy of Sciences Advisory Board on drilling in the Gulf of Mexico.

Arjun H. Kohli, Graduate Teaching Assistant

Arjun H. Kohli is a 4th year Ph.D. candidate in the Department of Geophysics at Stanford and laboratory manager of the Stress and Crustal Mechanics Laboratory. Arjun conducts research on fault mechanics and microstructure with applications to plate-boundary fault zones, geothermal and petroleum reservoirs, and induced and triggered seismicity. He completed a B.S. in Geology-Physics/Mathematics at Brown University in 2010 and was awarded the Brown University Department of Geological Sciences Undergraduate Research Award for his work on dynamic fault weakening mechanisms. In 2011, he received a National Science Foundation Graduate Research Fellowship to investigate controls on the transition from stable to dynamic fault slip with Dr. Zoback at Stanford. Arjun is currently engaged in collaborative research with numerous partners including the United States Geological Survey, University of Silesia, University of Minnesota, and Stanford University Department of Geological and Environmental Sciences.

FREQUENTLY ASKED QUESTIONS

Will I receive a Statement of Accomplishment

Yes. A Statement of Accomplishment will be given to students who obtain more than 70% of the maximum score on the homework assignments.

Do I need to purchase a textbook for the course?

While it is not required to purchase the Reservoir Geomechanics textbook for this course, it is recommended. Lectures 2-17 follow the 12 chapters of the book. The book provides significant additional detail and explanation of the course concepts. It is available through:
Cambridge University Press:
http://www.cambridge.org/us/academic/subjects/earth-and-environmental-science/applied-geoscience-petroleum-and-mining-geoscience/reservoir-geomechanics
Amazon and Kindle:
http://www.amazon.com/Reservoir-Geomechanics-Mark-D-Zoback/dp/0521146194

Res Geomechanics Course Image

View All Courses

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

Date: 
Monday, March 23, 2015 to Saturday, May 16, 2015
Go to Course

About the Course

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!

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

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.

Suggested Readings

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.

Course Format

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.

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 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
Algorithms: Design and Analysis, Part I  Course Image

View All Courses

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

Pages

Subscribe to RSS - Engineering & Computer Science