Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
December 14th, 2012, 10:31 AM
 Big Chaze
Registered User

Join Date: Dec 2012
Posts: 10
Time spent in forums: 1 h 53 m 48 sec
Reputation 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

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
December 15th, 2012, 04:24 AM
 Jacques1
pollyanna

Join Date: Jul 2012
Location: Germany
Posts: 1,869
Time spent in forums: 1 Month 2 Weeks 1 Day 22 h 57 m 55 sec
Reputation Power: 813
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?

 Viewing: Dev Shed Forums > Programming Languages - More > Other Programming Languages > Help with this algorithm..total newb