[exe]

(Original post by BalletDystopia)
Okay i know 3 tree traversals. Pre/In/Post order. Never done Breadth and depth before. So I just looked up depth first and I'm a little confused. Breadth is just going along each 'level' of the tree right to left and outputting them but I don't understand Depth first.

• In breadth-first searching we explore all the undiscovered neighbours of our root, and then all the undiscovered neighbours of these nodes until all the nodes are fully explored.
• In depth-first searching we explore all the neighbours to the left until we find a leaf, then we backtrack to that leaf’s root and explore to the right.


from the revision notes posted earlier

[gowans07]

Good luck to everyone tomorrow, no more posts from me. Your on you're own now...


This was posted from The Student Room's iPhone/iPad App

[Chrisaster]

(Original post by BalletDystopia)
Okay i know 3 tree traversals. Pre/In/Post order. Never done Breadth and depth before. So I just looked up depth first and I'm a little confused. Breadth is just going along each 'level' of the tree right to left and outputting them but I don't understand Depth first.

This might help:

[BalletDystopia]

(Original post by exe)
• In breadth-first searching we explore all the undiscovered neighbours of our root, and then all the undiscovered neighbours of these nodes until all the nodes are fully explored.
• In depth-first searching we explore all the neighbours to the left until we find a leaf, then we backtrack to that leaf’s root and explore to the right.


from the revision notes posted earlier

Got it now thanks.

[Amirrryy]

i dont know if there is any need to memorise this so can anyone please give an example of how this can be asked? thanks


Turing also conceived a universal Turing machine (UTM). The following description details a UTM which uses a single one-dimensional tape.
• The instructions of the Turing machine, M, are placed on the tape followed by the data, D, to be processed by M.
• The UTM, U, processes M and D by starting with its read/write head positioned on M and then moving between M and D as M is executed.
U may be a lot slower than M but it acts as an interpreter would, identifying the next instruction to be executed, and then executing it.

[jtanna]

(Original post by BalletDystopia)
Okay i know 3 tree traversals. Pre/In/Post order. Never done Breadth and depth before. So I just looked up depth first and I'm a little confused. Breadth is just going along each 'level' of the tree right to left and outputting them but I don't understand Depth first.

With depth first, you go through each 'line' of the tree. For example, in the tree below, depth-first will go ABCDE, whereas a breadth-first will go ABECD



Hope I actually explained that properly and didn't confuse you more!

Edit: Ignore the attached thumbnail...

[jtanna]

(Original post by Amirrryy)
i dont know if there is any need to memorise this so can anyone please give an example of how this can be asked? thanks


Turing also conceived a universal Turing machine (UTM). The following description details a UTM which uses a single one-dimensional tape.
• The instructions of the Turing machine, M, are placed on the tape followed by the data, D, to be processed by M.
• The UTM, U, processes M and D by starting with its read/write head positioned on M and then moving between M and D as M is executed.
U may be a lot slower than M but it acts as an interpreter would, identifying the next instruction to be executed, and then executing it.

A UTM is a Turing Machine that, given the instructions of an arbitrary Turing Machine, M, and data, D, faithfully executes the instructions of M, as M(D), or as if M was executing on data D.

• Instructions of machine M
• Data, D
• Executes 'faithfully' as if M(D)

[Amirrryy]

(Original post by jtanna)
A UTM is a Turing Machine that, given the instructions of an arbitrary Turing Machine, M, and data, D, faithfully executes the instructions of M, as M(D), or as if M was executing on data D.

• Instructions of machine M
• Data, D
• Executes 'faithfully' as if M(D)

yea but how can it be asked??

[BalletDystopia]

(Original post by jtanna)
With depth first, you go through each 'line' of the tree. For example, in the tree below, depth-first will go ABCDE, whereas a breadth-first will go ABECD



Hope I actually explained that properly and didn't confuse you more!

Edit: Ignore the attached thumbnail...

Confirmed what I thought. Thanks for this Always good to see a visual representation.

[Amirrryy]

i pasted this from a revision thingy its an example of backus-Naur form (BNF) being used. i am confused as to why for the "First bit" it has different versions like a letter and a number, two letters and a number or even a letter and two numbers....am i missing something or is it just because in this case a postcode can have various forms? i dont know this :L


thanks in advance

[ms607]

(Original post by Amirrryy)
i pasted this from a revision thingy its an example of backus-Naur form (BNF) being used. i am confused as to why for the "First bit" it has different versions like a letter and a number, two letters and a number or even a letter and two numbers....am i missing something or is it just because in this case a postcode can have various forms? i dont know this :L


thanks in advance

Yeah the first bit of UK postcodes can be like A12, AB12, A1, AB1

[ElMoro]

Hi, guys. I'm not actually taking this exam until next year (God willing I do well at AS) but I just wanted to wish you all luck. Hope it goes well for everyone

[jtanna]

(Original post by Amirrryy)
yea but how can it be asked??

Apologies. Usually, they'll ask, as in Jun11, "Explain what a Universal Turing Machine is.", or something like that. They may ask "How does a Universal Turing Machine differ to a standard Turing Machine", but not sure if they would... Maybe something like "How does a Universal Turing Machine's output differ to a standard Turing Machine?"

[Amirrryy]

(Original post by jtanna)
Apologies. Usually, they'll ask, as in Jun11, "Explain what a Universal Turing Machine is.", or something like that. They may ask "How does a Universal Turing Machine differ to a standard Turing Machine", but not sure if they would... Maybe something like "How does a Universal Turing Machine's output differ to a standard Turing Machine?"

thanks man!

[Amirrryy]

(Original post by ms607)
Yeah the first bit of UK postcodes can be like A12, AB12, A1, AB1

cheers. i have another question about BNF lol sorry. Is:

[A-Z] mean EITHER A OR B OR etc or does it mean you could have for exmaple AAABZD etc
essentially is [A-Z] the same as [A-Z]+ ?

thanks!

[Amirrryy]

if you for example want to define what letter is can you write it in two forms below? would they have the same meaning? they equal?

<letter>::= [A-Z]
or instead
<letter>::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P| Q|R|S|T|U|V|W|X|Y|Z

or do these have different meanings?

[exam2k10]

(Original post by jtanna)
Apologies. Usually, they'll ask, as in Jun11, "Explain what a Universal Turing Machine is.", or something like that. They may ask "How does a Universal Turing Machine differ to a standard Turing Machine", but not sure if they would... Maybe something like "How does a Universal Turing Machine's output differ to a standard Turing Machine?"

Just out of interest, "How does a Universal Turing Machine's output differ to a standard Turing Machine?"

[PreciseUrination]

[A-Z] = A OR B OR C etc....

However, [A-Z] * = zero or more of A or B or C etc

[joenye]

(Original post by exam2k10)
Just out of interest, "How does a Universal Turing Machine's output differ to a standard Turing Machine?"

I would very much like to know this also.

[joenye]

(Original post by Amirrryy)
if you for example want to define what letter is can you write it in two forms below? would they have the same meaning? they equal?

<letter>::= [A-Z]
or instead
<letter>::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P| Q|R|S|T|U|V|W|X|Y|Z

or do these have different meanings?

For BNF, you can't use the [A-Z] notation, as this is a regular expression. You do have to define it as:

<letter>::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P| Q|R|S|T|U|V|W|X|Y|Z

But I doubt they will ask you to write the entire alphabet tomorrow!