Binary Trees Summary

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.

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+

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

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.

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

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.

PHP and MySql

Today in class we created a simple database using XAMPP and MySql:


To display information from the table on web browser we used html code with php embedded in it. Using our memory sticks as a web server and the URL http://localhost/ we were able to display the information we wanted displayed.

Web Browser

We selected to display the products in bullet point form from our database.

Code

As you can see this looks like an ordinary html document but if you notice is also has <?php.....?>. This shows php is being used.

More PHP

Here is a mind map of some of the things i have learned about PHP:

PHP

PHP stands for PreHypertext processor
PHP is a server-side scripting language, like ASP
PHP scripts are executed on the server
PHP supports many databases (MySQL, Informix, Oracle, Sybase, Solid, PostgreSQL, Generic ODBC, etc.)
PHP is an open source software (OSS)
We downloaded XAMPP and and installed in on our memory sticks. We are going to use this for our coursework.

Binary

Task23

A two byte floating point numbering system uses 10 places for the mantissa and 6 for the exponent. Convert the number 1010 1100 0000 0011 into decimal by filling in the following:
Step1:The number is negative. I know that because the left most bit is a one.
Step2:The Mantissa is: 1.010110000
Step3:The mantissa converted into a negative binary number that is not in 2s complement form is: -(0101.010000)
Step4:The exponent is : 000011 = 3
Step5:The decimal point in the mantissa must now be moved 3 places to the right.
Step6:The mantissa is now -(101.01)
Step7:Converting to denary :-5.25

Binary

Task 14

A two byte floating-point numbering system uses 10 places for the mantissa and 6 for the exponent. Convert the number 0111 1010 0000 0101 into decimal by filling in the following:
STEP 1: This number is positive. I know this because the left most bit is a zero.
STEP 2: The mantissa is: 0.11101000
STEP 3: The exponent is 000101 which is positive because left most bit is a zero.
STEP 4: The denary equivalent of 000101 is 3
STEP 5: The decimal place in the mantissa must be moved right because the denary value is positive
STEP 6: The mantissa now looks like this 0111.101000
STEP 7: Removing the redundant zeros the mantissa now looks like this 111.101
STEP 8: The final denary answer is 7.625

Binary

Task8

Convert these fixed-point numbers into denary fractions:
(a)01111100 =15.5
(b)00000100 =0.5
(c)11000001 =24.125

Binary Floating Point Representation

Task 1

Suppose you had 3 bits to represent 2s complement numbers
(a)What is the weighting of each bit? -4, 2, 1
(b)What is the largest number that can be represented? 3
(c)What is the smallest number? -4

Basic html

Frames

With frames, you can display more than one HTML document in the same browser window. Each HTML document is called a frame, and each frame is independent of the others.
The disadvantages of using frames are:
The web developer must keep track of more HTML documents
It is difficult to print the entire page

The Frameset Tag

The frameset tag defines how to divide the window into frames
Each frameset defines a set of rows or columns
The values of the rows/columns indicate the amount of screen area each row/column will occupy

Above is the code used to obtain seperate frames.

Here is an example of 2 different frames below at 25% and 75%.

Links

An anchor can be used in two ways:
To create a link to another document by using the href attribute
To create a bookmark inside a document, by using the name or id attribute
An anchor can point to any resource on the Web: an HTML page, an image, a sound file, a movie, etc.
The anchor tag is used to create an anchor to link from, the href attribute is used to address the document to link to, and the words between the open and close of the anchor tag will be displayed as a hyperlink.
Here is an example of how a link can be created in notepad++:

Learning html

I was using the W3schools website to learn about html. Through the use of various tags you can view text in an internet browser as shown.






Here is the coding for the example:

Various tags are used with html.
The use of the "<" and ">" signs indicate a tag.

Class Today

Today we looked at the w3School website. We are learning to use html and are using notepad++ to enhance our skills.

A2 Computing

Blog created for A2 computing.