Hey there! Sign in to join this conversationNew here? Join for free
    Offline

    1
    ReputationRep:
    Has anybody seen or can anybody look at this playliston f453?
    https://www.youtube.com/playlist?lis...U3eNbOUtxFjTsZ

    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.
    • Thread Starter
    Offline

    7
    ReputationRep:
    (Original post by CheaterHater)
    Has anybody seen or can anybody look at this playliston f453?
    https://www.youtube.com/playlist?lis...U3eNbOUtxFjTsZ

    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.
    Offline

    1
    ReputationRep:
    (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?
    • Thread Starter
    Offline

    7
    ReputationRep:
    (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:

    Name:  IMG_1506.jpg
Views: 38
Size:  318.4 KB

    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.
    Offline

    1
    ReputationRep:
    (Original post by CheaterHater)
    Has anybody seen or can anybody look at this playliston f453?
    https://www.youtube.com/playlist?lis...U3eNbOUtxFjTsZ

    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?
    Offline

    12
    ReputationRep:
    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..
    Offline

    1
    ReputationRep:
    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
    • Thread Starter
    Offline

    7
    ReputationRep:
    (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
    Offline

    12
    ReputationRep:
    (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!
    • Thread Starter
    Offline

    7
    ReputationRep:
    (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!
    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
    Offline

    1
    ReputationRep:
    (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
    Offline

    2
    ReputationRep:
    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
    Offline

    12
    ReputationRep:
    (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.
    Offline

    5
    ReputationRep:
    (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!!
    Offline

    2
    ReputationRep:
    (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!
    Offline

    0
    ReputationRep:
    (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:

    Name:  IMG_1506.jpg
Views: 38
Size:  318.4 KB

    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.
    Offline

    1
    ReputationRep:
    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!
    Offline

    1
    ReputationRep:
    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
    Offline

    1
    ReputationRep:
    (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 feel the same, sure a lot feel a little disappointed. Lets work work work tonight and get A*s in F453 tomorrow
    Offline

    0
    ReputationRep:
    No each node in a binary tree is an integral part of its structure, to put this idea simply by deleting the node you are removing whatever organisation was there before.
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Would you like to hibernate through the winter months?
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.