Skip to content

Latest commit

 

History

History
100 lines (90 loc) · 3.29 KB

README.md

File metadata and controls

100 lines (90 loc) · 3.29 KB

Data structures

  1. ArrayList
  2. Heap
  3. LinkedQueue
  4. PriorityQueue (BinarySearchTree)
  5. LinkedStack
  6. BinarySearchTree
  7. BinarySearchTree (without link to parent)
  8. Union-Find
  9. LinkedList

Tasks

Sorting

  1. Heap sorting
  2. Insertion sorting
  3. Merge sorting
  4. Quick sorting

Tasks

Searching

  1. Binary searching

Graph Traversal

  1. Adjacency List structure
  2. Adjacency Matrix structure
  3. Incidence Matrix structure
  4. Breadth First Searching
  5. Depth First Searching (recursive)
  6. Depth First Searching (with stack)
  7. Colorizing vertices algorithm
  8. Finding articulation points
  9. Finding connected components
  10. Finding cycles
  11. Topological sorting
  12. Strongly connected components (Kosaraju algorithm)
  13. Strongly connected components (Tarjan algorithm)
  14. Converting from Adjacency Matrix into Adjacency List
  15. Converting from Adjacency List into Incidence Matrix
  16. Converting from Incidence Matrix into Adjacency List
  17. Calculating square of directed graph for Adjacency Matrix
  18. Calculating square of directed graph for Adjacency List
  19. Finding minimum vertex cover of a tree
  20. Finding minimum vertex cover of a tree such that the weight of each vertex is equal to the degree of that vertex
  21. Finding minimum vertex cover of a tree with arbitrary weights associated with the vertices
  22. Finding maximum independent set of a tree
  23. Removing an edge from graph

Tasks

Weighted Graph Algorithm

  1. Prim's algorithm of finding min spanning tree
  2. Kruskal's algorithm of finding min spanning tree
  3. Kruskal's algorithm of finding min spanning tree that uses union-find structure
  4. Dijkstra's Algorithm of finding shortest path of a graph
  5. Floyd-Warshall algorithm of finding all-pairs shortest path of a graph
  6. Ford-Fulkerson algorithm of finding maximum flow

Combinatorial Search and Heuristics Methods

  1. Backtracking
    • Generating all subsets of a set
    • Generating all permutations of a string
    • N-Queens problem
    • All paths between two vertices in a graph
    • Sudoku
    • Derangement of set
    • Graph isomorphism problem
    • Bandwidth minimization problem
    • Partition problem
    • Data compression
  2. Heuristic Search Methods
    • Monte-Carlo method for solving Travelling Salesman Problem
    • Local Search method for solving Travelling Salesman Problem
    • Simulated Annealing method for solving Travelling Salesman Problem
    • Simulated Annealing method for solving Bandwidth minimization problem

Dynamic Programming

  1. Fibonacci numbers
    • Naive Recursive
    • Memorized Recursive
    • Bottom Up
  2. Binomial Coefficients
  3. LevenshteinDistance
    • Naive Recursive
    • Memorized Recursive
    • Bottom Up
  4. Partition problem
  5. Parsing Context-Free Grammars
    • CYK Parsing Algorithm
  6. Minimum Weight Triangulation
  7. Change-making problem
    • Greedy algorithm
    • Classic algorithm
  8. Subset sum problem
  9. Max sum an arc of a circle of numbers
  10. Data compression

Intractable Problems and Approximations Algorithms

TODO