Swift Algorithm Club: June Digest 2017

The Swift Algorithm Club is a popular open source project to implement popular algorithms and data structures in Swift, with over 13,000 stars on GitHub.

We periodically give status updates with how things are going with the project. There’s been quite a few updates to the repo this month, including 3 brand new contributions:

• Swift Minimum Coin Change
• Swift Minimum Spanning Tree (Kruskal’s & Prims)
• Swift Dijkstra’s Algorithm

Let’s dig in!

Minimum Coin Change

In the traditional coin change problem, you have to find all the different ways to change some money given a set of coins (i.e. 1 cent, 2 cents, 5 cents, 10 cents etc.).

For example, if you have the value of 4 Euro cents, that can be changed in three possible ways:

• Four 1 cent coins
• Two 2 cent coins
• One 2 cent coin and two 1 cent coins

The minimum coin change problem is a variation of the generic coin change problem, where you need to find the option that returns the least number of coins.

You can learn how to implement this in Swift here:

• Swift Minimum Coin Change Algorithm by Jacopo Mangiavacchi

Dijkstra’s Algorithm

This algorithm was invented in 1956 by Edsger W. Dijkstra, and is one of the most effective algorithms in finding the shortest paths from one point to all other points in a graph.

The best example is a road network. If you want to find the shortest path from two points, let’s say, from your house to your workplace, then you would use Dijkstra’s algorithm.

You can learn how to implement this in Swift here:

• Swift Dijkstra’s algorithm by Taras Nikulin

Minimum Spanning Tree

A minimum spanning tree (MST) of a connected undirected weighted graph has a subset of the edges from the original graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. There can be more than one MSTs of a graph.

There are two popular algorithms to calculate MST of a graph – Kruskal’s algorithm and Prim’s algorithm. Both algorithms have a total time complexity of O(ElogE) where E is the number of edges from the original graph.

You can learn how to implement this in Swift here:

• Swift Minimum Spanning Tree by Xiang Xin

Where To Go From Here?

The Swift Algorithm Club is always looking for new members. Whether you’re here to learn or here to contribute, we’re happy to have you around.

To learn more about the Swift Algorithm Club, check out our introductory article. We hope to see you at the club! :]

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

• You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
• Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
• Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
• Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
• And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.