Coursera
Coursera Logo

Stanford University - Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming 

  • Offered byCoursera

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
 at 
Coursera 
Overview

Duration

15 hours

Start from

Start Now

Total fee

Free

Mode of learning

Online

Difficulty level

Intermediate

Official Website

Explore Free Course External Link Icon

Credential

Certificate

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
 at 
Coursera 
Highlights

  • Shareable Certificate Earn a Certificate upon completion
  • 100% online Start instantly and learn at your own schedule.
  • Course 3 of 4 in the Algorithms Specialization
  • Flexible deadlines Reset deadlines in accordance to your schedule.
  • Intermediate Level
  • Approx. 15 hours to complete
  • English Subtitles: Arabic, French, Portuguese (European), Italian, Vietnamese, German, Russian, English, Spanish
Read more
Details Icon

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
 at 
Coursera 
Course details

Skills you will learn
More about this course
  • The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
 at 
Coursera 
Curriculum

Week 1

Application: Internet Routing

Application: Sequence Alignment

Introduction to Greedy Algorithms

Application: Optimal Caching

Problem Definition

A Greedy Algorithm

Correctness Proof - Part I

Correctness Proof - Part II

Handling Ties [Advanced - Optional]

MST Problem Definition

Prim's MST Algorithm

Correctness Proof I

Correctness Proof II

Proof of Cut Property [Advanced - Optional]

Fast Implementation I

Fast Implementation II

Week 1 Overview

Overview, Resources, and Policies

Lecture slides

Optional Theory Problems (Week 1)

Problem Set #1

Programming Assignment #1

Week 2

Kruskal's MST Algorithm

Correctness of Kruskal's Algorithm

Implementing Kruskal's Algorithm via Union-Find I

Implementing Kruskal's Algorithm via Union-Find II

MSTs: State-of-the-Art and Open Questions [Advanced - Optional]

Application to Clustering

Correctness of Clustering Algorithm

Lazy Unions [Advanced - Optional]

Union-by-Rank [Advanced - Optional]

Analysis of Union-by-Rank [Advanced - Optional]

Path Compression [Advanced - Optional]

Path Compression: The Hopcroft-Ullman Analysis I [Advanced - Optional]

Path Compression: The Hopcroft-Ullman Analysis II [Advanced - Optional]

The Ackermann Function [Advanced - Optional]

Path Compression: Tarjan's Analysis I [Advanced - Optional]

Path Compression: Tarjan's Analysis II [Advanced - Optional]

Week 2 Overview

Optional Theory Problems (Week 2)

Problem Set #2

Programming Assignment #2

Week 3

Introduction and Motivation

Problem Definition

A Greedy Algorithm

A More Complex Example

Correctness Proof I

Correctness Proof II

Introduction: Weighted Independent Sets in Path Graphs

WIS in Path Graphs: Optimal Substructure

WIS in Path Graphs: A Linear-Time Algorithm

WIS in Path Graphs: A Reconstruction Algorithm

Principles of Dynamic Programming

Week 3 Overview

Problem Set #3

Programming Assignment #3

Week 4

The Knapsack Problem

A Dynamic Programming Algorithm

Example [Review - Optional]

Optimal Substructure

A Dynamic Programming Algorithm

Problem Definition

Optimal Substructure

Proof of Optimal Substructure

A Dynamic Programming Algorithm I

A Dynamic Programming Algorithm II

Week 4 Overview

Optional Theory Problems (Week 4)

Info and FAQ for final exam

Problem Set #4

Programming Assignment #4

Final Exam

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
 at 
Coursera 
Admission Process

    Important Dates

    May 25, 2024
    Course Commencement Date

    Other courses offered by Coursera

    – / –
    Start Now
    – / –
    – / –
    – / –
    – / –
    – / –
    Start Now
    View Other 6713 CoursesRight Arrow Icon
    qna

    Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
     at 
    Coursera 

    Student Forum

    chatAnything you would want to ask experts?
    Write here...