How To Approach Algorithims (1 Viewer)

[Beaky]

Approaching algorithims by Sam Davis

The main problem is that every algorithm question is different. Writing algorithms is not something you can learn by rote and just spew out an answer. However you do need to understand the principles behind each of the standard searches and sorts. Some possible tips include:

- Try to solve a simpler case of the question first. For example work out how to process a single record first and then add the loops to iterate around through the whole record set and then generalise any constants by changing them to variables.

- Design data structures first. That is, write down the structure of any arrays or records you'll be using. This helps you maintain focus while you construct your algorithm and it also gives the marker a clearer understanding of where your answer is headed.

- The best answers solve the problem in the most efficient manner. If you think you've solved it then when checking think about ways to get out of loops as soon as the vital processing is done. For example setting a flag and using it as part of your loop condition. This can make the difference between 5/6 and 6/6.

- Generally better answers tend to be written in pseudocode. Pseudocode has the advantage of restricting you to standard control structures. Its also easier to slot in or remove statements here and there as you check your answer.

- If you're stuck then think in terms of simple example data. If you can actually do the processing on some example data then write down how you do that in step by step form. This will likely gain you a few marks and it may just allow you to formulate a more generalised algorithm.

- If you really have no idea then as a last resort reword the question in step by step form. Many algorithm questions are quite specific, and even the question itself contains a series of steps. Remember the aim is to rank student responses, at least you've shown that you understood the question whereas writing nothing always results in a zero.

- Everyone makes stupid mistakes. The best time to spot these is later on. Plan to have time at the end of the exam to reread all your answers, particularly the algorithms.

HTH
Sam Davis

 

[Beaky]

This will be stickied, once admin gets message

 

[Winston]

i think you should add this in the method of algorithm thread which is pinned, primarily because, it's practically about algorithms, and there's no need to pin so many things, like the School forum and UAI section has like 15 pinned items lol..

 

[fatmuscle]

Originally posted by Beaky
This will be stickied, once admin gets message

s t u c k !

 

[Fosweb]

There are a few algorithms that you really should just 'know' (learn...) because they dont change no matter what situation they are used in, and are common things that can make up part of an algorithm question.

Things like:
-Maximum/Minimum value in an array search. (One while loop, counter incremented and each value checked. Replace a variable value with the value of the array(counter) if it suits)
-Bubble Sort (You will need to know this bit (the 'swap' using a temp variable) in particular)

tempVar = list(x)
list(x) = list(x + 1)
list(x + 1) = tempVar

-Other sorts: I don't think these will be asked as algorithm questions, just because they tend to get a little more complicated.


-And Like Beaky said - use Pseudocode if you are allowed to. You can indent this way, neatness is far greater, its faster because you don't need to draw little boxes/etc, and you can add other things in.

 

[jm1234567890]

Repeat: not just better to use Psudocode...

NEVER use flowchart

NEVER!!!!

it takes about twice as long to make and difficult to connect to new page

 

[Beaky]

Yer your damn right Fosweb...

Pretty much in the HSC (from what I have seen) algorithims usually contain parts of the syllabus (like a swap routine or a linear search etc)... So I have just made like a "function library" of algorithim code... Not say im going to learn them off by heart, but there handy to use in an HSC. Also a great resource to n00b algorithimers like me...

Practcing algorithims has GREATLY helped and if only i had done it before the trials!!!

Software... even though u will give me shit marks i still love u!!!

 

[Winston]

Originally posted by Beaky
Yer your damn right Fosweb...

Pretty much in the HSC (from what I have seen) algorithims usually contain parts of the syllabus (like a swap routine or a linear search etc)... So I have just made like a "function library" of algorithim code... Not say im going to learn them off by heart, but there handy to use in an HSC. Also a great resource to n00b algorithimers like me...

Practcing algorithims has GREATLY helped and if only i had done it before the trials!!!

Software... even though u will give me shit marks i still love u!!!

