Algorithms and Data Structures in Swift 5

In this section we are going to talk about computational complexity. The Big-O notation is a mathematical model used in computer science to describe the efficiency of algorithms as a function of their input size. 

The best way to understand the Big-O thoroughly is via code examples. Therefore, we are going to illustrate each concept using live Swift coding.

I'll give you a quick overview of the common Big O time complexities: constant time, linear time, quadratic time, and logarithmic time. We'll discuss each of them in greater detail in the upcoming videos.

In this video, we'll delve into Constant Time complexity. I'll show you an example of an O(1) function and we'll discuss why constant time is the ideal Big O complexity.

In this lesson, we'll implement a high-precision QuartzCore-based benchmarking tool to measure execution times accurately. We’ll use this utility class to perform measurements in the upcoming demos.

In this lecture, we'll implement a couple of demo projects to illustrate the constant time complexity.

In this lecture, I'll demonstrate O(n)--linear time--complexity via Swift code examples.

The topic of this lecture is the Quadratic Time complexity. We are going to delve into the world of nested loops and we'll discuss why they should be avoided if possible.

Do your best to avoid polynomial time complexity. This lecture explains what to do if you encounter O(n^k).

Let's take a closer look at the logarithmic time complexity. Logarithmic time denotes an extremely efficient algorithm, such as the binary search technique.


Understanding the Big-O notation paves the road to working with algorithms. This lecture is a brief summary of what we've learned during this module.

Xcode playground projects for the Big-O section.

An overview of what we're going to cover in the Recursion section.

I'm going to show how what recursion is. We're going to analyze some examples and we'll even implement a recursive data structure.

In this video, I'm going to walk you through a demo to show you how recursion works. We're going to also solve an interesting problem.

Recursion is great, but it doesn’t come without pitfalls. The biggest problem is infinite recursion. I’m going to illustrate it using an Xcode playground project.

There are two basic rules we need to follow to avoid infinite recursion. Let's take a closer look at them.

Recursion demos.

In this section, we are going to take a closer look at the importance and the benefits of algorithms and algorithmic thinking.

In this lecture, we are going to implement a function which calculates the sum of the first N natural numbers. We’ll start with a naive implementation. 
Then, we are going to implement a more efficient way to solve this problem using a formula that is more than 2000 years old.

Our task is to implement a function that, given an array and a target value, returns zero-based indices of any two distinct elements whose sum is equal to the target sum.

In this lecture, we are going to build a function to find the equilibrium indices of an array. The equilibrium index of an array is an index such that the sum of elements at lower indices is equal to the sum of elements at higher indices.

In this section, we’ve seen some practical examples of solving problems using two different approaches. Let's recap the biggest take-aways.

The Power of Algorithms - Xcode playground projects.

This is what we're going to talk about in this section.

In this video, we'll try to solve a problem using a naive approach. We'll see where this leads and why generics are the way to go.

Generic structures provide an elegant solution to the problem presented in the previous lecture. Here's how.

Generic functions can work with any type. In this lecture, I'll show you how to avoid code repetition. We'll also talk about generic functions and type constraints.

Xcode playground projects for the Generics section.

We’ve seen that the array stores elements in a given order. We can even have duplicates in an array.
What if we need a collection that guarantees the uniqueness of its elements? The Set is the answer!

Now that we know how to create a Set, let’s talk about accessing and modifying its contents.

The Set exposes useful methods that let us perform fundamental set operations.

There will be cases when you need to adopt the Hashable protocol.
For example, if you want to create a Set with your custom type, or use it as a key in a Dictionary, you can't avoid conforming to Hashable.

The Dictionary, also known as hash-map, stores key-value pairs. In this lecture, we're going to talk about topics like dictionary creation, heterogeneous dictionaries, the AnyHashable protocol and much more.

The Dictionary provides various methods to access and modify its contents. This video takes a closer look at these methods.

Xcode playground projects for the "Built-In Swift Collection Types" section.

In this module, we'll focus mainly on data structures that are not part of the standard Swift library, such as queues, stacks, and linked lists.

The tuple is a lightweight data structure that can hold values of different types. Let's have a closer look and see how to create, access, and modify tuples.

A practical example of weighing the pros and cons of using different data structures.

The queue is a linear data structure that processes elements in the order they were added. We'll discuss how queues work, and we'll implement a generic queue from scratch. I'll also show you a practical example of using queues.

Follow along as I'll implement a generic queue in Swift.

Let's analyze a practical application that relies heavily on the queue data structure.

In this lecture, we'll discuss the deque--short for "double-ended queue"--a linear data structure that allows insertion and deletion at both ends.

We'll implement a solution to finding the maximum element within a sliding window of size k. Let's start by explaining the algorithm and a first attempt to solve the problem.

In this video, we'll discuss the benefits of a deque-based approach to solving the sliding window maximum algorithm.

A stack is a linear data structure that stores elements in a Last-In-First-Out (LIFO) order. This video discusses what you can do with a stack, what are its strengths and when should you use a different data structure.

In this video, I'll show you an efficient approach to implementing a stack using an array as its underlying storage.

Follow along as I demonstrate how stacks can be used to determine the validity of arithmetical expressions. This particular problem would serve as an excellent choice for a job interview question.

Xcode playground projects for the "Basic Data Structures and Their Practical Applications" section.

In this section we are going to talk about basic sorting algorithms.
Understanding the inner workings and knowing how to implement the basic sorting algorithms gives you a strong foundation to building other, more sophisticated algorithms.

We'll start the study of basic sorting algorithms with the selection sort algorithm. We are going to implement it in Swift. We’ll also visualize how selection sort works and we’ll analyze the time complexity of this algorithm.
Finally,we are going back up the theory with performance tests.

Let's quickly recap the pros and cons of the selection sort algorithm.

Insertion sort is a basic sorting algorithm, which works by analyzing each element and inserting it into its proper place, while larger elements move one position to the right. 

Insertion sort has quadratic time complexity. However, the performance of the insertion sort is largely affected by the initial order of the elements in the sequence.

In the previous lecture, we took a closer look at the insertion sort algorithm. Did you know that even Apple uses it in their sort() implementation? Check out why!

The topic of this lecture is Bubble Sort. This algorithm works by repeatedly evaluating adjacent items and swapping their position if they are in the wrong order. While it's easy to grasp and implement, you don't want to use it in production code. Let's see why!

A brief summary of the bubble sort algorithm.

Xcode playground projects for the Basic Sorting section.

A brief overview of what to expect in this section.

The merge sort is a fast divide-an-conquer algorithm. Check out this lecture to see what that means.

Merge sort in a nutshell.

In this lecture, we'll analyze the famous quicksort - the king of the compare-based sorting algorithms.

Let's recap what we've learned about the popular - and fast - quicksort algorithm.

Xcode playground projects for the Advanced Sorting section.