Graph Search, Shortest Paths, and Data Structures

Location type
Logo Coursera
Provider rating: starstarstarstar_borderstar_border 6.3 Coursera has an average rating of 6.3 (out of 4 reviews)

Need more information? Get more details on the site of the provider.

Description

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).

Who is this class for: Learners with at least a little bit of programming experience who want to learn the essentials of algorithms. In a University computer science curriculum, this course is typically taken in the third year.

Created by:  Stanford University
  • Taught by:  Tim Roughgarden, Professor

    Computer Science
Basic Info C…

Read the complete description

Frequently asked questions

There are no frequently asked questions yet. Send an Email to info@springest.com

Didn't find what you were looking for? See also: Algorithms, Computer Science, Programming, Hour of Code, and Ruby on Rails.

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).

Who is this class for: Learners with at least a little bit of programming experience who want to learn the essentials of algorithms. In a University computer science curriculum, this course is typically taken in the third year.

Created by:  Stanford University
  • Taught by:  Tim Roughgarden, Professor

    Computer Science
Basic Info Course 2 of 4 in the Algorithms Specialization Level Intermediate Commitment 4 weeks of study, 4-8 hours/week Language English How To Pass Pass all graded assignments to complete the course. User Ratings 4.8 stars Average User Rating 4.8See what learners said Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from your peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

Stanford University The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is an American private research university located in Stanford, California on an 8,180-acre (3,310 ha) campus near Palo Alto, California, United States.

Syllabus


WEEK 1


Week 1
Breadth-first and depth-first search; computing strong components; applications.


9 videos, 4 readings expand


  1. Reading: Week 1 Overview
  2. Reading: Overview, Resources, and Policies
  3. Reading: Lecture slides
  4. Video: Graph Search - Overview
  5. Video: Breadth-First Search (BFS): The Basics
  6. Video: BFS and Shortest Paths
  7. Video: BFS and Undirected Connectivity
  8. Video: Depth-First Search (DFS): The Basics
  9. Video: Topological Sort
  10. Video: Computing Strong Components: The Algorithm
  11. Video: Computing Strong Components: The Analysis
  12. Video: Structure of the Web [Optional]
  13. Reading: Optional Theory Problems (Week 1)

Graded: Problem Set #1
Graded: Programming Assignment #1

WEEK 2


Week 2
Dijkstra's shortest-path algorithm.


4 videos, 2 readings expand


  1. Reading: Week 2 Overview
  2. Video: Dijkstra's Shortest-Path Algorithm
  3. Video: Dijkstra's Algorithm: Examples
  4. Video: Correctness of Dijkstra's Algorithm
  5. Video: Dijkstra's Algorithm: Implementation and Running Time
  6. Reading: Optional Theory Problems (Week 2)

Graded: Problem Set #2
Graded: Programming Assignment #2

WEEK 3


Week 3
Heaps; balanced binary search trees.


9 videos, 1 reading expand


  1. Reading: Week 3 Overview
  2. Video: Data Structures: Overview
  3. Video: Heaps: Operations and Applications
  4. Video: Heaps: Implementation Details [Advanced - Optional]
  5. Video: Balanced Search Trees: Operations and Applications
  6. Video: Binary Search Tree Basics, Part I
  7. Video: Binary Search Tree Basics, Part II
  8. Video: Red-Black Trees
  9. Video: Rotations [Advanced - Optional]
  10. Video: Insertion in a Red-Black Tree [Advanced]

Graded: Problem Set #3
Graded: Programming Assignment #3

WEEK 4


Week 4
Hashing; bloom filters.


9 videos, 3 readings expand


  1. Reading: Week 4 Overview
  2. Video: Hash Tables: Operations and Applications
  3. Video: Hash Tables: Implementation Details, Part I
  4. Video: Hash Tables: Implementation Details, Part II
  5. Video: Pathological Data Sets and Universal Hashing Motivation
  6. Video: Universal Hashing: Definition and Example [Advanced - Optional]
  7. Video: Universal Hashing: Analysis of Chaining [Advanced - Optional]
  8. Video: Hash Table Performance with Open Addressing [Advanced - Optional]
  9. Video: Bloom Filters: The Basics
  10. Video: Bloom Filters: Heuristic Analysis
  11. Reading: Optional Theory Problems (Week 4)
  12. Reading: Info and FAQ for final exam

Graded: Problem Set #4
Graded: Programming Assignment #4
Graded: Final Exam
There are no reviews yet.

Share your review

Do you have experience with this course? Submit your review and help other people make the right choice. As a thank you for your effort we will donate $1.- to Stichting Edukans.

There are no frequently asked questions yet. Send an Email to info@springest.com