The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.
|
 |
|
Dev Shed Forums
> Programming Languages - More
> Other Programming Languages
|
Help with this algorithm..total newb
Discuss Help with this algorithm..total newb in the Other Programming Languages forum on Dev Shed. Help with this algorithm..total newb A place for discussing programming languages not covered in specific forums such as Assembler, COBOL, etc. - you get the idea.
|
|
 |
|
|
|
|

Dev Shed Forums Sponsor:
|
|
|

December 14th, 2012, 10:31 AM
|
|
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
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
|

December 15th, 2012, 04:24 AM
|
 |
pollyanna
|
|
Join Date: Jul 2012
Location: Germany
|
|
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?
|
Developer Shed Advertisers and Affiliates
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Rate This Thread |
Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|