Design and Analysis of Algorithm

Breadth First Search (BFS)

BFS(V, E, s) 1.         for each u in V − {s}             ▷ for each vertex u in V[G] except s. 2.             do color[u] ← WHITE 3.                 d[u] ← infinity...

Graphs Traversal/Searching

Graph Traversal To traverse a graph is to process every node in the graph exactly once. Because there are many paths leading from one node to another, the hardest...

Introduction to Graphs

Introduction to graphs Graphs are widely-used structure in computer science and different computer applications. We don’t say data structure here and see the difference. Graphs mean to store and...

Shortest Path by Dynamic programming

Given a cost matrix cost and a position (m, n) in cost, write a function that returns cost of minimum cost path to reach (m, n) from (0, 0)....

Calculation of binomial Co-efficient using Dynamic Programming

Following are common definition of Binomial Coefficients. 1) A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n. 2)...

Problems solved using Dynamic programming

  Calculation of binomial Co-efficient Making Change Problem Assembly Line Scheduling Knapsack Problem Shortest Path Matrix Chain multiplication Longest Common Subsequence

Dynamic Programming

Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. (“Programming” in this context refers to a tabular method, not to writing computer code.) divide-and-conquer...

Problem solved using Greedy strategy

  Problem solved using Greedy strategy Knapsack Prim`s Kruskal Finding Shortest Path Job Sequencing with deadline Activity Selection Problem  

Exponentation

Can we use divide-and conquer to solve the exponentiation problem (or to improve our solution)? What can we divide in half? (What gives the “size” of the problem?) Here’s...

Problems Solved by divide and conquer strategy

  Binary Search Quick Sort Merge Sort Matrix Multiplications Exponential