Warning: Illegal string offset 'html' in /home/hsn/public_html/forum/cache/skin_cache/cacheid_1/skin_topic.php on line 909

Warning: Cannot modify header information - headers already sent by (output started at /home/hsn/public_html/forum/cache/skin_cache/cacheid_1/skin_topic.php:909) in /home/hsn/public_html/forum/admin/sources/classes/output/formats/html/htmlOutput.php on line 114

Warning: Cannot modify header information - headers already sent by (output started at /home/hsn/public_html/forum/cache/skin_cache/cacheid_1/skin_topic.php:909) in /home/hsn/public_html/forum/admin/sources/classes/output/formats/html/htmlOutput.php on line 127

Warning: Cannot modify header information - headers already sent by (output started at /home/hsn/public_html/forum/cache/skin_cache/cacheid_1/skin_topic.php:909) in /home/hsn/public_html/forum/admin/sources/classes/output/formats/html/htmlOutput.php on line 136

Warning: Cannot modify header information - headers already sent by (output started at /home/hsn/public_html/forum/cache/skin_cache/cacheid_1/skin_topic.php:909) in /home/hsn/public_html/forum/admin/sources/classes/output/formats/html/htmlOutput.php on line 137

Warning: Cannot modify header information - headers already sent by (output started at /home/hsn/public_html/forum/cache/skin_cache/cacheid_1/skin_topic.php:909) in /home/hsn/public_html/forum/admin/sources/classes/output/formats/html/htmlOutput.php on line 141
Standard Algorithms - HSN forum

Jump to content


Standard Algorithms


15 replies to this topic

#1 Michael

    Site Swot

  • Members
  • PipPipPipPip
  • 237 posts
  • Location:Glasgow
  • Gender:Male

Posted 26 May 2006 - 11:20 AM

Can anyone give me the standard algorithms for Linear search, counting occurences, find max and find min.

Cheers,

Mike

#2 coca

    Child Prodigy

  • Members
  • PipPipPipPipPipPip
  • 891 posts
  • Location:Stormwind City
  • Interests:Programming and gaming<br /><br />http://coca-123.bebo.com
  • Gender:Male

Posted 26 May 2006 - 12:11 PM

What the heck is linear search?

Counting occurrences:

Pseudocode:

Set the current position in the array to 0
Set the current number of occurrences to 0
While the current position is less than the number of array elements
Check if the current element equals the value we are looking for
If it is, increment occurrences by 1
End while
Number of occurrences is left in the occurrences variable smile.gif

C example:

CODE

int CountOccurrences(int * array, int ElementCount, int NumberToFind)
{
  int position = 0, occurrences = 0;
  for(;position<ElementCount;position++)
  {
    if(array[position]==NumberToFind)
      occurrences++;
  }
return occurrences;
}


Find max:

Set the current maximum to the value of the first element
Starting at the 2nd element, loop through all elements and check
on each iteration for the current element being larger in value than the current maximum, and if it is, set the current maximum to that value

CODE

int FindMax(int * array, int ElementCount)
{
int CurrentMax, position = 1;
if(ElementCount > 1)
  CurrentMax = *array;
else
   return 0;
for(;position<ElementCount;position++)
{
   if(array[position] > CurrentMax)
     CurrentMax = array[position];
}
return CurrentMax;
}


Find min:

Same as find max, except you compare values to find if the current element is smaller...

Hrm, I'm not sure about my Find Max/Min algos. Certainly that's how I'd code it, and it works, but I can't remember what the "official" answer is.



<MrBob> I hate Uni. At least in film studies we get to talk about Fight Club.
<@X-Factor> Wouldnt you be breaking the first 2 rules?


#3 AM4R

    Site Swot

  • Members
  • PipPipPipPip
  • 145 posts
  • Gender:Male
  • Gender:Male

Posted 26 May 2006 - 12:13 PM

sure,

Finding min

Set first to lowest in list
repeat
if next in list<min
make min = next in list
found_at=counter
until end of list
write minimum

Finding Max

same as above but change min to max, and < into>

Counting Occurences

target = 'random'
counter = 0
repeat
if next in value = targer
then counter = counter + 1
until end of list
if counter = 0 write'not found' (<<<<<<<<<<<<<<<<<<<linear search up to here)
write counter

I think thats what you wanted smile.gif


EDIT: just typed that for nothing, lol
::::::/\M/\R::::::

