OCR A2 Computing F453 Official Thread 22/06/2016 Exam Discussion

OP

Original post by CheaterHater

Has anybody seen or can anybody look at this playliston f453?
https://www.youtube.com/playlist?list=PL9GOZQCTC05DNyWi8wSU3eNbOUtxFjTsZ

It's quite good and extremely indepth but I want to know how much of this can actually come up in the exam, like writing the algorithm to the different tree traversals and stuff, there's a lot of videos in there where I know the basics about it and have done fine in papers with only that.

I have seen adding data to a binary tree algorithm in an exam paper once, it was worth 6 marks iirc. Another algorithm they like is the one to merge two sorted files.

Reply 222

CheaterHater

Original post by Dapperblook22

I have seen adding data to a binary tree algorithm in an exam paper once, it was worth 6 marks iirc. Another algorithm they like is the one to merge two sorted files.

Okay thanks, that's fine, the main thing I'm worried about then is the whole polish and reverse polish, I can't get my head around translating and writing them, is there any easy way to do them?

Reply 223

OP

Original post by CheaterHater

Okay thanks, that's fine, the main thing I'm worried about then is the whole polish and reverse polish, I can't get my head around translating and writing them, is there any easy way to do them?

A neat trick I have found with reverse polish when converting to infix is that the variables will always remain in the same place - the operators will move around.

Consider the reverse polish expression pq+rs-*.
This in infix is translated as (p+q)*(r-s). Note how p is always before q, r is always after p and before s.

Another neat way is post order traversal of a binary tree - they usually give reverse polish in this form:

Postfix (reverse polish) expressions can be determined by post-order traversal of a binary tree:

1. Traverse left subtree (PQ+)
2. Traverse right subtree (RS-)
3. Visit root (*)

Putting it all as one expression gives the reverse polish form PQ+RS-*
To check the expression in infix, you can use in-order traversal.

(edited 7 years ago)

Reply 224

CervixPounder

7

Original post by CheaterHater

Has anybody seen or can anybody look at this playliston f453?
https://www.youtube.com/playlist?list=PL9GOZQCTC05DNyWi8wSU3eNbOUtxFjTsZ

It's quite good and extremely indepth but I want to know how much of this can actually come up in the exam, like writing the algorithm to the different tree traversals and stuff, there's a lot of videos in there where I know the basics about it and have done fine in papers with only that.

I have never seen linked lists in a past paper question...Is it in the spec?

Reply 225

ryanroks1

12

Do we need an algorithm to delete a node from a binary tree? I can describe the steps but don't have a fully-rehearsed algorithm like I do for merging files for example..

Reply 226

joef1337

I think linked lists are on the spec, yes.

I think I'm strongest on questions about data structures and algorithms, but I'm not very good at questions with all the different types of diagrams

Reply 227

OP

Original post by ryanroks1

Do we need an algorithm to delete a node from a binary tree? I can describe the steps but don't have a fully-rehearsed algorithm like I do for merging files for example..

The algorithm I learnt was:

Traverse the tree until item is found
Remove the elements below the item...
...and store them
Delete the searched item
Traverse stored items back into tree

Reply 228

ryanroks1

12

Original post by Dapperblook22

The algorithm I learnt was:

Traverse the tree until item is found
Remove the elements below the item...
...and store them
Delete the searched item
Traverse stored items back into tree

Same as the one I have - just wasn't sure if it was detailed enough! I can't imagine many people (if anyone) having an algorithm fully describing every step so we should hopefully be fine. Thank you! :biggrin:

Reply 229

OP

Original post by ryanroks1

Same as the one I have - just wasn't sure if it was detailed enough! I can't imagine many people (if anyone) having an algorithm fully describing every step so we should hopefully be fine. Thank you! :biggrin:

The most detail I can think of adding to the algorithm is replacing the last line with the algorithm for inserting items into a tree - if they do ask us a question and it is 8 marks, I will probably replace the last line with that algorithm :tongue:

Reply 230

joef1337

Original post by Dapperblook22

The algorithm I learnt was:

Traverse the tree until item is found
Remove the elements below the item...
...and store them
Delete the searched item
Traverse stored items back into tree

The one I learnt is:

Traverse until item found
Go to the right node...
...and keep going left until there is no left node...
...This is the "next" value in the tree
Then swap replace the value of the searched node with this one
Then replace the branch that led to the next node with it's right node

It's hard for me to explain it, but I could write it in code

Reply 231

username1831327

2

Trying to revise but I can't concentrate knowing how badly I've ****ed up c3! bye bye A* I'll be lucky if I get an A

Reply 232

ryanroks1

12

Original post by lordyP

Trying to revise but I can't concentrate knowing how badly I've ****ed up c3! bye bye A* I'll be lucky if I get an A

I did C3 today too - it wasn't the nicest of papers so I'm pretty sure the boundaries will be quite nice - no more than 66 for an A* I reckon, and probably 59/60 for an A. There's still C4 to go as well, not all hope is lost! Good luck for tomorrow.

Reply 233

raman_17

5

Original post by lordyP

Trying to revise but I can't concentrate knowing how badly I've ****ed up c3! bye bye A* I'll be lucky if I get an A

im in the same situation!!

Reply 234

username1831327

2

Original post by ryanroks1

I did C3 today too - it wasn't the nicest of papers so I'm pretty sure the boundaries will be quite nice - no more than 66 for an A* I reckon, and probably 59/60 for an A. There's still C4 to go as well, not all hope is lost! Good luck for tomorrow.

I just made so many stupid mistakes that I've never done before in my life and it all just snowballed! Very worst case scenario is around 55/75 but hopefully it won't be that low as I might have picked up some method marks. It's disappointing as I averaged at 73/75 across the past papers, solomon papers and the gold papers and I even got 70/75 on the Jun 13 paper we did as a mock! But thank you and good luck too!

Reply 235

William_Hand

Original post by Dapperblook22

A neat trick I have found with reverse polish when converting to infix is that the variables will always remain in the same place - the operators will move around.

Consider the reverse polish expression pq+rs-*.
This in infix is translated as (p+q)*(r-s). Note how p is always before q, r is always after p and before s.

Another neat way is post order traversal of a binary tree - they usually give reverse polish in this form:

Postfix (reverse polish) expressions can be determined by post-order traversal of a binary tree:

1. Traverse left subtree (PQ+)
2. Traverse right subtree (RS-)
3. Visit root (*)

Putting it all as one expression gives the reverse polish form PQ+RS-*
To check the expression in infix, you can use in-order traversal.

Use a stack. Imagine that any operations are "Heavy" and crush the two numbers below into the result.

Reply 236

King_Kauko

3.3.5 Describe algorithms for the insertion, retrieval and deletion of data items stored in stack, queue and tree structures.

Can somebody post some examples of algorithms for these? I have a few ideas in mind but am concerned if we get one worth a lot of marks tomorrow!

Reply 237

King_Kauko

How is a stack used for parameter passing? (I understand and have done a question on procedure calling regarding a stack)

What is predicate logic?

How is SQL used to produce reports?

Chances of them making us draw a use case or communication diagram tomorrow? (object and class is more common so I think you would be easier anyway)

All the things I posted are gaps ion my knowledge and things that I think could happen tomorrow. Would appreciate any help :P p.s. all of these comments are directly linked to the specification and relevant or I wouldn't be wasting your time or my own :smile:

Reply 238

King_Kauko