Graphs and NP-completeness

Comments

Post a Comment

Popular posts from this blog

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

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