#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    10
    Rep Power
    0

    Help with this algorithm..total newb


    I have not been able to figure these three algorithms, and Im gonna be tested on similar ones soon. Can anyone offer me a break down?

    Consider the following algorithm:
    L = input(”Input a list of positive integers:”)
    m = -1
    c = 0
    N = len(L)
    i=0
    while i < N do
    if (L[i] < 0) then
    print ”not expecting negative integer. Error.”
    STOP
    else if (m < L[i]) then
    m = L[i]
    c = 1
    else if (m == L[i]) then
    c = c + 1
    end if
    i = i + 1
    end while
    print m + ”,” + c

    It is not required that you show all of the work. Just writing the output of the
    algorithm is enough. But running the algorithm for a few elements of the list will
    give you an idea of how it’s working.
    3.1 What will be the output of the algorithm for input L = [2, 5, 1, 6,
    5, 6, 5].
    3.2 Run the algorithm for input L = [] i.e. an empty list. Hint: length
    of an empty list is 0.
    3.3 What does the algorithm do in general?
    3.4 What is the time complexity of the algorithm. Provide reasoning
    and/or proof.

    Buggy Bubble sort
    .
    Following is buggy implementation of bubble sort. A bug is a problem in the
    algorithm that would result in an undesired output. Identify what’s the problem
    and how would you fix it. You may assume that the user enters the correct input.
    Hint: there are 2 bugs
    L = input(”Input a list of integers:”)
    N = len(L)
    i=0
    while i < N do
    j = i + 1
    while (j < N) do
    if (L[i]  L[j]) then
    swap(L[i], L[j])
    j = j + 1
    end if
    end while
    i = i + 1
    end while


    Write an algorithm to reverse a list of elements. Take
    the list as an input from the user. Make sure to take care
    of all the boundary conditions. What is the time complexity
    of your algorithm.

    Example: given the following list of elements: [1, 5, a], the output should be [a, 5,
    1]. Hint: Make use of the swap(L[i], L[j]) function.

    Write an algorithm to find the median of a
    list of integers. Take the list as an input from the user.
    Make sure to take care of all the boundary conditions.
    What is the time complexity of your algorithm?
    Definition of median: It is a number such that half the integers in the list are smaller
    than this number and half are greater than this number.
    Example 1: The median in list of integers [5, 1, 3] is 3. Because, there is one
    integer less than 3 and one greater than 3.
    Example 2: The median in list of integers [5, 1, 3, 7] is 4. Because, there are 2
    integers less than 4 and two
  2. #2
  3. --
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Jul 2012
    Posts
    3,911
    Rep Power
    1045
    Hi,

    this is no homework service. We can help you with concrete questions, point out errors etc., but the initial ideas have to come from you.

    If you ever want to write code, you have to be able to think for yourself and come up with your own solutions. You don't learn just from other people explaining their ideas -- I'm pretty sure that's what you get every day in school, but obviously it's not enough. At some point, you have to actually start working yourself.

    The first thing you should do is write down an arbitrary list of (positive) integers and go through the first algrithm to see what it does with the list:
    Code:
    L = [2, 5, 1, 6, 5, 6, 5]
    What happens in the first iteration of the "while" loop?

IMN logo majestic logo threadwatch logo seochat tools logo