Trees and Graphs: Basics

Trees and Graphs: Basics

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

Instructor: Sriram Sankaranarayanan

Access provided by Veterans Transition Support

21,766 already enrolled

4 modules

Gain insight into a topic and learn the fundamentals.

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

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