Design and Analysis of Algorithms

View Course Materials

Buying via our links supports this free directory · Affiliate disclosure.
Course facts
  • Payment: Free, no certificate
  • Credits: Non Credit
  • Learning style: Self-paced, start anytime
  • Resources: Exam Solutions; Exams; Instructor Insights; Lecture Notes; Lecture Videos; Problem Set Solutions; Problem Sets; Problem-solving Videos
MIT OpenCourseWare details
  • As taught in: Spring 2015
  • Department: Electrical Engineering and Computer Science, Mathematics
Created byMIT
Available onMIT OpenCourseWareMIT OpenCourseWare

Course Details
Learning Style

Start Anytime

Level

All Levels

Study Mode

100% Online

Outcomes
Academic Credits

Non Credit

Price & Terms
Pricing Model

Free Content (No Certificate)

Technical
Content Medium

Video Based

Specification
Access

Free Access

Academic Level

Undergraduate

SKU: design-analysis-algorithms Category: Brand:

Intermediate algorithms: divide and conquer, randomization, dynamic programming, greedy, network flow, NP-completeness, approximation and cryptography.

At a glance
LevelAll Levels
AccessFree access
FormatVideo Based
As taught inSpring 2015
DepartmentElectrical Engineering and Computer Science, Mathematics
Add your review
Add to wishlistAdded to wishlistRemoved from wishlist 0
Add to compare

Designing an efficient algorithm takes a toolkit of techniques and the means to prove how well they perform. This intermediate algorithms course teaches both, emphasizing how to apply them, in recorded lectures with notes and recitation videos: divide and conquer, amortization, randomization, dynamic programming, greedy algorithms, network flow and matching, linear programming, complexity and approximation, distributed algorithms, cryptography and cache-oblivious algorithms.

What You Will Achieve

  • Design algorithms with divide and conquer, dynamic programming, greedy and randomized techniques
  • Analyze running times, including amortized and expected costs
  • Model problems as network flow, matching or linear programs
  • Prove problems NP-complete and design approximation and fixed-parameter algorithms


Program Overview

Core Design Techniques

The main strategies for building efficient algorithms.

  • Divide and conquer: convex hull, median finding, FFT and van Emde Boas trees
  • Amortized analysis and union-find
  • Randomization: quicksort, skip lists and universal and perfect hashing
  • Dynamic programming, all-pairs shortest paths and greedy minimum spanning trees

Flows, Optimization and Complexity

Network flow, linear programming and hard problems.

  • Max flow, min cut and matching
  • Linear programming, reductions and the simplex method
  • P, NP, NP-completeness and reductions
  • Approximation and fixed-parameter algorithms

Advanced Topics

Algorithms for distributed systems, security and memory.

  • Synchronous and asynchronous distributed algorithms
  • Cryptography: hash functions, encryption and other primitives
  • Cache-oblivious algorithms for medians, matrices, searching and sorting

Course Completion


Job Outlook

Algorithm design is used in software engineering, competitive programming, systems and infrastructure, operations research and theoretical computer science research.


Before you start: This course is the header course for the Theory of Computation concentration. You are expected, and strongly encouraged, to have taken: 6.006 Introduction to Algorithms; 6.042J / 18.062J Mathematics for Computer Science; Petitions for waivers will be considered by the course staff. Students will be responsible for material covered in prerequisites.

Our take

Good for: Learners who want a wide toolkit of algorithm design techniques, with the proofs and analysis behind each one.

Keep in mind: The problem sets draw on Introduction to Algorithms by Cormen, Leiserson and colleagues, third edition, so you will want access to that textbook.

Bottom line: A complete intermediate algorithms course with solutions for every problem set and exam.

Frequently Asked Questions

Are solutions published?

Yes. Solutions are published for all ten problem sets, both quizzes and the final exam.

How should an algorithm be written up?

As a short essay: a description in English with pseudocode if helpful, a worked example or diagram, a proof of correctness and an analysis of running time, with clarity valued as much as correctness.

Who teaches the lectures?

Erik Demaine, Srini Devadas and Nancy Lynch taught this spring 2015 version, and the site includes their notes and recitation videos.

User Reviews

0.0 out of 5
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0

No reviews yet. Be the first to review this course.

There are no reviews yet.

Write your review

Reviews can only be posted by registered learners. Log in, then you will return here to post.

×

    Report this page
    Design and Analysis of Algorithms
    Design and Analysis of Algorithms
    LiveTalent
    Logo
    Compare items
    • Total (0)
    Compare
    0