Algorithm Problems Java

Recursion

• sumRecursive
• Factorial
• GCD
• HouseBuilding Head and Tail
• Linear Binary Search
• Tower Of HaNoi

Selection

• Quick Selection (kinda like Quick Sort)

Backtracking

• Coloring Problem
• Queens Problem
• Hamiltonian Cycle
• Knight Tour Problem
• Maze Problem
• Sodoku

Dynamic Programming

• Fibonacci
• Knapsack Problem
• Coin Change Problem
• rod Cutting Problem
• Subset Problem

Graph

• Graphs G(V,E) are mathematical structures to model pairwise relations between given objects
• A graph is made up of vertices/nodes and edges
• There are two types of graphs: directed and undirected graphs
• We know wht are graphs
  • First of all how to model them in programming languages?
    1. Adjacency matrix
    • We have an matrix constructed out of the vertices of the graph:
      • the A(i,j) value in the matrix is 1 if there is a connection between node i and node j
      • Otherwise A(i,j) is 0
    2. Edge list representation
    • We create a Vertix class
      • it stores the neighbors accordingly

        class Vertex
          vertex Name:
          visited;
          Vertex[] neighbors;

Breadth First Search (BFS)

• BFS
• WebCrawler

Depth First Search (DFS)

• DFS Implementation with Stack and Recusion
• Topological Ordering
• Cycle Detection
• Maze Solving Algorithm (BackTrack)

Memory complexity: BFS vs DFS

• In BFS, at the leaves -> if we have N items stored in the balanced tree, then there will be N/2 leave nodes.
  • So we have to store O(N) items if we want to traverse a tree that contains N items!!!
• In DFS, we ahve to backtrack (pop item from stack): so basically we just have to store as many items n the stack as the height of the tree -> which is log N !!!
  • so the memory complexity will be O(log N)
• That's why depth-first search is preferred most of the times. However, there may be some situations where VFS is better: AI, robot movements,..

Shortest Path Algorithms

• Dijkstra Algorithm
• Bellman-Ford Algorithm
• DAG Shortest Path
• FOREX Problem
• Longest Path