Data Structures & Algorithms in Swift

Jan 29 2019 · Intermediate · Video Course · 2 hrs, 49 mins

Learn how to implement data structures and algorithms in Swift! This course covers a wide range of topics, from fundamental data structures to advanced pathfinding algorithms.

Version

  • Swift 4, iOS 12, Xcode 10

Elementary Data Structures

Introduction

4:58 Free

In this introductory episode, find out what we'll cover in the course, and familiarize yourself with Big O Notation.

1

Data structures are language agnostic. Swift is a great language to learn them in due to its high-level expressiveness and performance.

2

Stack

11:56

The Stack data structure gets its name from a stack of physical objects. When you add an item, you place it on top. And you'll always remove from the top too.

3

In your first challenge of the course, employ your stack data structure to check for balanced parentheses.

4

Queue

10:51

Queues use first-in-first-out (FIFO) ordering, meaning the first element that was enqueued will be the first to get dequeued.

5

"Whose turn is it?" You will never have to ask that question again after solving this next challenge!

6

These 3 sorting algorithms are not very performant, but are space efficient and easy to understand. What are Bubble Sort, Selection Sort, and Insertion Sort?

7

Merge Sort

9:41

Implement Merge Sort, a divide-and-conquer style algorithm and one of the most efficient general-purpose sorting algorithms around.

8

Conclusion

0:24

This episode concludes Part 1 of the course, reviews what you've learned, and hints at what's up next.

9

Trees

In this part, you'll learn about trees and build up the skills you need to implement a priority queue, which you'll need for graph-based algorithms.

10

Trees are used to tackle many recurring challenges in software development. Binary Trees, which limit children to two nodes, are the basis for many algorithms.

11

Who doesn't love to serialize and deserialize data? See if you can transform a tree into an array, and back!

12

Binary Search is one of the most efficient searching algorithms, but requires a sorted collection with constant time index manipulation capabilities.

13

Write a pair of customized binary search algorithms to find a range of indices for a given element in this challenge.

14

Heap

11:33 Free

Create the backbone of the Heap data structure, a special sort of binary tree that will support the rest of the algorithms in this course.

15

Heap Sort

12:26

Now that you're able to sift down elements in a heap, Heap Sort is trivial to implement. Finish off your Heap by sifting in the other direction: up.

16

Write a method that will let you know if a given Array represents a Heap. Swift's closures make it possible to use the same code for min and max heaps.

17

Combine your fully-featured Heap with a simple Queue interface, and you'll have a Priority Queue. Use it for working with maximum or minimum list values.

18

Conclusion

0:33

This episode concludes Part 2 of the course, reviews what you've learned, and hints and what's up next.

19

Graphs

A graph is a data structure that captures relationships using vertices connected by edges. You'll be using weighted, undirected graphs in this part.

20

Define a protocol that will apply to all Graphs. Vertex and Edge types will also be necessary for all concrete Graph implementations.

21

An Adjacency List is a compound data structure used to represent the edge connections of every vertex in a graph. You'll be using it for undirected graphs.

22

Design an algorithm to get all the paths from one vertex to another, in a graph, without any cycles.

23

Using a diagram of a graph, use Dijkstra's algorithm to choose vertices and edges to build up shortest paths.

24

Now that you understand Dijkstra's algorithm conceptually, it's time to create an API to use it for pathfinding!

25

Leverage Dijkstra's algorithm to find the shortest paths from one vertex in a graph to every other vertex–not just one in particular.

26

Use Prim’s algorithm to construct a minimum spanning tree for a graph (which is a lowest-cost subset of its edges).

27

Here's a minimum spanning tree that may have resulted from Prim’s algorithm. What is it that you can say about one of its mystery edges?

28

Conclusion

1:18

Congrats on completing the course! This episode offers advice on where to learn more about data structures and algorithms.

29

Contributors

Comments