#4 st-and Paul

    Top of the Class

  • Members
  • PipPipPipPipPip
  • 356 posts
  • Location:St Andrews
  • Interests:Check facebook, i cant be bothered putting them all down again :P
  • Gender:Male

Posted 26 May 2006 - 02:07 PM

Linear search is an algorithm which manually searches through a collection of data and attempts to match a specified target. It examines each member and compares their equality and once has searched all data or finds the target will display the result of the search to the user. Here is an example in java:

public class repeat {

public static void main(String[] args) {
String target = "one";
int i =0;
String [] data = {"one", "two", "three"}; //declares an array as a type string with 3 elements in it
for(i=0; i<data.length; i++){ // iterates over the following code
if(data[i].equals(target)){
System.out.println("Target found " + data[i]);
i = data.length;
}
else{ System.out.println("Target not found");

}
}
}
}

Obviously usually the target is specified by the user. I have omitted it for simplicity here as reading input in Java requires exception handling to read input from a user. The linear search can be adapted to any situation and in the examination you will be expected to write the algorithm in pseudocode. An array was used in the above example but a linked list would probably more common if there is no way of knowing how much data was needed to search through.

#5 Michael

    Site Swot

  • Members
  • PipPipPipPip
  • 237 posts
  • Location:Glasgow
  • Gender:Male

Posted 26 May 2006 - 02:08 PM

Cheers smile.gif

#6 John

    HSN Legend

  • Members
  • PipPipPipPipPipPipPipPip
  • 2,713 posts
  • Location:In a Peripheral Estate in Glasgow
  • Interests:First the boring stuff:<br /><br />2004 Results:<br /><br />Highers:<br /><br />Computing A<br />Craft and Design A<br />Physics A<br />Administration A<br />English A<br />Maths A<br />Modern Studies A<br />French A<br /><br />2005 Results:<br /><br />Advanced Highers:<br />Computing A<br />Physics A<br />Maths A<br />Modern Studies A<br />English A<br /><br />2006 Results:<br /><br />Advanced Highers(All Crashed):<br />Chemistry A<br />Biology A<br />Business Managemnt A<br /><br />Aren't I marvellous?
  • Gender:Male

Posted 27 May 2006 - 12:47 PM

Linear search is an Advanced Higher Algorithm, i'm sure it isnt in the Higher.

