Trees and Graphs: Basics

Trees and Graphs: Basics

This course is part of Foundations of Data Structures and Algorithms Specialization

Instructor: Sriram Sankaranarayanan

21,797 already enrolled

Included with

Learn more

4 modules

Gain insight into a topic and learn the fundamentals.

187 reviews

Advanced level

Recommended experience

Flexible schedule

3 weeks at 10 hours a week

Learn at your own pace

91%

Most learners liked this course

4 modules

Gain insight into a topic and learn the fundamentals.

187 reviews

Advanced level

Recommended experience

Flexible schedule

3 weeks at 10 hours a week

Learn at your own pace

91%

Most learners liked this course

What you'll learn

Define basic tree data structures and identify algorithmic functions associated with them
Execute traversals and create graphs within a binary search tree structure
Describe strongly connected components in graphs

Skills you'll gain

Tools you'll learn

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

16 assignments

Taught in English

See how employees at top companies are mastering in-demand skills

Learn more about Coursera for Business

logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

Build your subject-matter expertise

This course is part of the Foundations of Data Structures and Algorithms Specialization

When you enroll in this course, you'll also be enrolled in this Specialization.

Learn new concepts from industry experts
Gain a foundational understanding of a subject or tool
Develop job-relevant skills with hands-on projects
Earn a shareable career certificate

There are 4 modules in this course

Basic algorithms on tree data structures, binary search trees, self-balancing trees, graph data structures and basic traversal algorithms on graphs. This course also covers advanced topics such as kd-trees for spatial data and algorithms for spatial data.

Trees and Graphs: Basics can be taken for academic credit as part of CU Boulder’s Master of Science in Data Science (MS-DS) degree offered on the Coursera platform. The MS-DS is an interdisciplinary degree that brings together faculty from CU Boulder’s departments of Applied Mathematics, Computer Science, Information Science, and others. With performance-based admissions and no application process, the MS-DS is ideal for individuals with a broad range of undergraduate education and/or professional experience in computer science, information science, mathematics, and statistics. Learn more about the MS-DS program at https://www.coursera.org/degrees/master-of-science-data-science-boulder.

In this module, you will learn about binary search trees and basic algorithms on binary search trees. We will also become familiar with the problem of balancing in binary search trees and study some solutions for balanced binary search trees such as Red-Black Trees.

What's included

5 videos12 readings5 assignments1 programming assignment1 discussion prompt

5 videos Total 147 minutes

Binary Search Trees -- Introduction and Properties 22 minutes
Binary Search Trees -- Insertion and Deletion 31 minutes
Red-Black Trees Basics 33 minutes
Red-Black Trees -- Rotations/Algorithms for Insertion (and Deletion) 30 minutes
Skip Lists 30 minutes

12 readings Total 111 minutes

Course Updates and Accessibility Support 1 minute
Earn Academic Credit for your Work! 10 minutes
Course Support 10 minutes
Important Prerequisites 10 minutes
Logistics: Textbook and Readings 10 minutes
Important Specialization Information 10 minutes
Overview of Module 1 10 minutes
Reading CLRS Chapter 12 10 minutes
CLRS Chapter 12.1-12.3 10 minutes
CLRS Chapter 13 - 13.1 10 minutes
CLRS Chapter 13.2 - 13.3 10 minutes
Skip 10 minutes

5 assignments Total 150 minutes

Basics of Binary Search Trees 30 minutes
Binary Search Tree: Insert and Delete 30 minutes
Red-Black Tree Basics 30 minutes
Tree Rotations 30 minutes
Skip Lists 30 minutes

1 programming assignment Total 180 minutes

Binary Search Trees 180 minutes

1 discussion prompt Total 10 minutes

Introduce Yourself! 10 minutes

In this module, you will learn about graphs and various basic algorithms on graphs such as depth first/breadth first traversals, finding strongly connected components, and topological sorting.

What's included

7 videos6 readings4 assignments1 programming assignment

7 videos Total 125 minutes

Graphs and Their Representations 14 minutes
Graph Traversals and Breadth First Traversal 18 minutes
Depth First Search 33 minutes
Topological Sorting and Applications 11 minutes
Strongly Connected Components - Definitions 16 minutes
Strongly Connected Components - Properties 17 minutes
Strongly Connected Components - Algorithm 17 minutes

6 readings Total 60 minutes