lol it will be better off remembering your basic sort and search algorithms, who knows how cruel BOS can be, they can even ask you to write a specific sort algorithm.

 

[TrickmA]

lol @ Flowcharts, i remember the good old days bahaha

i learnt how to use algorithms in a few weeks now i have no problems what so ever, but it doesn't really matter because the HSC algorithms are quite easy.
"Create an array" or "Sort through these Records"

nothing to worry about

 

[Fosweb]

Originally posted by jm1234567890
it takes about twice as long to make and difficult to connect to new page

Never do a flowchart over multiple pages. The point about an algorithm is to simplify the problem into a number of steps. If your algorithm goes over a page long, then it is too complex, and you should modularise sections of it.

 

[TrickmA]

^

never DO a flowchart.

 

[Ragerunner]

If possible im ALWAYS going to do a flowchart.

I'd probably get 1/8 for an algorithm is i used pseudocode. Flowchart i'll get like 4

I just hope this HSC isn't too algorithm based. Anything else is fine by me. I was lucky that the CSSA paper this this wasn't too heavily absed on algorithms.

 

[honky tonk]

I always do pseudo code because it's quicker and easier. I can never get more than 2/7 for my flowcharts, but usually get 6/7 for my pseudo code. I hope they don't ask us to do a flowchart in the HSC.

 

[Ragerunner]

I hope they do for me

 

[chris42]

Is there any other algorithms structures we would need to know, like how to write an array, etc ?

EDIT :

Also does anyone know an algorithm for randomisiation ? ie. RND equilivant from visual basic

 

[Popo Nana]

I was wondering that myself. Recently, I've been using something like:

set Array(Index) to random

to set a random variable. But I don't know if this is correct or whathaveyou. Maybe there needs to be something after it, like:

set Array(Index) to random(1-100)

Ah, I don't know.

 

[J0n]

Originally posted by chris42
EDIT :

Also does anyone know an algorithm for randomisiation ? ie. RND equilivant from visual basic

There are a number of methods, but the most common is the Linear Congruential Generator. Basically, it involves multiplying your seed by a constant, adding another constant, and using the MOD operator with yet another constant.

RandomNumber = (SeedValue * FactorConstant + OffsetConstant) MOD ModConstant.

To get a random number between 0 and 1, the number is then divided by ModConstant.

The actual values are fairly important here...

First, to get a reasonable amount of resolution, ModConstant should be quite large. If, for instance, you had a ModConstant value of 4 then your random number generator would only generate 4 possible values. eg. 0, 0.25, 0.5 and 0.75

Second, your FactorConstant should be a fairly large number. When you multiply it by seed value, you should get a number several times larger than modconstant.

Third, Offset constant should be less than ModConstant. Mainly because the mod operation makes larger values pointless. The main function of Offset is to prevent certain errors. For instance, suppose you had

RandomNumber = SeedValue * factorConstand MOD ModConstant.

If SeedValue happened to be 0, you would be locked into 0 forever.


Fourth, your function should not get locked into a cycle, as above. You have to pick your values carefully but a good rule of thumb is to use Prime Numbers.

When you use the Randomize statement, VB sets the seed value according to the time.
I also think there was some question to do with something similar to this in one of the past prog comps - check their site and you'll probably find it (it was something to do with the chaos theory).
http://do.cse.unsw.edu.au/progcomp/index.html

 

[chris42]

Thanks for that , so In an exam you could use the statemement "RandomNumber = SeedValue * factorConstand MOD ModConstant "

 

[SamD]

You wont be asked for this sort of detail. In the exam it is reasonable to just assume that a random number generator exists (normally generating numbers from 0 to less than 1).

In pseudocode just write something like:

Set RanNum to random number from 0 to less than 1

And if you wanted to simulate a dice throw, ie, 1,2,3,4,5 or 6 then you'd add the line:

Set DiceResult to integer part of (RanNum*6 +1)

HTH
Sam

 

[Popo Nana]

Thanks Sam. I'll remember that in case it pops up.