Skip to content

twho/algorithms-swift

BranchesTags

Repository files navigation

Algorithms in Swift

Introduction to Graduate Algorithms - Udacity

Swift 5 License

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

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:

About

Algorithms written in Swift for an Udacity course - Introduction to Graduate Algorithms

Topics

swift graph-algorithms linear-programming fast-fourier-transform divide-and-conquer randomized-algorithms maxflow-mincut dynamic-programing graduate-algorithms

Resources

Readme

License

MIT license
Activity

Stars

3 stars

Watchers

1 watching

Forks

4 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages