15 replies to this topic

[Michael]

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

Cheers,

Mike

[coca]

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

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.

[AM4R]

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


EDIT: just typed that for nothing, lol

[st-and Paul]

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.

[Michael]

Cheers

[John]

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.

[Michael]

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.

[John]

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

[Dave]

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

[Michael]

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

[Dave]

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

[John]

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.

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.

[Michael]

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

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

[Dave]

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

[Michael]

No i mean like declarative, procedural etc

[John]

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.