Scribd Logo
Upload

Welcome to Scribd!

  • 30 views

    Algorithms

    Uploaded by

    Lovedeep kaur
    Binary search works on a sorted list by comparing the search key to the middle element of the list. If the key is less than the middle element, it searches the lower half. If greater, it searches the upper half. This halves the search space at each step, resulting in O(log n) time complexity. The example shows searching for 13 in a sorted list, eliminating parts of the list in 3 passes. Brute force, greedy, divide and conquer, and dynamic programming are common algorithm design techniques. Brute force tries all solutions while greedy algorithms make locally optimal choices. Divide and conquer breaks problems into subproblems, solves them, and combines the solutions. Dynamic programming optimizes problems by storing results of sub

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Algorithms

    Uploaded by

    Lovedeep kaur
    30 views6 pages
    Binary search works on a sorted list by comparing the search key to the middle element of the list. If the key is less than the middle element, it searches the lower half. If greater, it searches the upper half. This halves the search space at each step, resulting in O(log n) time complexity. The example shows searching for 13 in a sorted list, eliminating parts of the list in 3 passes. Brute force, greedy, divide and conquer, and dynamic programming are common algorithm design techniques. Brute force tries all solutions while greedy algorithms make locally optimal choices. Divide and conquer breaks problems into subproblems, solves them, and combines the solutions. Dynamic programming optimizes problems by storing results of sub

    Original Title

    algorithms

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Binary search works on a sorted list by comparing the search key to the middle element of the list. If the key is less than the middle element, it searches the lower half. If greater, it searches the upper half. This halves the search space at each step, resulting in O(log n) time complexity. The example shows searching for 13 in a sorted list, eliminating parts of the list in 3 passes. Brute force, greedy, divide and conquer, and dynamic programming are common algorithm design techniques. Brute force tries all solutions while greedy algorithms make locally optimal choices. Divide and conquer breaks problems into subproblems, solves them, and combines the solutions. Dynamic programming optimizes problems by storing results of sub

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    30 views6 pages

    Algorithms

    Uploaded by

    Lovedeep kaur
    Binary search works on a sorted list by comparing the search key to the middle element of the list. If the key is less than the middle element, it searches the lower half. If greater, it searches the upper half. This halves the search space at each step, resulting in O(log n) time complexity. The example shows searching for 13 in a sorted list, eliminating parts of the list in 3 passes. Brute force, greedy, divide and conquer, and dynamic programming are common algorithm design techniques. Brute force tries all solutions while greedy algorithms make locally optimal choices. Divide and conquer breaks problems into subproblems, solves them, and combines the solutions. Dynamic programming optimizes problems by storing results of sub

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 6

    1) Explain Binary search with example?

    Ans: - The binary search implemented only sorted list of elements. The process starts with
    finding the element at the middle of the list and comparing the key value with the element in
    the middle of the list, if the value of the key is less than the element at the middle then the
    search process the key to the list up to the middle element and if the value of the key is
    greater than element at the middle then search the key from middle element to the end of the
    list.
    The complexity of binary search is o (log n).

    Algorithm:-

    Binary search(A[0,1,2,3…..n-1],key)

    low <-0
    high<-1
    while(low<=high)
    do
    {
    mid<-(low high)/2
    if(key=A[mid])
    then
    return mid
    else if(key<A[mid])
    then
    high<-m-1
    else
    low<-m+1
    }

    Example:-
    Perform binary search on below list for finding value 13.

    6 13 14 25 33 43 51 53 64 72 84 93 95 98
    0 1 2 3 4 5 6 7 8 9 10 11 12 13

    Pass1:-

    Low=0 high=13 mid=0+13/2=13/2=6.5~6

    6 13 14 25 33 43 51 53 64 72 84 93 95 98
    0 1 2 3 4 5 6 7 8 9 10 11 12 13

    1
    low mid high

    mid-value=51. Compare key value 13 with mid value 51.

    13<51 . So eliminate elements 51 and above. New list will be as follows

    6 13 14 25 33 43
    0 1 2 3 4 5

    Low mid high

    Pass2:-

    Low=0 high=5, mid=0+5/2=5/2=2.5


    In this case consider mid=3. The mid value 25 .compare the key value 13 with this
    mid value 25.
    13<25 so eliminate 25 and above elements.
    Now list will be as follows:

    6 13 14
    0 1 2

    Low mid high

    Pass3:-

    Low=0 high=2 mid=0+2/2=1


    Compare new value of key value and mid.
    13=13 .item is found and done.

    Pass Low high Mid-point Mid value


    1 0 13 6 51
    2 0 5 3 25
    3 0 2 1 13

    2
    2) Explain Brute Force, Greedy, Divide and Conquer and Dynamic programming
    techniques. And which algorithms are under in these techniques?
    Ans:-
    Brute Force: - brute force is a straightforward approach to solving a problem, usually
    directly based on the problem statement and definitions of the concept involved.
    It’s used for many elementary but algorithmic tasks such as computing the sum of n numbers,
    finding the largest element in a list and so on.

     Sorting, searching, matrix multiplication, string matching –the brute-force


    approach yields reasonable algorithms of at least some practical value with no
    limitation on instance size.

    Greedy: the greedy is most straightforward design technique which can be applied to a wide
    variety of problems. This algorithm works in steps. It is easy to implement and quite efficient
    in most of the cases.

    Greedy algorithms:-

     Kruskal’s minimum spanning tree


     Prim’s minimum spanning tree
     Dijkastra ‘s shortest path algorithm
     Knapsack problem
     Minimal spanning tree
     Job scheduling problem
     Graph-map colouring

    Divide and conquer: -


    This approach divides the problem into smaller but similar sub problems solve it, and these
    solutions to create a solution to the original problem.
    This technique can be divided into the following three parts:
    Divide: the problem into two or smaller sub problems.
    Conquer the sub problems by solving them recursively.
    Combine the solutions to the sub problems into the solutions for the original problems.
    The following are some algorithms that follows divide and conquer algorithms:

    3
     Binary search
     Quick sort
     Merge sort

    Dynamic programming: -
    Dynamic programming is an algorithm 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 problems depends upon the optimal solution to its sub problems.

    Dynamic programming algorithm

     Fibonacci number computed by iteration


     Wars hall’s algorithm implemented by iterations.
     All pair shortest path
     Longest common subsequence(LCS)

    3) Short Note

    a) Algorithm specification
    Ans:-
    An algorithm is defined as finite set of instructions that, if followed, performs a particular
    task. All algorithms must satisfy the following criteria
    Input: - An algorithm has zero, taken or collected from specified set of objects.
    Output: - An algorithm has one or more outputs having a specific relation to the inputs.
    Definiteness. Each step must be clearly defined. Each instruction must be clear and
    unambiguous.
    Finiteness: - the algorithm must always finish or terminate after a finite number of steps.
    Effectiveness. All operations to be accomplished must be sufficiently basic that they can be
    done exactly and in finite length.

    b) Induction proof

    Ans: - A proof by induction is just like an ordinary proof in which every step must be
    justified.
    Proof is a sequence of deductive steps

    4
     Basis step: - The algorithm is correct for base case or two by inspection.
     Inductive hypothesis (n=k):-Assume that the algorithm works correctly for the first K
    cases.
     Inductive step (n=k+1):- Given the hypothesis above, show that K+1 case will be
    calculated correctly.

    c) Time complexity of all algorithms


    Ans:-
    Algorithm Best time Average time Worst time Worst space
    complexity complexity complexity complexity
    Linear search O(1) O(n) O(n) O(1)
    Binary search O(1) O(logn) O(logn) O(1)
    Selection sort O(n^2) O(n^2) O(n^2) O(1)
    Merge sort O(nlogn) O(nlogn) O(nlogn) O(n)
    Quick sort O(nlogn) O(nlogn) O(n^2) O(logn)
    Kruskal’s O(e logv) O(e logv) O(e logv) O(e+v)
    Prim’s O(e logv) O(e logv) O(e logv) O(e+v)

    d) Identifying the repeated elements


    Ans:-
    You can find repeated elements in an array in time complexity O(n) and space complexity
    O(1) only when you are given limit of elements in array and limit must not exceed the array
    size. If limit is not given den u have to use another array of size MAX (element)-MIN
    (element) +1.

    So suppose u r given array of size n which contains elements of varying from 0 to n-1. You
    can use the index of elements to find repeated elements.

    Suppose array is 2,3,4,3,2,6,4 now size is 7 and element limits is 0 to 6.

    Algorithms:-

    1) Iterate the array from 1st element to last.

    2) 1st elements is 2 so check element in array with index 2 is >=0 if yes then change
    the element in array index 2 to -1*arr[abs(arr[i])]

    else print it.

    Check arr[abs(arr[i])]>0 if yes then make it arr[abs(arr[i])]= - arr[abs(arr[i])]

    else printf the abs(arr[i])

    5
    Example:-

    arr[]=2,3,4,3,2,6,4

    for i=0 array will be 2,3,-4,3,2,6,4

    for i=1 array will be 2,3,-4,-3,2,6,4

    for i-2 array will be 2,3,-4,-3,-2,6,4

    for i=3 array will be 2,3,-4,-3,2,6,4 it will print 3

    for i=4 array will be 2,3,-4,-3,2,6,4 it will print 2

    for i=5 array will be 2,3,-4,-3,2,6,-4

    for i=6 array will be 2,3,-4,-3,2,6,-4 it will print 4.

    e) Recursion

    Ans:-
    The process in which a function calls itself directly or indirectly is called recursion and the
    corresponding is called recursive function. Using recursive algorithm, certain problems can
    be solved quite easily.

    You might also like