Overview of Module 2 10 minutes
CLRS Chapter 22 (Section 22.1) 10 minutes
CLRS Chapter 22 (Section 22.2) 10 minutes
CLRS Chapter 22 (Section 22.3) 10 minutes
CLRS Chapter 22 (Section 22.4 10 minutes
CLRS Chapter 22 (Section 22.5) 10 minutes

4 assignments Total 120 minutes

Graph Representations 30 minutes
Combined Quiz on Graph Traversals 30 minutes
Topological Sort Graphs 30 minutes
Strongly Connected Components 30 minutes

1 programming assignment Total 180 minutes

Graphs 180 minutes

Union Find Data-structure with rank compression. Spanning trees and properties of spanning trees. Prim’s algorithm for finding minimal spanning trees. Kruskal’s algorithm for finding minimal spanning trees.

What's included

5 videos5 readings4 assignments1 programming assignment

5 videos Total 127 minutes

Amortized Analysis of Data Structures 28 minutes
Amortized Analysis: Potential Functions 26 minutes
Spanning Trees and Minimal Spanning Trees with Applications 26 minutes
Kruskal’s Algorithm for Finding Minimal Spanning Trees 8 minutes
Union-Find Data Structures and Rank Compression 38 minutes

5 readings Total 50 minutes

Overview of Module 3 10 minutes
CLRS Chapter 17 10 minutes
CLRS Chapter 23 (Section 23.1) 10 minutes
CLRS Chapter 23 (Section 23.2) 10 minutes
CLRS Chapter 21 10 minutes

4 assignments Total 120 minutes

Amortized Analysis 30 minutes
Minimum Spanning Tree 30 minutes
Kruskal's Algorithm 30 minutes
Disjoint Set Forest 30 minutes

1 programming assignment Total 180 minutes

Spanning Trees and Union-Find Data Structure 180 minutes

In this module, you will learn about: Shortest Path Problem: Basics. Bellman-Ford Algorithm for single source shortest path. Dijkstra’s algorithm. Algorithms for all-pairs shortest path problem (Floyd-Warshall Algorithm)

What's included

6 videos6 readings3 assignments1 programming assignment

6 videos Total 155 minutes

Shortest Path Problems and Their Properties 30 minutes
Bellman-Ford Algorithm for Single Source Shortest Paths 46 minutes
Dijkstra’s Algorithm for Single Source Shortest Paths with Nonnegative Edge Weights 20 minutes
Proof of Dijkstra's Algorithm 13 minutes
Shortest Path on DAGs 12 minutes
All Pairs Shortest Path Problems and Floyd-Warshall’s Algorithm 35 minutes

6 readings Total 60 minutes

Overview of Module 4 10 minutes
CLRS Chapter 24 (up to section 24.1) 10 minutes
CLRS Chapter 24 (Section 24.1) 10 minutes
CLRS Chapter 24 (Section 24.3 and 24.5) 10 minutes
CLRS Chapter 24 (Section 24.2) 10 minutes
CLRS Chapter 25 (Sections 25.1 and 25.2) 10 minutes

3 assignments Total 90 minutes

Shortest Path Problems Properties 30 minutes
Shortest Path - Bellman Ford Algorithm 30 minutes
Dijkstra's Algorithm 30 minutes

1 programming assignment Total 180 minutes

Shortest Path Algorithms 180 minutes

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.

Build toward a degree

This course is part of the following degree program(s) offered by University of Colorado Boulder. If you are admitted and enroll, your completed coursework may count toward your degree learning and your progress can transfer with you.¹

Instructor

Instructor ratings

(54 ratings)

Sriram Sankaranarayanan

University of Colorado Boulder

5 Courses 98,372 learners

Offered by

University of Colorado Boulder

Explore more from Algorithms

Status: Free Trial
Packt
Intermediate Algorithms: Graphs, Trees, and Backtracking
Course
Status: Free Trial
University of Colorado Boulder
Foundations of Data Structures and Algorithms
Specialization
Status: Free Trial
University of Colorado Boulder
Trees, SVM and Unsupervised Learning
Course
Status: Free Trial
University of Colorado Boulder
Algorithms for Searching, Sorting, and Indexing
Course

Why people choose Coursera for their career

Felipe M.

Learner since 2018

"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."

Jennifer J.

Learner since 2020

"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."

Larry W.

Learner since 2021

"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."

Chaitanya A.

"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

5 stars
75.93%
4 stars
16.57%
3 stars
4.27%
2 stars
1.06%
1 star
2.13%

Showing 3 of 187

Reviewed on Sep 12, 2024

Good but some typo's in the quizzes and assignments. Would like to see more thorough exercises

Reviewed on Sep 28, 2022

This course is easy to understand and implement. It needs more programming exercises further!

Reviewed on Jul 2, 2021

very solid course - would love more programming assignments and tougher final

View more reviews

Open new doors with Coursera Plus

Unlimited access to 10,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Learn more

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Explore degrees

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Learn more

Frequently asked questions

To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.

When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.

Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.