Algorithm Newbee

[shaqnolysis]

HELLO GREAT MINDS OF THE WORLD.....AM studying computer science and algorithms is a new concept to me....I have written an algorithm which returns a smallest value in an array and am not that sure if its correct....

1 s = A[1]

2 for i = 2 to lengthA[] do

3 if s > A then

4 s = A

5 return s

please analysis that and please help me by showing me how i can do an algorithm that output the largest and second largest values in an array A[ 1.....n] assuming n>1 and the values in the array are distinct .

[Hamrick]

am not that sure if its correct....

Lack of confidence in your algorithm is a serious flaw and you should make sure that it's correct. Do a quick test in your head with all permutations of three numbers.

{1,2,3}

s = 1
1 is not greater than 2
3 is not greater than 2
return 1

{2,1,3}

s = 2
2 is greater than 1
s = 1
3 is not greater than 2
return 1

{2,3,1}

s = 2
2 is not greater than 3
2 is greater than 1
s = 1
return 1

{3,2,1}

s = 3
3 is greater than 2
s = 2
2 is greater than 1
s = 1
return 1

{3,1,2}

s = 3
3 is greater than 1
s = 1
1 is not greater than 2
return 1

{1,3,2}

s = 1
1 is not greater than 3
1 is not greater than 2
return 1

That makes sure that the algorithm works for a non-empty array and checks every possible case. You can even automate that test for bigger arrays. Now test the edge cases. There's only one where the length of the array is 0.

{}

s = <error>

Setting s to A[1] is wrong if the array is empty because there's no A[1] to assign. Label that as bug #1 and keep testing. The next thing you test is how duplicates are handled.

{1,1,1}

s = 1
<the second>1 is not less than <the first>1
<the third>1 is not less than <the first>1
return <the first>1

Keep doing that for every case you can think of that might cause a problem and you'll gain a lot of confidence in your algorithm. :) You can even use the test cases as a way to make the algorithm or modify it for similar problems.

please help me by showing me how i can do an algorithm that output the largest and second largest values

The largest is just the inverse of the smallest. Instead of testing with >, use < and see what happens in the tests. ;) For the second largest the most obvious solution is to find the largest first and then do the search again but this time ignore anything that matches the largest. That way you get the second largest as a result. You don't need to get fancy with time complexity when you're just learning how to come up with algorithms. And processing the array twice probably won't be slow anyway unless the it's super huge.

[shaqnolysis]

thanx Hamrick.Your comment has boost my confidence.Lemme work on the next problem.i will post it for you to look at.I really appreciate your input.