Anyway here it is in Pseudocode(My Pseudocode skills aren't great btw)

1. Set Search Value to X and Found to False
2. Set Loop Size to Array Size
3. Compare Array(Loop) to Search Value
4. If Array(loop) = Search Value Goto Line 7
5. Else Increment Loop by 1
6. Goto Line 3
7. Set Found = True, and Display message

I would also recommend sticking to Pseudocode, as the examiner maynot know Java, C, C++, or whatever language you may want to use.

#7 Michael

    Site Swot

  • Members
  • PipPipPipPip
  • 237 posts
  • Location:Glasgow
  • Gender:Male

Posted 27 May 2006 - 12:54 PM

Its the pseudo code version that we are supposed to know and linear search is definately in it......i think lol. We were taught it once upon a time anyway lol.

#8 John

    HSN Legend

  • Members
  • PipPipPipPipPipPipPipPip
  • 2,713 posts
  • Location:In a Peripheral Estate in Glasgow
  • Interests:First the boring stuff:<br /><br />2004 Results:<br /><br />Highers:<br /><br />Computing A<br />Craft and Design A<br />Physics A<br />Administration A<br />English A<br />Maths A<br />Modern Studies A<br />French A<br /><br />2005 Results:<br /><br />Advanced Highers:<br />Computing A<br />Physics A<br />Maths A<br />Modern Studies A<br />English A<br /><br />2006 Results:<br /><br />Advanced Highers(All Crashed):<br />Chemistry A<br />Biology A<br />Business Managemnt A<br /><br />Aren't I marvellous?
  • Gender:Male

Posted 27 May 2006 - 01:00 PM

Just checked it is in the Higher, well it maybe, i checked Scholar not the Arrangements Document.

#9 Dave

    Ruler (but not owner) of hsn

  • Moderators
  • PipPipPipPipPipPipPipPip
  • 4,252 posts
  • Location:kilmarnock(ok kilmaurs)
  • Interests:programming, exercising, brass band, using this board
  • Gender:Male

Posted 27 May 2006 - 01:10 PM

i was sure it was in the higher that i sat but the course changed though

If i am not here i am somewhere else



#10 Michael

    Site Swot

  • Members
  • PipPipPipPip
  • 237 posts
  • Location:Glasgow
  • Gender:Male

Posted 27 May 2006 - 01:16 PM

It just changed this year, its basically the same though. They probably have just taken a few things out rather than add anything new.

#11 Dave

    Ruler (but not owner) of hsn

  • Moderators
  • PipPipPipPipPipPipPipPip
  • 4,252 posts
  • Location:kilmarnock(ok kilmaurs)
  • Interests:programming, exercising, brass band, using this board
  • Gender:Male

Posted 27 May 2006 - 01:19 PM

i tihnk the new course was to add content in rather than take it out. This is from the arrangements document

Description and exemplification of the following standard algorithms in pseudocode and an appropriate high level language:
linear search
counting occurrences
finding min/max

If i am not here i am somewhere else



#12 John

    HSN Legend

  • Members
  • PipPipPipPipPipPipPipPip
  • 2,713 posts
  • Location:In a Peripheral Estate in Glasgow
  • Interests:First the boring stuff:<br /><br />2004 Results:<br /><br />Highers:<br /><br />Computing A<br />Craft and Design A<br />Physics A<br />Administration A<br />English A<br />Maths A<br />Modern Studies A<br />French A<br /><br />2005 Results:<br /><br />Advanced Highers:<br />Computing A<br />Physics A<br />Maths A<br />Modern Studies A<br />English A<br /><br />2006 Results:<br /><br />Advanced Highers(All Crashed):<br />Chemistry A<br />Biology A<br />Business Managemnt A<br /><br />Aren't I marvellous?
  • Gender:Male

Posted 27 May 2006 - 01:25 PM

QUOTE(Dhesi @ May 27 2006, 02:16 PM) View Post

It just changed this year, its basically the same though. They probably have just taken a few things out rather than add anything new.


It changed lat year, but was a dual running.

QUOTE(Dave @ May 27 2006, 02:19 PM) View Post

i tihnk the new course was to add content in rather than take it out. This is from the arrangements document

Description and exemplification of the following standard algorithms in pseudocode and an appropriate high level language:
linear search
counting occurrences
finding min/max



They have added and removed things.

Some of the Programming unit is now in the AH and Software Dev unit, and alot has been added to the Networking unit.

#13 Michael

    Site Swot

  • Members
  • PipPipPipPip
  • 237 posts
  • Location:Glasgow
  • Gender:Male

Posted 27 May 2006 - 01:36 PM

I dont do networking and cant really speak for the software development unit, its still the easiest one tongue.gif

Does anyone have a list of the programming languages and features of each I should know about for higher?

#14 Dave

    Ruler (but not owner) of hsn

  • Moderators
  • PipPipPipPipPipPipPipPip
  • 4,252 posts
  • Location:kilmarnock(ok kilmaurs)
  • Interests:programming, exercising, brass band, using this board
  • Gender:Male

Posted 27 May 2006 - 01:40 PM

do you have to know languages? are you sure

Visual Basic - event driven,
Java, C#,J# - object orientated
Prolog - declaritive, AI
php, VB script, javascript - scripting language


If i am not here i am somewhere else



#15 Michael

    Site Swot

  • Members
  • PipPipPipPip
  • 237 posts
  • Location:Glasgow
  • Gender:Male

Posted 27 May 2006 - 02:36 PM

No i mean like declarative, procedural etc

#16 John

    HSN Legend

  • Members
  • PipPipPipPipPipPipPipPip
  • 2,713 posts
  • Location:In a Peripheral Estate in Glasgow
  • Interests:First the boring stuff:<br /><br />2004 Results:<br /><br />Highers:<br /><br />Computing A<br />Craft and Design A<br />Physics A<br />Administration A<br />English A<br />Maths A<br />Modern Studies A<br />French A<br /><br />2005 Results:<br /><br />Advanced Highers:<br />Computing A<br />Physics A<br />Maths A<br />Modern Studies A<br />English A<br /><br />2006 Results:<br /><br />Advanced Highers(All Crashed):<br />Chemistry A<br />Biology A<br />Business Managemnt A<br /><br />Aren't I marvellous?
  • Gender:Male

Posted 27 May 2006 - 03:57 PM

They can be found in this thread HERE!!!

And no Dave, you do not need to know specific languages, but it is very useful to know some for each one, as you can then give examples of each.





1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users