Design an ER diagram for an ABC IT Training Institute that will meet t he  training  needs for
individuals and employees of corporate offices. Clearly indicate the entities, relationships,
cardinality and the key constraints. The description of the environment is as follows:
The Institute offers  5 advanced courses of 3 months duration each. The Institute has 20  faculty
and can handle upto 40  trainees  per  batch.  The training will be conducted batch wise. They can
accommodate maximum 5 batches per day (2 batches in the pre-lunch session and 3 batches in
the post-lunch session). The student can register upto 2 courses simultaneously. Training
consists of theory and practicals. Theory and practicals are scheduled on alternate days. Each
batch is assigned a faculty member who takes theory sessions as  well as practical sessions.
Sunday is holiday for everyone. A test will be conducted per course every week to continuously
evaluate the performance of the student. The question paper will be set by the faculty concerned
whoever is teaching the batch. The result/grade will be declared at the end of the third month
after conducting course-end exam. 

Write an algorithm for the implementation of a Stack.

Write a note of not more than 5 pages summarizing the latest research in the area
of  “Trees”.  Refer to various journals and other online resources. Indicate them in your
assignment.

Write an algorithm that accepts a Binary Tree as input and prints the number of leaf
nodes to standard output.

Write an algorithm for the implementation of a AVL Tree.

Pointers in C language is a variable that stores/points the address of another variable. A Pointer in C is used to allocate memory dynamically i.e. at run time. The pointer variable might be belonging to any of the data type such as int, float, char, double, short etc.

Adder

An adder is a kind of calculator that is used to add two binary numbers. When I say, calculator, I don’t mean one with buttons, this one is a circuit that can be integrated with many other circuits for a wide range of applications. There are two kinds of adders;

Half adder

Full adder

Half Adder

With the help of half adder, we can design circuits that are capable of performing simple addition with the help of logic gates.

Let us first take a look at the addition of single bits.

0+0 = 0

0+1 = 1

1+0 = 1

1+1 = 10

These are the least possible single-bit combinations. But the result for 1+1 is 10. Though this problem can be solved with the help of an EXOR Gate, if you do care about the output, the sum result must be re-written as a 2-bit output.

Thus the above equations can be written as

0+0 = 00

0+1 = 01

1+0 = 01

1+1 = 10

Here the output ‘1’of ‘10’ becomes the carry-out. The result is shown in a truth-table below. ‘SUM’ is the normal output and ‘CARRY’ is the carry-out.

INPUTS                 OUTPUTS

A             B             SUM      CARRY

0              0              0              0

0              1              1              0

1              0              1              0

1              1              0              1

From the equation, it is clear that this 1-bit adder can be easily implemented with the help of EXOR Gate for the output ‘SUM’ and an AND Gate for the carry. Take a look at the implementation below.

Half Adder Circuit

For complex addition, there may be cases when you have to add two 8-bit bytes together. This can be done only with the help of full-adder logic.

Full Adder

This type of adder is a little more difficult to implement than a half-adder. The main difference between a half-adder and a full-adder is that the full-adder has three inputs and two outputs. The first two inputs are A and B and the third input is an input carry designated as CIN. When a full adder logic is designed we will be able to string eight of them together to create a byte-wide adder and cascade the carry bit from one adder to the next.

The output carry is designated as COUT and the normal output is designated as S. Take a look at the truth-table.

INPUTS                 OUTPUTS

A             B             CIN         COUT    S

0              0              0              0              0

0              0              1              0              1

0              1              0              0              1

0              1              1              1              0

1              0              0              0              1

1              0              1              1              0

1              1              0              1              0

1              1              1              1              1

From the above truth-table, the full adder logic can be implemented. We can see that the output S is an EXOR between the input A and the half-adder SUM output with B and CIN inputs. We must also note that the COUT will only be true if any of the two inputs out of the three are HIGH.

Thus, we can implement a full adder circuit with the help of two half adder circuits. The first will half adder will be used to add A and B to produce a partial Sum. The second half adder logic can be used to add CIN to the Sum produced by the first half adder to get the final S output. If any of the half adder logic produces a carry, there will be an output carry. Thus, COUT will be an OR function of the half-adder Carry outputs. Take a look at the implementation of the full adder circuit shown below.

