Graphs and NP-completeness

Comments

Post a Comment

Popular posts from this blog

Backtracking

Image
Index N-Queens Problem Hamiltonian Circuit Problem Subset-Sum Problem Branch and Bound Assignment Problem Knapsack Problem Traveling Salesperson Problem Backtracking is an algorithmic method to solve a problem in an additional way. It uses a recursive approach to explain the problems. We can say that backtracking is needed to find all possible combinations to solve an optimization problem. Backtracking is a systematic way of trying out different sequences of decisions until we find one that works. Suppose we have to make a series of decisions, among various choices, where we don't have enough information to know what to choose and each decision leads to a new set of choices, Some sequence of choices (possibly more than one) may be a solution to our problem Backtracking is a methodical way of trying out various seq...
Read more

Algorithms

Image
Index Algorithm Analyzing Algorithms Order Arithmetic Complexity of Algorithm Time Complexity Space Complexity Cost Complexity Worst-case Best-case Average-case Orders of Growth Asymptotic Analysis Asymptotic Notation Polynomial Runing time Exponential Runing time Principles of Algorithm Design Algoritm Design and Analysis Process Algorithm Algorithm is defined as a step by step procedure to perform a specific task within finite number of steps It can be defined as a sequence of definite and effective instructions, while terminates with the production of correct...
Read more

Basic Algorithm Design Techniques

Image
Index Divide and Conquer Greedy Approach Randomization Dynamic Programming Branch and Bound Backtracking Algorithms Algorithm Design Techniques For a given problem, there are many ways to design an algorithm for it, (e.g., Insertion sort is an Incremental approach). The following is a list of several popular design approaches. Divide-and-Conquer (D and C) Greedy Approach Dynamic Programming Branch-and-Bound Randomized Algorithms Backtracking Algorithms Divide-and-Conquer Divide the original problem into a set of subproblems Solve every subproblem individually, recursively Combine the solutions of the subproblems (top-level) into a solution of the whole original pro...
Read more