Skip to content

Algorithm

Algorithm is series of steps to solve a problem. In computer science an algorithm is used to solve problems. Algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

  • What is algorithm, space and time complexity?
  • Measuring space and time complexity
    • How we measure space and time complexity of algorithm depend on the computational model we are trying to use. Generally we use turing model of computing.
  • Why study analysis of algorithms?
    • Some algorithms are fast some are slow. Some take more space and some less.
    • To choose which algorithm to use we should have some analytical tools; these are provided by analysis of algorithms

Time complexity

  • Big \(O\) notation
  • lower bound, upper bound, tight bound
  • pseudo polynomial time, amortized time complexity
  • P vs NP: P, NP, NP-Complete, NP-Hard

Arrays

  • sorting
  • searching

Trees

  • Types: n-ary, complete tree, binary
  • Binary Trees
    • Traversal: - inorder, preorder, postorder, level order
    • Operations: insert, delete, search
    • Binary Heap
    • Binary search tree
      • Self balancing trees - AVL trees, red black trees
    • Segment Trees
    • Trie
    • Binary Index Trees

Graphs

  • Types: directed, undirected, weighted, cyclic, acyclic
  • Traversal: bfs, dfs
  • Operations
    • Check for cycle in graph
    • Find connected components
  • Minimum spanning tree
    • Kruskal Algorithm
    • Prim algorithms
    • Brovuka'a Algorithm
  • Shortest path from source to all other nodes
    • djkstra's
    • bellman ford's
  • Shortest path between all nodes to all other node
    • floyd warshall
    • Johnson's Algorithm
  • Directed Acyclic Graph (DAG): topological traversal
  • dfs-tree
  • bfs-tree
  • Connectivity
    • Path between two vertices
    • Bridges in a graph
    • Articulation Points
    • Eulerian Path
  • Maximum Flow
  • Union Find

Range Queries

  • Segment Tree
  • Binary Index Trees
  • sqrt decomposition

Strings

  • Pattern Matching
    • KMP method
    • rabin karp method
  • Trie

Hashing

  • simple hashing
  • collision on hashing

Algorithm Techniques

Resources