Traversing a tree - INORDER
Using this method, we must visit the tree in this order:
Visit the left sub-tree.
Visit the root node.
Visit the right sub-tree.
How does this work? We visit the left sub-tree, then the node, then the right sub-tree.
We start at the root, node A.
Underneath node A is the left sub-tree (with root node B) and the right sub-tree (with root node C).
We must check the left sub-tree first according to our INORDER rules. Move to B.
But B has a left sub-tree (with a root at D) and a right sub-tree (with a root at E).
We must check the left sub-tree first according to our INORDER rules. Move to D.
D does not have a left sub-tree, so visit the node D.
Now check for D’s right sub-tree. It doesn’t have one.
We have now done the left sub-tree for the tree that has a root node at B. Now visit node B.
Now visit the right sub-tree of B. We move to E.
E doesn’t have a left sub-tree so visit E.
E doesn’t have a right sub-tree so move to B and because we have now completely visited the tree with the root node at B, we move up to node A. Visit node A.
Now visit the right sub-tree of A. We move to C.
C doesn’t have a left sub-tree so visit C.
C doesn’t have a right sub-tree so move back up to A.
We have now visited every node.
The order that we visited the nodes was DBEAC. We can write an algorithm to print out all of the data at the nodes, like this:
1.For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 2. If there isn’t, go to 3.
2.Repeat 1.
3.Print the current node.
4.For the current node, check whether it has a right sub-tree. If it has, go to 5. else go to 6.
5.Repeat 1.
6.END
20.5.2 Traversing a tree - PREORDER
Using this method, we need to
Visit the root node.
Visit the left sub-tree.
Visit the right sub-tree.
Using our previous binary tree, we would visit the nodes in the order: A B D E C. We can write an algorithm that would print out all of the data at the nodes, like this:
1.Print the current node.
2.For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 1. If there isn’t, go to 3.
3.For the current node, check whether it has a right sub-tree. If it has, go to 4. else go to 5.
4.Repeat 1.
5.END.
Traversing a tree - POSTORDER
Using this method, we need to
Visit the left sub-tree.
Visit the right sub-tree.
Visit the root node.
Tuesday, 20 November 2007
Monday, 19 November 2007
Binary Trees
Task 11
1.For the current node, check if there is a left sub-tree. If there is, Go to 2. If there isn’t, go to 3.
2.Print the current node.
3.For the current node, check whether it has a right sub-tree. If it has, go to 5. else go to 6.
5.Repeat 1.
6.END
Task 12
Task 13
Task 14
INORDER F+5
PREORDER +F5
POSTORDER F5+
1.For the current node, check if there is a left sub-tree. If there is, Go to 2. If there isn’t, go to 3.
2.Print the current node.
3.For the current node, check whether it has a right sub-tree. If it has, go to 5. else go to 6.
5.Repeat 1.
6.END
Task 12
Task 13
Task 14
INORDER F+5
PREORDER +F5
POSTORDER F5+
Binary Trees
Task 9
Visit the left sub-tree.
Visit the root node.
Visit the right sub-tree.
Task 10
1.For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 2.
2.If there isn’t, go to 3. Repeat 1.
3.Print the current node.
4.For the current node, check whether it has a right sub-tree. If it has, go to 5. else go to 6.
5.Repeat 1.
6.END
Visit the left sub-tree.
Visit the root node.
Visit the right sub-tree.
Task 10
1.For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 2.
2.If there isn’t, go to 3. Repeat 1.
3.Print the current node.
4.For the current node, check whether it has a right sub-tree. If it has, go to 5. else go to 6.
5.Repeat 1.
6.END
Binary Trees
Task5 Traverse the tree until you find the item that you want to delete.
Call that item the root node.
Copy all of the items underneath the root node to another data structure, perhaps using a stack, for example.
Delete the root node.
Use the insertion algorithm to re-enter each data item in turn from the stack into the tree.
Task 6 Mandy
/ \
Ali John
\ / \
Emma peter Susan
/ \
Robert Tim
\
William
\
Tom
Robert
Tim
William
Tom
Mandy
/ \
Ali John
\ / \
Emma peter Robert
/ \
Tim William
/
Tom
Task7
50
/ \
25 74
/ \ \
17 35 80
\
90
50
/ \
25 74
/ \ \
17 35 80
Task8
Let TERMINAL NODE = ROOT NODE
If ROOT NODE = DATA ITEM
Then end
Else Transverse Until ROOT NODE = DATA ITEM
Binary Trees
Task1 + task4
Mandy
/ \
Ali John
\ / \
Emma peter Susan
/ \
Robert Tim
\
William
\
Tom
Task 2
50
/ \
25 74
/ \ \
17 35 80
\
90
Task 3
If the tree doesn't exist yet, make the DATA ITEM = ROOT NODE and finish.
Let CURRENT NODE = ROOT NODE.
Repeat until CURRENT NODE is null.
If DATA ITEM is less than CURRENT NODE, go to the left.
Else go to the right.
CURRENT NODE = value of node reached so far. (Node reached so far = null if there is no node at that position).
Create new node and add DATA ITEM to that position.
Wednesday, 7 November 2007
Assembly Language Questions
1. Most low level programming is carried out using assembly language. What typical scenario might mean that a program has to be written in machine code?
Someone who uses a program frequently may use machine code because it is 2 or 3 times quicker than using high level languages.
2. Why do assembly language instructions written for one type of machine not run on another?
The memory locations may store different things on a different computer therefore the assembly language will not be compatiable.
3. What is the purpose of the following parts of a typical assembly language instruction? (a)label (b)operation code (c)operands (d)comments.
Label: the leftmost item (e.g. Reset), it identifies each section of code and can be used as a pointer to show a jump command where to move to.
Operation (Op) code: the command to be carried out, usually shown as a mnemonic (e.g. ADD, MOV, etc).
Operands: the parts that the operation will be carried out on, they may have two parts (e.g. Acc 45 means the contents of the accumulator are moved to memory location 45).
Comments: assembly language code can be very long, so comments are used to explain what each command does as an aid to the programmer.
4. Why are different modes of addressing encountered when programming in assembly language?.
Different modes of addressing allow data to be manipulated if different ways according to the users requirements.
Explain what is meant by immediate, direct, indirect and indexed addressing.
Immediate addressing - this is where the data apperas immediately after the op code.
Direct addressing - refers directly to a specific memory location.
Indirect addressing - uses a number inside a register( usually an index register) to point to the memory location of interest where the actual data can be found.
Indexed addressing - a number conatained in one register is usually used in combination with the number in another register to point to the actual memory location where the data is stored.
5.AN assembly language instruction set may be broken down into subsets like 'logical', 'arithmetical' and 'control'. Making use of the arithmetical subset outlined in this chapter, show how two simple one-byte integer binary numbers may be added together.
[add] [al,bl] - [;Add bl to al and store the result in al] al = 00000001 bl= 00000010 al now = 00000011
6. Explain how a mask may be used to prevent alteration of the top(most significant) three bits and the bottom(least significant) two bits but set the rest of the bits in the register to 1. We use the or function. or al, bl in this example the first 3bits and last 2 bits are kept the same and the rest are rest to one. The or function means an output of 1 in either al or bl register or both will mean an output of one in the result.
1st operand al = 10101010
2nd operand bl = 10111110
result in al register 10111110
Someone who uses a program frequently may use machine code because it is 2 or 3 times quicker than using high level languages.
2. Why do assembly language instructions written for one type of machine not run on another?
The memory locations may store different things on a different computer therefore the assembly language will not be compatiable.
3. What is the purpose of the following parts of a typical assembly language instruction? (a)label (b)operation code (c)operands (d)comments.
Label: the leftmost item (e.g. Reset), it identifies each section of code and can be used as a pointer to show a jump command where to move to.
Operation (Op) code: the command to be carried out, usually shown as a mnemonic (e.g. ADD, MOV, etc).
Operands: the parts that the operation will be carried out on, they may have two parts (e.g. Acc 45 means the contents of the accumulator are moved to memory location 45).
Comments: assembly language code can be very long, so comments are used to explain what each command does as an aid to the programmer.
4. Why are different modes of addressing encountered when programming in assembly language?.
Different modes of addressing allow data to be manipulated if different ways according to the users requirements.
Explain what is meant by immediate, direct, indirect and indexed addressing.
Immediate addressing - this is where the data apperas immediately after the op code.
Direct addressing - refers directly to a specific memory location.
Indirect addressing - uses a number inside a register( usually an index register) to point to the memory location of interest where the actual data can be found.
Indexed addressing - a number conatained in one register is usually used in combination with the number in another register to point to the actual memory location where the data is stored.
5.AN assembly language instruction set may be broken down into subsets like 'logical', 'arithmetical' and 'control'. Making use of the arithmetical subset outlined in this chapter, show how two simple one-byte integer binary numbers may be added together.
[add] [al,bl] - [;Add bl to al and store the result in al] al = 00000001 bl= 00000010 al now = 00000011
6. Explain how a mask may be used to prevent alteration of the top(most significant) three bits and the bottom(least significant) two bits but set the rest of the bits in the register to 1. We use the or function. or al, bl in this example the first 3bits and last 2 bits are kept the same and the rest are rest to one. The or function means an output of 1 in either al or bl register or both will mean an output of one in the result.
1st operand al = 10101010
2nd operand bl = 10111110
result in al register 10111110
Tuesday, 6 November 2007
Assembly Language
Assembly language is second generation low level language made up from mnemonics which can be used instead of machine codebecause its easier to use. The format of of an assembly language instruction usually consists of four parts: label, op code,operand and comments. Label: the leftmost item (e.g. Reset), it identifies each section of code and can be used as a pointer to show a jump command where to move to.
Operation (Op) code: the command to be carried out, usually shown as a mnemonic (e.g. ADD, MOV, etc).
Operands: the parts that the operation will be carried out on, they may have two parts (e.g. Acc 45 means the contents of the accumulator are moved to memory location 45).
Comments: assembly language code can be very long, so comments are used to explain what each command does as an aid to the programmer.
Addressing Modes
If data is transferred from a source register to a destination register, then this is an example of register addressing.
Immediate addressing - this is where the data apperas immediately after the op code.
Direct addressing - refers directly to a specific memory location.
Indirect addressing - uses a number inside a register( usually an index register) to point to the memory location of interest where the actual data can be found.
Indexed addressing - a number conatained in one register is usually used in combination with the number in another register to point to the actual memory location where the data is stored.
There are four main types of operation code:data transfer;arithmetic; logical;branch.
Data transfer operations -These are commands that move data between the registers and main memory.Typical instructions include:move, store, load.
Arithmetic operations - These include:add, subtract, multiply and divide ,increment(increase by 1) and decrement (decrease by 1),negate (reverse the sign) logical and arithmetic shift (moving bits left or right).
Status registers record: overflow errors in calculations sign bits.
Logical shift
This is used to carry out logical statements (AND, OR and NOT) as part of conditional statements during programming.
It is used to extract the content of one bit.
Arithmetic shift
This is used to multiply or divide numbers.
Shifting all the bits one place to the left has the effect of multiplying by two.
Shifting all the bits one place to the right has the effect of dividing by two.
Logical operations
These include the functions AND, OR and NOT.
They are used to compare values.
They can be used to mask out or ignore the contents of some bits in a byte.
For example, a 16 bit code may contain op code and an operand:
0100011110010010
You want to use the op code (first byte) again but not the operand in subsequent instructions.
A 16 bit mask can be set up where 1 allows the bit through and 0 masks it out .
When the two codes are ANDed the mask 1111111100000000 would allow the op code through but mask out the operand.
Branch operations
Branching is the ability to jump to another part of the program.
Many programs are written in a linear fashion, where one command follows the next in a logical order.
However, there are many occasions when the program needs to take different routes.
The jump command can be used in assembly language to move from one command to another.
Conditional jumps: the jump takes place if a condition is met.
For example, Jump if Zero (JIZ) so JIZ reset jumps to the line with the label called reset.
Unconditional jumps (JMP): take place regardless of any conditions.
Operation (Op) code: the command to be carried out, usually shown as a mnemonic (e.g. ADD, MOV, etc).
Operands: the parts that the operation will be carried out on, they may have two parts (e.g. Acc 45 means the contents of the accumulator are moved to memory location 45).
Comments: assembly language code can be very long, so comments are used to explain what each command does as an aid to the programmer.
Addressing Modes
If data is transferred from a source register to a destination register, then this is an example of register addressing.
Immediate addressing - this is where the data apperas immediately after the op code.
Direct addressing - refers directly to a specific memory location.
Indirect addressing - uses a number inside a register( usually an index register) to point to the memory location of interest where the actual data can be found.
Indexed addressing - a number conatained in one register is usually used in combination with the number in another register to point to the actual memory location where the data is stored.
There are four main types of operation code:data transfer;arithmetic; logical;branch.
Data transfer operations -These are commands that move data between the registers and main memory.Typical instructions include:move, store, load.
Arithmetic operations - These include:add, subtract, multiply and divide ,increment(increase by 1) and decrement (decrease by 1),negate (reverse the sign) logical and arithmetic shift (moving bits left or right).
Status registers record: overflow errors in calculations sign bits.
Logical shift
This is used to carry out logical statements (AND, OR and NOT) as part of conditional statements during programming.
It is used to extract the content of one bit.
Arithmetic shift
This is used to multiply or divide numbers.
Shifting all the bits one place to the left has the effect of multiplying by two.
Shifting all the bits one place to the right has the effect of dividing by two.
Logical operations
These include the functions AND, OR and NOT.
They are used to compare values.
They can be used to mask out or ignore the contents of some bits in a byte.
For example, a 16 bit code may contain op code and an operand:
0100011110010010
You want to use the op code (first byte) again but not the operand in subsequent instructions.
A 16 bit mask can be set up where 1 allows the bit through and 0 masks it out .
When the two codes are ANDed the mask 1111111100000000 would allow the op code through but mask out the operand.
Branch operations
Branching is the ability to jump to another part of the program.
Many programs are written in a linear fashion, where one command follows the next in a logical order.
However, there are many occasions when the program needs to take different routes.
The jump command can be used in assembly language to move from one command to another.
Conditional jumps: the jump takes place if a condition is met.
For example, Jump if Zero (JIZ) so JIZ reset jumps to the line with the label called reset.
Unconditional jumps (JMP): take place regardless of any conditions.
Subscribe to:
Posts (Atom)