Algorithms in Swift

Introduction to Graduate Algorithms - Udacity

Dynamic Programming

Lesson 1 - source code

• Fibonacci
• Longest Common Subsequence
• Longest Increasing Subsequence

Lesson 2 - source code

• Knapsack problems with or without repetition of items
• Chain Matrix Multiplication

Lesson 3 - source code

• Find the shortest path using Dijkstra's algorithm
• Find the shortest path using Bellman-Ford's algorithm
• Find negative weight cycle using Floyd Warshall's algorithm (incomplete)

Randomized Algorithms

Lesson 1 - source code

• Modular Arithmetic
• Multiplicative Inverses
• Euclid's Algorithm (GCD)
• Extended Euclid's Algorithm

Lesson 2 - source code

• Euler's Theorem
• RSA Algorithm and Implementation
• Primality Tests

Lesson 3 - source code

• Implementation of Hash Map
• Implementation of Bloom Filter

Divide and Conquer

Lesson 1 - source code

• Merge Sort
• Multiplication using Divide and Conquer approach

Lesson 2 - source code

• Find Kth Smallest in an unsorted array
• Find Kth Largest in an unsorted array
• Quick Sort

Lesson 3 - source code

• Sum of Geometric Series

Lesson 4 - source code

• Polynomial Multiplication
• Fast Fourier Transform - FFT

Lesson 5 - source code

• Polynomial Multiplication using FFT

Graph Algorithms

Lesson 1 - source code

• Depth First Search (DFS)
• Breadth First Search (BFS)
• Topological Sort
• Find Strongly Connected Components (SCCs) by DFS

Lesson 2 - source code

• 2-Satisfiability (2-SAT) Problem
• Find bridge in graph

Lesson 3 - source code

• Union-Find algorithm
• Detect cycles in graph
• Bipartite in graph
• Find Miniumum Spanning Tree (MST)

Lesson 4 - source code

• PageRank (PR)

Max Flow

Lesson 1 - source code

• Find maximum flow by Ford Fulkerson algorithm

Lesson 2 - source code

• Find minimum cut

Lesson 3 - source code

• Application - image segmentation (incomplete)

Lesson 4 - source code

• Find maximum flow by Edmonds Karp algorithm

Lesson 5 - source code

• Circulation with demands

Linear Programming

Lesson 1 - source code

• Simplex algorithm

Lesson 2 - source code

• Determine optimum in Simplex

Lesson 3 - source code

• Determine feasible, infeasible, bounded and unbounded results

Lesson 4 - source code

• Application - Max SAT problem (incomplete)

NP-completeness

Lesson 1 - Lesson 5 (Not covered in this repo)

Credits:

• Udacity Course - Introducation to Graduate Algorithms
• Geeks for Geeks