Little oh-notation:
In mathematical relation,
f(n) = o(g(n)) means
lim f(n)/g(n) = 0
n→∞
Eg: 7n + 8 ∈ o(n2)
Little omega-notation:
In mathematical relation,
if f(n) ∈ ω(g(n)) then,
lim f(n)/g(n) = ∞
n→∞
Eg: 4n + 6 ∈ ω(1);
Computational procedure:
The procedure of calculating; determining something by mathematical or logical methods is
called computation procedure.
Program:
A program is a set of instructions that a computer follows in order to perform a particular
task.
Recurrence relation:
A recurrence relation is an equation that defines a sequence based on a rule that gives the
next term as a function of the previous term(s).
Need of studying algorithms:
We learn by seeing others solve problems and by solving problems by ourselves. Being
exposed to different problem-solving techniques and seeing how different algorithms are
designed helps us to take on the next challenging problem that we are given.
Algorithm design technique:
In the field of computing, an algorithm is a set of instructions applied to solve a particular
problem.
The technique of designing algorithms is called Algorithm design technique.
Following are some of the main algorithm design techniques:
Brute-force or exhaustive search
Divide and Conquer
Greedy Algorithms
Dynamic Programming
Branch and Bound Algorithm
Randomized Algorithm
Backtracking
Worst-case efficiency:
Worst Case Efficiency - is the maximum number of steps that an algorithm can take for any
collection of data values.
Maximum number of comparisons taken.
Best-case efficiency:
Best Case Efficiency - is the minimum number of steps that an algorithm can take any
collection of data values. In Big Oh Notation, O(1) is considered as best case efficiency.
Average case efficiency:
Average Case Efficiency - average comparisons between minimum no. of comparisons and
maximum no. of comparisons.
Minimum number of comparisons = 1
Maximum number of comparisons = n
Therefore, average number of comparisons = (n + 1)/2
(n + 1)/2 is a linear function of n. Therefore, the average case efficiency will be expressed as
O(n).
Recursive algorithm for solving Tower of Hanoi problem:
For a given n number of disks, the way to accomplish the task in a minimum number of steps
is:
Non-recursive algorithm to find out the largest element in a list of n numbers:
ALGORITHM MaxElement(A[0..n − 1])
//Determines the value of the largest element in a given array
//Input: An array A[0..n − 1] of real numbers
//Output: The value of the largest element in A
maxval ← A[0]
for i ← 1 to n − 1 do
if A[i] > maxval
maxval ← A[i]
return maxval
Input size:
The input size is given as a function of the input(s) (for the problem). So we measure time in
the steps the algorithm takes with respect to the input size (for any instance of said problem,
this is where your analysis will matter).
Prior estimation:
It means we do analysis (space and time) of an algorithm prior to running it on specific
system - that is,
we determine time and space complexity of algorithm by just seeing the algorithm rather than
running it on particular system (with different processor and compiler).
Posterior estimation:
It means we do analysis of algorithm only after running it on system. It directly depends on
system and changes from system to system.
Steps involved in the Analysis of Algorithms.
A complete analysis of the running time of an algorithm involves the following steps:
• Implement the algorithm completely.
• Determine the time required for each basic operation.
• Identify unknown quantities that can be used to describe the frequency of execution of
the basic operations.
• Develop a realistic model for the input to the program.
• Analyze the unknown quantities, assuming the modelled input.
• Calculate the total running time by multiplying the time by the frequency for each
operation, then adding all the products.
Exponential growth functions:
An exponential growth or decay function is a function that grows or shrinks at a constant
percent growth rate. The equation can be written in the form
f(x) = a(1 + r)x or f(x) = abx where b = 1 + r.
Where
a is the initial or starting value of the function,
r is the percent growth or decay rate, written as a decimal,
b is the growth factor or growth multiplier. Since powers of negative numbers behave
strangely, we limit b to positive values.
How to measure an algorithm’s running time?
Algorithm’s running time can be measured by using the following notations.
• Big Oh notation
• Theta notation
• Omega notation.
General plan for analyzing the efficiency for recursive algorithms:
General Plan for Analyzing the Time Efficiency of Recursive Algorithms
• Decide on a parameter (or parameters) indicating an input’s size.
• Identify the algorithm’s basic operation.
• Check whether the number of times the basic operation is executed can vary on
different inputs of the same size; if it can, the worst-case, average-case, and best-case
efficiencies must be investigated separately.
• Set up a recurrence relation, with an appropriate initial condition, for the number of
times the basic operation is executed.
• Solve the recurrence or, at least, ascertain the order of growth of its solution.
General plan for analyzing the efficiency for non-recursive algorithms.
The five steps are:
• Decide on parameter n indicating input size.
• Identify algorithm’s basic operation.
• Determine worst, average, and best case for input of size n.
• Set up summation for C(n) reflecting algorithm’s loop structure.
• Simplify summation.
Distinguish performance analysis and performance measurement:
Performance analysis estimates space and time complexity in advance, while performance
measurement measures the space and time taken in actual runs.
Computing time of selection sort algorithm and other algorithms
Algorithm to find mean and variance of an array
Two common summaries of data are the mean and the variance.
The mean of this set of values is
Mean = x-bar = sum x_i / n
The variance of N observations, x1,x2, . . . ,xN, is
Variance = s^2 = sum (x_i - x-bar)^2 / (n-1)
Time complexity is O(n) for both mean and variance.
Average case efficiency of binary search:
The average case efficiency of Binary search is O(log n).
Difference between linear search and binary search:
Linear search is a search that finds an element in the list by searching the element
sequentially until the element is found in the list.
On the other hand, a binary search is a search that finds the middle element in the list
recursively until the middle element is matched with a searched element.
The time complexity of linear search is O(n).
The time complexity of Binary search is O(log n).
Objectives of sorting Algorithms:
The objective of the sorting algorithm is to rearrange the records so that their keys are
ordered according to some well-defined ordering rule.
There are three reasons for studying sorting algorithms.
• sorting algorithms illustrate many creative approaches to problem solving and these
approaches can be applied to solve other problems.
• sorting algorithms are good for practicing fundamental programming techniques using
selection statements, loops, methods, and arrays.
• sorting algorithms are excellent examples to demonstrate algorithm performance.
In Merge sort while merging the solutions if list-1 contains p elements and list-2
contains q elements, what are the minimum and maximum comparison’s we require?
Minimum comparisons are min(p,q)
Maximum comparisons are p+q
When quicksort behaves in worst case situation?
When the elements are already in sorted order, quick sort behaves in worst case situation, and
the complexity is O(n2).
Disadvantages of binary search algorithm are:
• It employs recursive approach which requires more stack space.
• Programming binary search algorithm is error prone and difficult.
Weighted tree.
A tree to whose nodes and/or edges labels (usually number) are assigned.
The word "weight" also has a more specific meaning when applied to trees, namely the
weight of a tree at a point is the maximum number of edges in any branch at.
How divide and conquer technique can be applied to binary trees?
Finding the middle element and key element is compared with the middle element. If they are
equal, search is successful.
Else if key is less than the middle element search continues in the left subtree, else search
continues in the right sub tree.
In this way divide and conquer will be applied for binary search.
Define Substitution method with suitable example:
The substitution method is the algebraic method to solve simultaneous linear equations. As
the word says, in this method, the value of one variable from one equation is substituted in
the other equation.
Solve linear equations x+y=2 and 2x+3y=4 using Substitution Method
Difference between quick sort and merge sort:
Merge sort uses two arrays for sorting, whereas quick sort is in-place sorting.
The worst case time complexity of Merge sort is O(n log n), but for Quick sort it is O(n2)
Limitations of quick sort.
• It is recursive. Especially, if recursion is not available, the implementation is
extremely complicated.
• It requires quadratic (i.e., n2) time in the worst-case.
• It is fragile, i.e. a simple mistake in the implementation can go unnoticed and cause it
to perform badly.
Limitations of merge sort.
• Slower comparative to the other sort algorithms for smaller tasks.
• goes through the whole process even if the list is sorted (just like insertion and bubble
sort?)
• uses more memory space to store the sub elements of the initial split list.
Greedy technique:
Greedy Method. Among all the algorithmic approaches, the simplest and straightforward
approach is the Greedy method. In this approach, the decision is taken on the basis of current
available information without worrying about the effect of the current decision in future.
Applications of greedy technique?
Job sequencing with deadlines
Knapsack problem
Minimum cost spanning trees
Single source shortest path problem
How the choices are made in each step in greedy method?
The choice made by a greedy algorithm may depend on choices made so far, but not on future
choices or all the solutions to the subproblem.
It iteratively makes one greedy choice after another, reducing each given problem into a
smaller one. In other words, a greedy algorithm never reconsiders its choices.
Principle of optimality.
Principle of Optimality: An optimal policy has the property that whatever the initial state and
initial decision are, the remaining decisions must constitute an optimal policy with regard to
the state resulting from the first decision.
Drawbacks of greedy algorithm:
• It is not suitable for Greedy problems where a solution is required for every
subproblem like sorting.
• In such Greedy algorithm practice problems, the Greedy method can be wrong; in the
worst case even lead to a non-optimal solution.
• Therefore the disadvantage of greedy algorithms is using not knowing what lies ahead
of the current greedy state.
Greedy choice property:
Greedy-choice property: a globally optimal solution can be arrived at by making a locally
optimal (greedy) choice.
steps required to develop a greedy algorithm:
Steps for achieving a Greedy Algorithm are:
Feasible: Here we check whether it satisfies all possible constraints or not, to obtain at least
one solution to our problems.
Local Optimal Choice: In this, the choice should be the optimum which is selected from the
currently available
Unalterable: Once the decision is made, at any subsequence step that option is not altered.
Difference between dynamic programming and greedy algorithm:
Difference between dynamic programming and divide and conquer strategies:
Principle behind dynamic programming:
The dynamic programming relies on a principle of optimality. This principle states that in an
optimal sequence of decisions or choices, each subsequence must also be optimal.
Drawbacks of Dynamic Programming:
• It takes a lot of memory to store the calculated result of every sub problem without
ensuring if the stored value will be utilized or not.
• Many times, output value gets stored and never gets utilized in the next sub problems
while execution. It leads to unnecessary memory utilization.
• In DP, functions are called recursively. Stack memory keeps increasing.
Features of Dynamic Programming:
Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem
by breaking it down into simpler sub problems and utilizing the fact that the optimal solution
to the overall problem depends upon the optimal solution to its sub problems.
Overlapping Subproblems
Subproblems are smaller versions of the original problem. Any problem has overlapping sub-
problems if finding its solution involves solving the same subproblem multiple times.
Optimal Substructure Property
Any problem has optimal substructure property if its overall optimal solution can be
constructed from the optimal solutions of its subproblems
Applications of dynamic programming:
• 0/1 knapsack problem
• All pairs shortest path problem
• Travelling sales person problem
• Reliability design
• optimal binary search tree
Running time of traveling salesman problem and 0/1 knapsack problem
• Traveling salesman problem O(n2 2n)
• Knapsack problem O(2n/2)
Steps involved in dynamic programming:
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom-up fashion.
4. Construct an optimal solution from computed information.
Memory function in dynamic programming:
Dynamic programming solves problems that have a recurrence relation. Using the
recurrences directly in a recursive algorithm is a top-down technique. It has the
disadvantage that it solves common sub problem multiple times. This leads to poor
efficiency, exponential.
The dynamic programming technique is bottom-up, and solving all the sub-problems only
once. This has the disadvantage that some of the sub-problems may not have been necessary
to solve. Illustrate in the table. We would like to have the best of both worlds, i.e. all the
necessary sub-problem solved only once. This is possible using memory functions.
The technique uses a top-down approach, recursive algorithm, with table of sub-problem
solution. Before determining the solution recursively the algorithm checks if the sub problem
has already been solved by checking the table. If the table has a valid value then the
algorithm uses the table value else it proceeds with the recursive solution.
How dynamic programming solves complex problems:
Dynamic Programming is a method for solving a complex problem by breaking it down into
a collection of simpler subproblems, solving each of those subproblems just once, and storing
their solutions using a memory-based data structure (array, map,etc).
Applications of traveling sales person problem:
The traveling salesman problem (TSP) is a problem in combinatorial optimization and has
several applications, such as vehicle routing problems, logistics, planning and scheduling.
Exhaustive search:
In computer science, brute-force search or exhaustive search, also known as generate and test,
is a very general problem-solving technique and algorithmic paradigm that consists of
systematically enumerating all possible candidates for the solution and checking whether
each candidate satisfies the problem's statement.
Categories of the problem in backtracking:
There are three types of problems which can be solved using backtracking :
• Decision Problem : Search for a feasible solution.
• Optimisation Problem : Search for the best solution.
• Enumeration Problem : Find all feasible solutions.
State Space Tree:
A state space tree is a tree constructed from all of the possible states of the problem as nodes,
connected via state transitions from some initial state as root to some terminal state as leaf.
Solution states and answer state:
Solution states are the problem states s for which the path from the root node to s defines a
tuple in the solution space
• In variable tuple size formulation tree, all nodes are solution states
• In fixed tuple size formulation tree, only the leaf nodes are solution states
Answer states are those solution states s for which the path from root node to s defines a tuple
that is a member of the set of solutions
• These states satisfy implicit constraints
Difference between Backtracking & Exhaustive search:
• Brute-force search (BFS) or Exhaustive search is a type of algorithm which computes
every possible solution to a problem and then selects one that fulfills the
requirements.
• Backtracking is an extension to BFS in which the implicit constraints are evaluated
after every choice (as opposed to after all solutions have been generated), which
means that potential solutions can be discarded before they have been 'finished'.
Promising and non promising node:
A node is said to be promising if the partial solution is still feasible. Any time the partial node
becomes infeasible the node, called non-promising the branch will no longer be pursued.
So, the algorithm backtracks to the first promising node and explores the other branches of
the state-space tree.
live node:
A node which has been generated and all of whose children have not yet been generated is
called a live node.
E-node:
The live node whose children are currently being generated is called the E-node(node being
expanded).
Dead node:
A dead node is a generated node which is not to be expanded further or all of whose children
have been generated.
Answer states:
Answer state: It is a node which is present in answer. Answer state is the problem state S for
which the path from the root to S defines a tuple which is the member of the set of solutions
(i.e. satisfies implicit constraints). All solution states are not answer states.
Tree organization of the 4-queens solution space. Nodes are numbered as in depth first
search.
Difference between dynamic programming and backtracking:
Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem
by breaking it down into simpler subproblems and utilizing the fact that the optimal solution
to the overall problem depends upon the optimal solution to its subproblems.
It basically reduces overlays in the problem having overlapping solutions. Therefore reducing
the time complexity.
It is also about building a recursive relation between the functions and subproblems and store
them in a data structure generally an array.
Subproblems are smaller versions of the original problem. Any problem has overlapping sub-
problems if finding its solution involves solving the same subproblem multiple times.
Backtracking is an algorithmic-technique for solving problems recursively by trying to build
a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the
constraints of the problem at any point of time (by time, here, is referred to the time elapsed
till reaching any level of the search tree).
Backtracking algorithm determines the solution by systematically searching the solution
space for the given problem. Backtracking is a depth-first search with any bounding
function. All solution using backtracking is needed to satisfy a complex set of constraints.
The constraints may be explicit or implicit.
Factors that influence the efficiency of Backtracking:
The efficiency of the backtracking algorithm depends on reject returning true for candidates
that are as close to the root as possible. If reject always returns false, the algorithm will still
find all solutions, but it will be equivalent to a brute-force search.
The efficiency of the backtracking algorithm depends on Branching factor also.
Polytime reducible:
In computational complexity theory, a polynomial-time reduction is a method for solving one
problem using another.
One shows that if a hypothetical subroutine solving the second problem exists, then the first
problem can be solved by transforming or reducing it to inputs for the second problem and
calling the subroutine one or more times. If both the time required to transform the first
problem to the second, and the number of times the subroutine is called is polynomial, then
the first problem is polynomial-time reducible to the second.
Halting Problem:
In computability theory, the halting problem is the problem of determining, from a
description of an arbitrary computer program and an input, whether the program will finish
running, or continue to run forever.
Approximate solution:
Sometimes it is difficult to solve an equation exactly. However, an approximate
solution may be accurate enough for solving the considered equation.
Satisfiability problem:
Boolean Satisfiability or simply SAT is the problem of determining if a Boolean formula is
satisfiable or unsatisfiable. Satisfiable : If the Boolean variables can be assigned values such
that the formula turns out to be TRUE, then we say that the formula is satisfiable.
Examples of NP-Problems:
• Travelling salesman problem
• 0/1 knapsack problem
Examples of P-Problems:
• Linear search
• Binary search
• Sorting