Full Adder Circuit

Though the implementation of larger logic diagrams is possible with the above full adder logic a simpler symbol is mostly used to represent the operation. Given below is a simpler schematic representation of a one-bit full adder.

Single-bit Full Adder

With this type of symbol, we can add two bits together taking a carry from the next lower order of magnitude, and sending a carry to the next higher order of magnitude. In a computer, for a multi-bit operation, each bit must be represented by a full adder and must be added simultaneously. Thus, to add two 8-bit numbers, you will need 8 full adders which can be formed by cascading two of the 4-bit blocks. The addition of two 4-bit numbers is shown below.

Multi-Bit Addition using Full Adder

Parity bits are used as a form of error checking during the transmission of information. When old modem is transmitted data over a network or communications device, the data was encoded into a series of ones and zeros called bits (modern modems send information in packets and check for errors in different ways, so a parity bit is unnecessary). A single bit can describe only two possible states, 0 (off) or 1 (on). Several bits are thus needed to describe a letter or number. A total of seven bits are used to describe the set of ASCII characters, which include the letters and numbers that compose this document.

The letter "A", for example, has ASCII code 65, which in binary is 1000001. Note that each binary digit corresponds to a power of two, and 65, which is two to the sixth power plus two to the zeroth power, has ones in only the sixth and zeroth columns of its binary representation. The letter C, with code value 67, has the binary sequence 1000011.

Because noise or electrical interference may sometimes interfere with the transmission of data, it is useful to have some way to easily detect errors in information as it is exchanged. One way to do this is to add an eighth bit to characters that are transmitted, called a parity bit. The parity bit is chosen such that all correctly transmitted characters will have either an even or odd number of ones. Thus, if a zero were placed at the start of the code for the letter A, producing 01000001, a one would be placed before the code for C, producing 11000011.

The prefixes shown here produce binary codes with an even number of ones (and zeros), and the added bit is thus called an even parity bit. The leading ones and zeros could also be chosen to always produce odd numbers of ones and zeros, and this scheme is called odd parity. Familiar settings in communications programs are E7, which uses one even parity bit and seven data bits, and N8, which indicates no parity bit and the use of all eight bits for transmitting data.

Use of the wrong parity setting in a communications program may produce screens full of garbage characters. If this happens, check to see what parity settings the computer to which you are connecting expects. If you do not have this information, try connecting with a different parity setting and see if this produces legible text.

Opcode is an instruction that tells processor what to do with the variable or data written besides it.

Oprand is a variable that stores data(and data can be a memory address or any data that we want to process).

e.g. MVI A,B

here instruction MVI is an opcode. A & B are oprands.

Same for other instructions.

An algorithm is a finite set of steps defining the solution of a particular problem. An algorithm is expressed in pseudo code – something resembling C language or Pascal, but with some statements in English rather than within the programming language

1. A sequential solution of any program that written in human language, called algorithm.
2. Algorithm is first step of the solution process, after the analysis of problem, programmers write the algorithm of that problem.

Pseudo code 

• Input Num
• Initialize Len to zero and Y to Num
• While Y is not zero
•                Save Remainder by Y Mod 16 in array HEXD at index Len
•                Initialize Y to Y divided 16
•                Increment Len
• for(Initialize I to Len-1 ; Condition I Greater than  -1 ;  Decrement I )
•                If HEXD[I] Less than 10
•                           HEXC[I]=HEXD[I]+48
•                Else
•                           HEXC[I]=HEXD[I]+55
• Initialize HEXC[I] to NULL
• Print HEXC

Detailed Algorithm:

Step 1:  Input NUM

Step 2:  LEN = 0 & Y=NUM

Step 3:  While (Y > 0)

                       HEXD[LEN]=Y%16

                       Y=Y/16

                       LEN++

Step 4: for(I=LEN-1;I>-1;I–)

                       IF(HEXD[I]<10)

                                HEXC[I]=HEXD[I]+48;

                       ELSE

                                HEXC[I]=HEXD[I]+55;

Step 5:  HEXC[I]=NULL

Step 5:  Print HEXC

Flowchart:-