Algorithms

Collection of various algorithms and data structures. The content of this is mostly based on the courses Algorithms and Data Structures, Algorithms and Probability, and Discrete Mathematics at ETH Zürich.

Contents

Sorting and Searching Algorithms

• Search
  • Binary search
  • Interpolation search
  • Linear search
• Sort
  • Sortedness
  • Bubble sort
  • Selection sort
  • Insertion sort
  • Heap sort
  • Merge sort
  • Quicksort

Dynamic Programming

• Maximum subarray sum
• Fibonacci sequence
• Longest increasing subsequence
• Longest common subsequence
• Edit distance
• Subset sum problem
• Knapsack problem

Data Structures

• Abstract data types
  • Stack
  • Queue
  • Priority Queue
  • Dictionary
• Linked list
• Min-Heap
• Binary search tree

Graph Algorithms

• Graph
  • Adjacency matrix
  • Adjacency list
• Depth-first search
• Breadth-first search
• Topological sort
• Shortest Paths
  • BFS shortest path
  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall
• Minimum Spanning Trees
  • Prim

Number Theory

• Euclidean algorithm
• Extended Euclidean algorithm
• Diffie-Hellman protocol

Miscellaneous

• Karatsuba