CS-IT Lecture Notes

Lesson10

2009-09-01T16:50:00.001-07:00

COE 512 – Computer Systems Architecture

Compiled by: Engr. Guilbert Nicanor A. Atillo

Lesson 10 – Operating System - Important Theory

Operating Systems - Some Theory

Introduction

In Chapter 8 we saw how the operation - in the sense of `driving' them - of computers evolved through users operating them, to operators, and finally through various sophistications of operating system software to timesharing operating systems.

First, we give a demonstration of the effect of multiprogramming.

Figures 9.1 and 9.2 shows the execution of three identical jobs, under two different operating system regimes.

Assume that the jobs/processes/programs are in memory to start with, that they do some computation (taking 10 millisec) which results in the requirement to read a particular record from a disk file (taking 10 millisec), finally they do some more computation (again 10 millisec). Viewed as executions of single programs this may not appear too useful - where do the results go to - but, in fact, the jobs are quite typical of what would be encountered by a timesharing during the execution lifetime of three processes

Figure 9.1 shows how the jobs would have to run on a single user system like MS-DOS. The computer is I/O blocked during each disk input - regardless of whether the input is by polled I/O, interrupts, or DMA.

Figure 9.2 shows the effect of multiprogramming; when one process become I/O bound, the CPU can do processing for another. Thus, a 90 millisec of computer usage can be reduced to 60; add more jobs and you get a greater increase in efficiency. NB. in this case, you are concerned with the method of I/O transfer - ideally the CPU asks for the data, and receives an interrupt when they are placed in memory.

Figure 9.1: Illustration of multiprocessing (a) single user

\...
...ng on CPU
ooooo waiting for I/O\end{verbatim}\end{tex2html_preform}\end{figure}" border="0" height="112" width="469">

Figure 9.2: Illustration of multiprocessing (b) multiprogrammed

... for I/O
...... waiting for CPU\end{verbatim}\end{tex2html_preform}\end{figure}" border="0" height="243" width="538">

The work that a modern timesharing operating system performs is a good deal more complex than that of, for example, a simple resident monitor - or even a single user OS like MS-DOS. Nevertheless, like all complex systems, the analysis of operating systems responds to breaking them into subsystems/components.

The following functions are required:

1. Dispatching or scheduling. Switching the processor from one process to another; allowing jobs to enter queue.

2. Interrupt handling.

3. Resource allocation. Allocation of the computer's resources to processes: memory, I/O devices, CPU time.

4. Resource protection. Ensuring that no process can access any resource which has not been allocated to it.

5. Provision of (virtual) I/O and other services.

6. Provision of a file system - to processes, and to human users.

7. Analysing and decoding user commands - and requests from programs, and converting these into procedure and program names.

The functions that meet these requirements, and the relationships between them are sometimes shown as a so-called onion-skin diagram; this concept of layers of skin is closely related to that of levels of abstraction given in chapter 8.

We shall now briefly look at a selection of topics that pertain to these requirements.

Processes

General

The concept of a process is central - first used by MULTICS. Sometimes referred to as a task. Definition can be difficult: `a program in execution' may be the best.

During its life, a process goes through a series of discrete states:

Running - if it currently has the CPU resource;
Ready - if it could use the CPU if the CPU were available;
Blocked - if it is waiting for some event to happen before it can proceed.

When a job is admitted to the system, a corresponding process is created and placed at the back of the queue and it is marked ready; alternatively, there may be separate queues. It gradually moves to the top of the ready list - see scheduling/dispatching below; when the CPU becomes available the process makes a state transition from ready to running. Strictly speaking this is dispatching.

To prevent any one process, say process A, monopolising the system - i.e. to provide time-sharing it must be possible possible to stop the process after it has consumed its allocated amount of CPU time. This is done via an interrupting clock (hardware) which allows a specified time quantum - a time-slot to pass; if process A is still using the CPU the clock generates an interrupt, causing the system to regain control. Process A now makes the state transition back to ready, i.e. A is put back in the ready queue.

The next process, process B, say, on the ready queue is now put into the running state; and so on ....

If a running process initiates an I/O operation before its time-slot expires then the process is forced to release the CPU; it enters the blocked state and releases the CPU.

If a process is in the blocked state and the event for which it is waiting completes, then the process makes the transition from blocked to ready. The four state transitions are shown in Figure 9.3

Figure 9.3: Process State Transitions: a Process can be running, blocked, or ready

\hbox{
\psfig{figure=process.eps}
}}
\end{figure}" border="0" height="211" width="500">

Process Control Block (PCB)

Because of this `switching on and off' of processes is is necessary to have housekeeping information associated with each process. A process control block PCB which is a record containing important current information about the process, for example: current state of the process, unique identification of the process, the process's priority, open files & I/O devices, use of main memory and backing store, other resources held, a register save area (see chapter 7).

The Kernel

All of the operations involving processes are controlled by a portion of the OS called its nucleus, core or kernel. The kernel represents only a small portion of the code of the entire OS but it is intensively used and so remains in primary storage while other portions may be transferred in and out of secondary storage as required.

One very important function of the kernel is interrupt processing. In large multi-user systems, the kernel is subjected to a constant barrage of interrupts. Clearly, rapid response is essential: to keep resources well utilised, and to provide acceptable response times for interactive users.

In addition, while dealing with an interrupt, the kernel disables other interrupts. Thus, to prevent interrupts being disabled for long periods of time, the kernel is designed to do the minimum amount of processing possible on each interrupt and to pass the remaining processing to an appropriate system process.

The kernel of a sophisticated OS may contain code to perform:

interrupt handling;
process creation & destruction;
process state switching and dispatching;
inter process communication;
manipulation of PCB;
support of I/O activities;
support of memory allocation & deallocation;
support of the file system;
support of system accounting functions.

Supporting hardware and microcode is often provided - even for portable operating systems like UNIX.

The kernel has privileges that allow it to do things that normal processes cannot do, e.g. access I/O devices. Privilege is usually conferred by the processor state, i.e. privilege level is stored in hardware, so a process has a different processor state from the kernel. In the original Intel 8086/88 and 80286, there was limited support for processor states; however, in the 80386 and after, full time-sharing was supported.

Scheduling

The goal of scheduling (the method by which processor time is managed) is to provide good service to all the processes that are currently competing for resources, including the CPU.

Three type of scheduling may be identified: long term scheduling, medium term scheduling, and short term scheduling.

We will be concerned only with short-term scheduling - also called dispatching, which decides how to share the computer among all the processes that currently want to compute. Such decisions may be made frequently - tens of times per second.

There are several competing goals that scheduling policies aim to fulfill - one is good throughput. For short term scheduling, this minimizes the number of process switches. Another goal is good (quick) service.

Scheduling Objectives

Some of the - often conflicting - objectives of a good scheduling algorithm/policy are:

1. Be fair - all processes should be treated equitably;

2. Maximize throughput and service, i.e. as many processes as possible per unit time;

3. Maximize the number of interactive users receiving acceptable response times;

4. Be predictable - a given job should run in about the same amount of time regardless of the load on the system;

5. Balance resource use - processes using underutilized resources should be favoured;

6. Achieve a balance between response and utilization;

7. Avoid indefinite postponement - as a process waits for a resource its priority should grow (aging);

8. Enforce priorities;

9. Give preference to processes holding key resources;

10. Give better service to processes exhibiting desirable behaviour e.g. low paging rates - see below;

11. Degrade gracefully under heavy loads.

Thus, scheduling may appear to be a complex problem.

Scheduling Policies, Algorithms

First Come, First Served (FCFS)

Under FCFS, the short term scheduler runs each process until it either terminates or leaves because of I/O or resource requests. Processes arriving wait in the order that they arrive.

FCFS is non-preemptive, so a process is never blocked once it has started to run until it leaves the domain of the short term scheduler.

FCFS is usually unsatisfactory because of the way that it favours long (greedy) processes - like the person in the bank queue in front of you with the weeks takings from a shop!

Round Robin (RR)

The intention is to provide good response ratios for short as well as long processes. This policy services (allocates CPU to) a process for a single time slot (length = q), where q = between 1/60 and 1 second; if the process is not finished it is interrupted at the end of the slot and placed at the rear of the ready queue & will wait for its turn again. New arrivals enter the ready queue at the rear.

RR can be tuned by adjusting q. If q is so high that it exceeds the service requirements for all processes, RR becomes the same as FCFS. As q tends to 0, process switching happens more frequently and eventually occupies all available time. Thus q should be set small enough so that RR is fair but high enough so that the amount of time spent switching processes is reasonable.

RR is preemptive, i.e. it will stop a process, if the process has not completed before the end of its time-slot.

Shortest Process Next (SPN)

SPN (like FCFS) is non-preemptive. It tries to improve response for short processes over FCFS. But, it requires explicit information about the service time requirements for each process. The process with the shortest time requirement is chosen.

Unfortunately, long processes wait a long time or suffer starvation. Short processes are treated very favourably.

Conclusion

Preemption is worth the extra switching cost. Since context must switch at every interrupt from the running process back to the kernel, it does not usually cost much extra for the kernel to make a decision and allow a different process to run.
The time-slot should be large enough so that preemption cost does not become excessive, e.g.. if a process switch costs 100 microseconds, the quantum should be about 100 times as long.
Some policies are more expensive than others to implement. FCFS only requires a queue for the ready list.
Many OSs use a hybrid policy, with RR for short processes and some other method for long.
Space management affects scheduling. Processes that need a substantial amount of memory are often given larger time-slots so that they can get more work done while they are occupying main store.

Memory Management

Figure 9.4 shows a five level storage organisation.

Figure 9.4: Five Levels of Memory/Storage.

...---------+---------------------+\end{verbatim}\end{tex2html_preform}\end{figure}" border="0" height="284" width="521">

Data that is currently accessed most frequently should be in the highest level of storage hierarchy. Each offers about an order of magnitude faster access than its lower neighbour.

The relationship between each layer and the one below it can be considered as similar to that between cache and main memory - cache explained during tutorial or see a textbook. If we need to cache an item from a higher level then access is significantly slower. We call such a situation a cache miss. In contrast a cache hit is when we find the data we need in a cache and need not turn to the associated slower memory.

Physical and Virtual Store

The OS must arrange main memory so that processes remain ignorant of each other and still share main memory. A guiding principle is that the more frequently data are accessed, the faster the access should be. If swapping in and out of main storage becomes the dominant activity, then we refer to this situation as thrashing.

Physical store is the hardware memory on the machine, usually starting at physical address 0. Certain locations may be reserved for special purposes; the kernel may reside in in the low addresses. The rest of physical store may be partitioned into pieces for the processes in the ready list.

Each process has its own virtual memory - the memory perceived by the process. As far as the process is concerned all address references refer to virtual space. Each process' virtual memory is limited only by the machine address size.

Note: Virtual memory can also be very useful even in a single user system - if the computer has a larger address space than physical memory, and if programs need a large amount of memory; compare overlaying - in which the programmer takes responsibility for segmenting the program into memory sized chunks.

Cache Memory

The following, from [Tanenbaum, 1999], pages 65-67, gives a nice explanation of cache memory; cache memory is a small amount of fast memory near the CPU which in many cases mitigates the difficulties caused by the slow(ish) speed of main memory and by the bottleneck of MAR, MBR (see chapter 5). The basic principles employed in paging, see section 9.9, apply to caching.

Insert p. 65 here.

!Insert pp. 66, 67 here

Paging

Principle

The most common virtual storage technique is paging. Paging is designed to be transparent to the process - like all virtual memory.

The program and data of each process are regarded - by the OS as being partitioned into a number of pages of equal size. The computer's physical memory is similarly divided into a number of page frames. Page frames are allocated among processes by the OS At any time, each process will have a few pages in memory, while the remainder is in secondary memory.

The real point behind paging is that, whenever a process needs to access a location that is within a page that is in secondary memory, the page is fetched, invisibly to the process, and the access takes place, almost as if the datum had already been in memory. Thus, the process thinks that it has ALL of its virtual memory in main memory.

The remainder of this discussion can now proceed as if we are only concerned with a single process, which happens to be using a bigger virtual memory than can fit in main, physical, memory; ie. what is said is applicable to single user systems as well as multi-user. In addition, we shall simplify the arithmetic by assuming a page size size of 1000 - simpler for decimal oriented humans.

The process's virtual memory is divided into pages. Page 0 refers to locations 0 to 999, page 1: 1000 to 1999, and so on, ...

The CPU must transform from virtual address to physical address:

1. Calculate:

(a)

Virtual page number, i.e. address/1000;

(b)

Offset within that page, i.e. remainder after address/1000.

2. Calculate which page frame - physical page -, if any, that the virtual page occupies; this involves the use of a lookup table, the page table which links virtual pages with page frames e.g. Figure 9.5.

Figure 9.5: Page Table

Process Page Pa...
...
----------- ------------- ----\end{verbatim}\end{tex2html_preform}\end{figure}" border="0" height="159" width="279">

The third column - Secondary Store address - indicates where the OS must read/write if a page is to be transferred in/out of memory.

If the process needs a page which is not in memory - marked by a -1, for example-- a page fault is generated, and the OS sets about reading the required page into main memory. Obviously, some other page will have to be removed, to make space for the new page.

The whole paging process is illustrated by the pseudo-code in Figure 9.6. Think of PagedVirtualMemory being used in the situation where you have a PC with 32-bit addressing - 2 Gigabytes of virtual memory) but only 2K of physical memory available for data - forget about instructions for this example. Imagine that you want to use a 60K array of bytes. You use PagedVirtualMemory to access the array; the function hides all the hassle of address translation and paging.

Figure 9.6: Paging

...return byte at aa; //i.e. M[aa]}\end{verbatim}\end{tex2html_preform}\end{figure}" border="0" height="442" width="466">

Choice of Page Size

The choice of page size determined at the design stage is a trade- off between various considerations:

Overhead space - least with large pages, since page tables have fewer entries.
Internal waste - smallest with small pages.
Cold start faults - lower with large pages. These are the faults needed to bring the program into main store the first time. With larger pages there are fewer total pages, hence fewer cold start faults.
Page fault rate - generally lower with small pages, assuming that a fixed amount of main store is available.
Efficiency of transfer between main memory and disk store - best with large pages, since they take about the same amount of time to transfer as small pages.

Larger pages are usually better, unless they become so large that too few processes in the ready list can have pages in main store at the same time. Common page sizes are from 512 bytes to 4K bytes but can be as large as 8K.

Page Replacement Policies

The storage manager must decide to keep some pages in main store and other pages in secondary store - unless virtual space requirements are less than the available physical space.

These decisions may be made at any time but when a page fault occurs a decision must be made; the process that suffered the page fault cannot continue until the appropriate page is swapped in.

A page replacement policy (PRP)/algorithm is used to decide which page frame to vacate ie. swap out its page.

Some commonly quoted strategies are:

Note: pages being heavily used should be preserved. One goal is to minimize the number of page faults. Swapping can reach a level at which all processes present need to swap so no progress can be made. If this persists, the OS is spending all its time transferring pages in and out of main store - known as thrashing.

First in, First out (FIFO)

Also called longest resident.

When a page frame is needed, the page that has been in main store for the longest time is chosen. This policy tends to save recently used pages which have a higher probability of being used again soon. However a frequently used page still gets swapped out when it gets to be old enough, even though it will have to be brought in immediately.

Least Recently Used (LRU)

This method is based on the assumption that the page reference pattern in the recent past is a mirror of the pattern in the near future. Pages that have been accessed recently are likely to continue to be accessed and ought to be kept in main store. It is expensive to implement exactly since in order to find the page least recently used, either a list of pages must be maintained in use order or each page must be marked with the time it was last accessed.

Review Questions:

Explain interrupts and traps, and provide a detailed account of the procedure that an operating system handles an interrupt.
What is the supervisor or kernel mode? What is the user mode? What are the differences? Why are they needed?
Define the meaning of mechanism and policy in the separation of mechanism and policy principle.
Most modern operating systems provide support for both processes and threads. Define process and thread. List two key differences and similarities between process and thread.
For each of the following pairs of terms, define each term, making sure to clarify the key difference(s) between the two terms.

(a) “application software” and “system software”

(b) “user mode” and “kernel mode”

(d) “text segment” and “data segment”

(e) “short-term scheduler” and “long-term scheduler”

(f) “waiting time” and “service time”

RESEARCH Problem:

Compare at least 20 commands for the following: DOS, WINDOWS, LINUX, UBUNTU,and

UNIX. A sample output is shown below. Please pass your hardcopy output on September 14, 2009.

Example:

DOS

WINDOWS

UNIX

LINUX

UBUNTU

Copy - this command can be used both to copy files from disk to disk or to create a second copy of a file on a single disk.

Ex. C> copy a:brazil1.dat b:\south\brazil2.dat

copy source [destination]

copy d:\i386\atapi.sy_ c:\windows\atapi.sys

cp firstfile secondfile

$ cp stuff stuff.bak

cp file_name/folder_name

Lesson 1

2009-06-18T05:04:00.001-07:00

LESSON 1

BASIC CONCEPTS

1.1 INTRODUCTION

Let us begin with the word ‘compute’. It means ‘to calculate’. We all are familiar with calculations in our day to day life. We apply mathematical operations like addition, subtraction, multiplication, etc. and many other formulae for calculations. Simpler calculations take less time. But complex calculations take much longer time. Another factor is accuracy in calculations. So man explored with the idea to develop a machine which can perform this type of arithmetic calculation faster and with full accuracy. This gave birth to a device or machine called ‘computer’.

The computer we see today is quite different from the one made in the beginning. The number of applications of a computer has increased, the speed and accuracy of calculation has increased. You must appreciate the impact of computers in our day to day life. Reservation of tickets in Air Lines and Railways, payment of telephone and electricity bills, deposits and withdrawals of money from banks, business data processing, medical diagnosis, weather forecasting, etc. are some of the areas where computer has become extremely useful.

However, there is one limitation of the computer. Human beings do calculations on their own. But computer is a dumb machine and it has to be given proper instructions to carry out its calculation. This is why we should know how a computer works.

1.2 OBJECTIVES

After going through this lesson you will be in a position to

define a computer
identify characteristics of computer
know the origin and evolution of computer
identify capability of computer in terms of speed and accuracy
distinguish computer from human beings and calculator
identify the role of computer
appreciate the evolution of computer through five generations

1.3 WHAT IS A COMPUTER?

Computer is an electronic device. As mentioned in the introduction it can do arithmetic calculations faster. But as you will see later it does much more than that. It can be compared to a magic box, which serves different purpose to different people. For a common man computer is simply a calculator, which works automatic and quite fast. For a person who knows much about it, computer is a machine capable of solving problems and manipulating data. It accepts data, processes the data by doing some mathematical and logical operations and gives us the desired output.

Therefore, we may define computer as a device that transforms data. Data can be anything like marks obtained by you in various subjects. It can also be name, age, sex, weight, height, etc. of all the students in your class or income, savings, investments, etc., of a country. Computer can be defined in terms of its functions. It can i) accept data ii) store data, iii) process data as desired, and iv) retrieve the stored data as and when required and v) print the result in desired format. You will know more about these functions as you go through the later lessons.

1.4 CHARACTERISTICS OF COMPUTER

Let us identify the major characteristics of computer. These can be discussed under the headings of speed, accuracy, diligence, versatility and memory.

1.4.1 Speed

As you know computer can work very fast. It takes only few seconds for calculations that we take hours to complete. Suppose you are asked to calculate the average monthly income of one thousand persons in your neighborhood. For this you have to add income from all sources for all persons on a day to day basis and find out the average for each one of them. How long will it take for you to do this? One day, two days or one week? Do you know your small computer can finish this work in few seconds? The weather forecasting that you see every day on TV is the results of compilation and analysis of huge amount of data on temperature, humidity, pressure, etc. of various places on computers. It takes few minutes for the computer to process this huge amount of data and give the result.

You will be surprised to know that computer can perform millions (1,000,000) of instructions and even more per second. Therefore, we determine the speed of computer in terms of microsecond (10-6 part of a second) or nano-second (10-9 part of a second). From this you can imagine how fast your computer performs work.

1.4.2 Accuracy

Suppose some one calculates faster but commits a lot of errors in computing. Such result is useless. There is another aspect. Suppose you want to divide 15 by 7. You may work out up to 2 decimal places and say the dividend is 2.14. I may calculate up to 4 decimal places and say that the result is 2.1428. Some one else may go up to 9 decimal places and say the result is 2.142857143. Hence, in addition to speed, the computer should have accuracy or correctness in computing.

The degree of accuracy of computer is very high and every calculation is performed with the same accuracy. The accuracy level is determined on the basis of design of computer. The errors in computer are due to human and inaccurate data.

1.4.3 Diligence

A computer is free from tiredness, lack of concentration, fatigue, etc. It can work for hours without creating any error. If millions of calculations are to be performed, a computer will perform every calculation with the same accuracy. Due to this capability it overpowers human being in routine type of work.

1.4.4 Versatility

It means the capacity to perform completely different type of work. You may use your computer to prepare payroll slips. Next moment you may use it for inventory management or to prepare electric bills.

1.4.5 Power of Remembering

Computer has the power of storing any amount of information or data. Any information can be stored and recalled as long as you require it, for any numbers of years. It depends entirely upon you how much data you want to store in a computer and when to lose or retrieve these data.

1.4.6 No IQ

Computer is a dumb machine and it cannot do any work without instruction from the user. It performs the instructions at tremendous speed and with accuracy. It is you to decide what you want to do and in what sequence. So a computer cannot take its own decision as you can.

1.4.7 No Feeling

It does not have feelings or emotion, taste, knowledge and experience. Thus it does not get tired even after long hours of work. It does not distinguish between users.

1.4.8 Storage

The Computer has an in-built memory where it can store a large amount of data. You can also store data in secondary storage devices such as floppies, which can be kept outside your computer and can be carried to other computers.

IN-TEXT QUESTIONS 1.1

1. What is a computer? Why is it known as data processor?

2. What are the important characteristics of computer?

1.5 HISTORY OF COMPUTER

History of computer could be traced back to the effort of man to count large numbers. This process of counting of large numbers generated various systems of numeration like Babylonian system of numeration, Greek system of numeration, Roman system of numeration and Indian system of numeration. Out of these the Indian system of numeration has been accepted universally. It is the basis of modern decimal system of numeration (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Later you will know how the computer solves all calculations based on decimal system. But you will be surprised to know that the computer does not understand the decimal system and uses binary system of numeration for processing.

We will briefly discuss some of the path-breaking inventions in the field of computing devices.

1.5 .1 Calculating Machines

It took over generations for early man to build mechanical devices for counting large numbers. The first calculating device called ABACUS was developed by the Egyptian and Chinese people.

The word ABACUS means calculating board. It consisted of sticks in horizontal positions on which were inserted sets of pebbles. A modern form of ABACUS is given in Fig. 1.2. It has a number of horizontal bars each having ten beads. Horizontal bars represent units, tens, hundreds, etc.

1.5.2 Napier’s bones

English mathematician John Napier built a mechanical device for the purpose of multiplication in 1617 A D. The device was known as Napier’s bones.

1.5.3 Slide Rule

English mathematician Edmund Gunter developed the slide rule. This machine could perform operations like addition, subtraction, multiplication, and division. It was widely used in Europe in 16th century.

1.5.4 Pascal's Adding and Subtractory Machine

You might have heard the name of Blaise Pascal. He developed a machine at the age of 19 that could add and subtract. The machine consisted of wheels, gears and cylinders.

1.5.5 Leibniz’s Multiplication and Dividing Machine

The German philosopher and mathematician Gottfried Leibniz built around 1673 a mechanical device that could both multiply and divide.

1.5.6 Babbage’s Analytical Engine

It was in the year 1823 that a famous English man Charles Babbage built a mechanical machine to do complex mathematical calculations. It was called difference engine. Later he developed a general-purpose calculating machine called analytical engine. You should know that Charles Babbage is called the father of computer.

1.5.7 Mechanical and Electrical Calculator

In the beginning of 19th century the mechanical calculator was developed to perform all sorts of mathematical calculations. Up to the 1960s it was widely used. Later the rotating part of mechanical calculator was replaced by electric motor. So it was called the electrical calculator.

1.5.8 Modern Electronic Calculator

The electronic calculator used in 1960 s was run with electron tubes, which was quite bulky. Later it was replaced with transistors and as a result the size of calculators became too small.

The modern electronic calculator can compute all kinds of mathematical computations and mathematical functions. It can also be used to store some data permanently. Some calculators have in-built programs to perform some complicated calculations.

IN-TEXT QUESTIONS 1.2

1. What is the first mathematical device built and when was it built?

2. Who is called the father of Computer Technology.

1.6 COMPUTER GENERATIONS

You know that the evolution of computer started from 16th century and resulted in the form that we see today. The present day computer, however, has also undergone rapid change during the last fifty years. This period, during which the evolution of computer took place, can be divided into five distinct phases known as Generations of Computers. Each phase is distinguished from others on the basis of the type of switching circuits used.

1.6.1 First Generation Computers

First generation computers used Thermion valves. These computers were large in size and writing programs on them was

difficult. Some of the computers of this generation were:

ENIAC: It was the first electronic computer built in 1946 at University of Pennsylvania, USA by John Eckert and John Mauchy. It was named Electronic Numerical Integrator and Calculator (ENIAC). The ENIAC was 30_ 50 feet long, weighed 30 tons, contained 18,000 vacuum tubes, 70,000 registers, 10,000 capacitors and required 150,000 watts of electricity. Today your favorite computer is many times as powerful as ENIAC, still size is very small.

EDVAC: It stands for Electronic Discrete Variable Automatic Computer and was developed in 1950. The concept of storing data and instructions inside the computer was introduced here. This allowed much faster operation since the computer had rapid access to both data and instructions. The other advantages of storing instruction was that computer could do logical decision

internally.

Other Important Computers of First Generation

EDSAC: It stands for Electronic Delay Storage Automatic Computer and was developed by M.V. Wilkes at Cambridge University in 1949.

UNIVAC-1: Ecker and Mauchly produced it in 1951 by Universal Accounting Computer setup.

Limitations of First Generation Computer

Followings are the major drawbacks of First generation computers.

1. The operating speed was quite slow.

2. Power consumption was very high.

3. It required large space for installation.

4. The programming capability was quite low.

1.6.2 Second Generation Computers

Around 1955 a device called Transistor replaced the bulky electric tubes in the first generation computer. Transistors are smaller than electric tubes and have higher operating speed. They have no filament and require no heating. Manufacturing cost was also very low. Thus the size of the computer got reduced considerably.

It is in the second generation that the concept of Central Processing Unit (CPU), memory, programming language and input and output units were developed. The programming languages such as COBOL, FORTRAN were developed during this period. Some of the computers of the Second Generation were

1. IBM 1620: Its size was smaller as compared to First Generation computers and mostly used for scientific purpose.

2. IBM 1401: Its size was small to medium and used for business applications.

3. CDC 3600: Its size was large and is used for scientific purposes.

1.6.3 Third Generation Computers

The third generation computers were introduced in 1964. They used Integrated Circuits (ICs). These ICs are popularly known as Chips. A single IC has many transistors, registers and capacitors built on a single thin slice of silicon. So it is quite obvious that the size of the computer got further reduced. Some of the computers developed during this period were IBM-360, ICL-1900, IBM-370, and VAX-750. Higher level language such as BASIC (Beginners All purpose Symbolic Instruction Code) was developed during this period.

Computers of this generations were small in size, low cost, large memory and processing speed is very high.

1.6.4 Fourth Generation Computers

The present day computers that you see today are the fourth generation computers that started around 1975. It uses large scale Integrated Circuits (LSIC) built on a single silicon chip called microprocessors. Due to the development of microprocessor it is possible to place computer’s central processing unit (CPU) on single chip. These computers are called microcomputers. Later very large scale Integrated Circuits (VLSIC) replaced LSICs.

Thus the computer which was occupying a very large room in earlier days can now be placed on a table. The personal computer (PC) that you see in your school is a Fourth Generation Computer.

1.6.5 Fifth Generation Computer

The computers of 1990s are said to be Fifth Generation computers. The speed is extremely high in fifth generation computer. Apart from this it can perform parallel processing. The concept of Artificial intelligence has been introduced to allow the computer to take its own decision. It is still in a developmental stage.

1.7 TYPES OF COMPUTERS

Now let us discuss the varieties of computers that we see today. Although they belong to the fifth generation they can be divided into different categories depending upon the size, efficiency, memory and number of users. Broadly they can be divided it to the following categories.

1. Microcomputer: Microcomputer is at the lowest end of the computer range in terms of speed and storage capacity. Its CPU is a microprocessor. The first microcomputers were built of 8-bit microprocessor chips. The most common application of personal computers (PC) is in this category. The PC supports a number of input and output devices. An improvement of 8-bit chip is 16-bit and 32-bit chips. Examples of microcomputer are IBM PC, PC-AT .

2. Mini Computer: This is designed to support more than one user at a time. It possesses large storage capacity and operates at a higher speed. The mini computer is used in multi-user system in which various users can work at the same time. This type of computer is generally used for processing large volume of data in an organisation. They are also used as servers in Local Area Networks (LAN).

3. Mainframes: These types of computers are generally 32-bit microprocessors. They operate at very high speed, have very large storage capacity and can handle the work load of many users. They are generally used in centralised databases. They are also used as controlling nodes in Wide Area Networks (WAN). Example of mainframes are DEC, ICL and IBM 3000 series.

4. Supercomputer: They are the fastest and most expensive machines. They have high processing speed compared to other computers. They have also multiprocessing technique. One of the ways in which supercomputers are built is by interconnecting hundreds of microprocessors. Supercomputers are mainly being used for whether forecasting, biomedical research, remote sensing, aircraft design and other areas of science and technology. Examples of supercomputers are CRAY YMP, CRAY2, NEC SX-3, CRAY XMP and PARAM from India.

IN-TEXT QUESTIONS 3

1. Into how many generations the evolution of computer is divided?

2. What is VLSIC?

3. The personal computer that you see today is in which generation of computer?

1.8 WHAT YOU HAVE LEARNT

In this lesson we have discussed about the major characteristics of computer. The speed, accuracy, memory and versatility are some of the features associated with a computer. But the computer that we see today has not developed over night. It has taken centuries of human effort to see the computer in its present form today. There are five generations of computer. Over these generations the physical size of computer has decreased, but on the other hand the processing speed of computer has improved

tremendously. We also discussed about the varieties of computers available today.

1.9 TERMINAL QUESTIONS

1. Why is computer known as data processor?

2. Explain in brief the various generations in computer technology?

3. Write a short note on Fifth Generation of computer. What makes it different from Fourth generation computer?

4. Why did the size of computer get reduced in third generation computer?

5. Give short notes on the following

(a) Versatility (b) Storage (c) Slide Rule (d) Babbage’s Analytical Engine

6. Distinguish between Microcomputer and Mainframe computer.

1.10 FEEDBACK TO IN-TEXT QUESTIONS

IN-TEXT QUESTIONS 1

1. A computer is an electronic device, which is used to accept, store, retrieve and process the data. It is called as data processor because it is mainly used for processing data for producing meaningful information.

2. The characteristics of computer are speed, accuracy, diligence, versatility and storage.

IN-TEXT QUESTIONS 2

1. Analytical engine, 1823.

2. Charles Babbage

IN-TEXT QUESTIONS 3

1. Five generations

2. Very Large Scale Integrated Circuits

3. Fourth Generation

1.11 TERMINAL QUESTIONS

1. Explain various types of computers.

2. Explain in brief the various generations in computer technology.

3. Write a short note on Fifth Generation of computer. What makes it different from Fourth Generation computer?

4. Why did the size of computer get reduced in Third Generation computer?

LESSON 2

COMPUTER ORGANISATION

2.1 INTRODUCTION

In the previous lesson we discussed about the evolution of computer. In this lesson we will provide you with an overview of the basic design of a computer. You will know how different parts of a computer are organised and how various operations are performed between different parts to do a specific task. As you know from the previous lesson the internal architecture of computer may differ from system to system, but the basic organisation remains the same for all computer systems.

2.2 OBJECTIVES

At the end of the lesson you will be able to:

understand basic organisation of computer system

understand the meaning of Arithmetic Logical Unit, Control Unit and Central Processing Unit

differentiate between bit , byte and a word

define computer memory

differentiate between primary memory and secondary memory

differentiate between primary storage and secondary storage units

differentiate between input devices and output devices

2.3 BASIC COMPUTER OPERATIONS

A computer as shown in Fig. 2.1 performs basically five major operations or functions irrespective of their size and make. These are 1) it accepts data or instructions by way of input, 2) it stores data, 3) it can process data as required by the user, 4) it gives results in the form of output, and 5) it controls all operations inside a computer. We discuss below each of these operations.

1. Input: This is the process of entering data and programs in to the computer system. You should know that computer is an electronic machine like any other machine which takes as inputs raw data and performs some processing giving out processed data. Therefore, the input unit takes data from us to the computer in an organized manner for processing.

Fig. 2.1 Basic computer Operations

2. Storage: The process of saving data and instructions permanently is known as storage. Data has to be fed into the system before the actual processing starts. It is because the processing speed of Central Processing Unit (CPU) is so fast that the data has to be provided to CPU with the same speed. Therefore the data is first stored in the storage unit for faster access and processing. This storage unit or the primary storage of the computer system is designed to do the above functionality. It provides space for storing data and instructions.

The storage unit performs the following major functions:

All data and instructions are stored here before and after processing.

Intermediate results of processing are also stored here.

3. Processing: The task of performing operations like arithmetic and logical operations is called processing. The Central Processing Unit (CPU) takes data and instructions from the storage unit and makes all sorts of calculations based on the instructions given and the type of data provided. It is then sent back to the storage unit.

4. Output: This is the process of producing results from the data for getting useful information. Similarly the output produced by the computer after processing must also be kept somewhere inside the computer before being given to you in human readable form. Again the output is also stored inside the computer for further processing.

5. Control: The manner how instructions are executed and the above operations are performed. Controlling of all operations like input, processing and output are performed by control unit. It takes care of step by step processing of all operations in side the computer.

2.4 FUNCTIONAL UNITS

In order to carry out the operations mentioned in the previous section the computer allocates the task between its various functional units. The computer system is divided into three separate units for its operation. They are 1) arithmetic logical unit, 2) control unit, and 3) central processing unit.

2.4.1 Arithmetic Logical Unit (ALU)

After you enter data through the input device it is stored in the primary storage unit. The actual processing of the data and instruction are performed by Arithmetic Logical Unit. The major operations performed by the ALU are addition, subtraction, multiplication, division, logic and comparison. Data is transferred to ALU from storage unit when required. After processing the output is returned back to storage unit for further processing or getting stored.

2.4.2 Control Unit (CU)

The next component of computer is the Control Unit, which acts like the supervisor seeing that things are done in proper fashion. The control unit determines the sequence in which computer programs and instructions are executed. Things like processing of programs stored in the main memory, interpretation of the instructions and issuing of signals for other units of the computer to execute them. It also acts as a switch board operator when several users access the computer simultaneously. Thereby it coordinates the activities of computer’s peripheral equipment as they perform the input and output. Therefore it is the manager of all operations mentioned in the previous section.

2.4.3 Central Processing Unit (CPU)

The ALU and the CU of a computer system are jointly known as the central processing unit. You may call CPU as the brain of any computer system. It is just like brain that takes all major decisions, makes all sorts of calculations and directs different parts of the computer functions by activating and controlling the operations.

HARDWARE

SOFTWARE

trees

2009-01-14T17:47:00.001-08:00

CSC 112 Data Structure

Binary Trees

Definition: A binary tree is either empty or consists
of a node called the root together with two binary trees
called the left subtree and the right subtree.

If h = height of a binary tree,

max # of leaves = 2^h

max # of nodes = 2^{h + 1} - 1

A binary tree with height h and 2^{h + 1} - 1
nodes (or 2^h leaves) is called a full binary tree

Figure 4.4: Examples of binary trees
Figure 4.5: Level by level numbering of a binary tree
Figure 4.4
shows several examples of binary trees.
The nodes of a binary tree can be numbered in a natural way, level
by level, left to right. For example, see Figure 4.5.
A binary tree with n nodes is said to be complete if
it contains all the first n nodes of the above numbering
scheme. Figure 4.6
shows examples of complete and incomplete binary trees.
Total number of binary trees having n nodes

= number of stack-realizable permutations of length n

= number of well-formed parentheses (with n left parentheses and n
right parentheses)

Figure 4.6: Examples of complete, incomplete binary trees

Binary Tree Traversal:

Preorder

Visit root, visit left subtree in preorder, visit right subtree
in preorder

Postorder

Visit left subtree in postorder, right subtree in postorder, then
the root

Inorder

Visit left subtree in inorder, then the root, then the right
subtree in inorder

Figure 4.7
shows several binary trees and the traversal sequences in preorder,
inorder, and postorder.
We can construct a binary tree uniquely from preorder and inorder or
postorder and inorder but not preorder and postorder.

Figure 4.7: Binary tree traversals

Data Structures for Binary Trees:

Arrays, especially suited for complete and full binary trees

Pointer-based

Pointer-based Implementation:

typedef struct node-tag {

item-type info ;

struct
node-tag * left ;

struct
node-tag * right ;

} node-type ;

node-type * root ; /* pointer to root */

node-type * p ; /* temporary pointer */

void preorder(node-type * root)

{

if
(root) {

visit (root) ;

preorder (root
left) ;

preorder (root
right) ;

}

void inorder (node-type * root)

{

if
(root) {

inorder (root
left) ;

visit (root) ;

inorder (root
right) ;

}
}

void postorder (node-type * root)

{

if (root) {

postorder (root
left) ;

postorder (root
right) ;

visit (root) ;

}

binary tree representation of trees

(data structure)

Definition: A way to represent a multiway
tree as a binary
tree. The leftmost
child,
c, of a node,
n, in the multiway tree is the left child, c', of the corresponding
node, n', in the binary tree. The immediately right sibling
of c is the right child of c'.

Formal Definition: A multiway tree T can be
represented by a corresponding binary tree B. Let {n₁,...,
n_k} be nodes of the multiway tree, T. Let {n'₁,...,
n'_k} be nodes of the corresponding binary tree B. Node n_k
corresponds to n'_k. In particular, nodes n_k and
n'_k have the same labels and if n_k is the root
of T, n'_k is the root of B. Connections correspond as
follows:

If n_l is the leftmost child of n_k,
n'_l is the left child of n'_k. (If n_k
has no children, n'_k has no left child.)
If n_s is the next (immediately right)
sibling of n_k, n'_s is the right child of n'_k.

Also known as first child-next sibling
binary tree, doubly-chained tree, filial-heir chain.

Aggregate parent (I am a part of or used in
...)
multiway
tree, k-ary
tree, Schorr-Waite
graph marking algorithm.

Note: See [Knuth97,
1:333, Sect. 2.3.2].

The binary
tree representation
of a multiway
tree or k-ary
tree is based on
first child-next sibling representation of the tree. In this
representation every node is linked with its leftmost child and its
next (right nearest) sibling.

Let us see one example. Consider the following multiway tree

1
/|\

/ | \
/ | \

2 3 4
/ \ |

5 6 7
/ \

8 9

This tree can be represented in first child-next sibling manner as
follows

1
/

/
/

2---3---4
/ /

5---6 7
/

8---9

Now, if we look at the first child-next sibling representation of
the tree closely, we will see that it forms a binary tree. To see
this better, we can rotate every next-sibling edge 45 degrees
clockwise. After that we get the following binary tree:

1
/

2
/ \

5 3
\ \

6 4
/

7
/

8
\

9

This
is binary tree representation of the given (multiway) tree.

Binary
Trees

Trees
are natural structures for representing certain kinds of
hierarchical data. A (rooted) tree consists of a set of nodes
(or vertices) and a set of arcs
(or edges). Each arc links a parent node to one of the parent's
children. A special root
node has no parent. Every other node has exactly one parent. It is
possible to reach any node by following a unique path of arcs from
the root. If arcs are considered bidirectional, there is a unique
path between any two nodes. The simplest kind of tree is a binary
tree where each parent has at most two children.
(We consider
unrooted
trees elsewhere, e.g. in [minimum
spanning trees].)

A
way to think of a binary
tree
is that it is either empty (emptyTree)
or it is a fork
which contains an element and two subtrees which are themselves
binary trees.

Types:

type
tree e = emptyTree | fork e × (tree e) × (tree e)

Operations:

empty:
tree e -> boolean

leaf
: tree e -> boolean

fork
: e × tree e × tree e -> tree e

left
: tree e -> tree e

right:
tree e -> tree e

contents:
tree e -> e

Rules:

empty(emptyTree)
= true

empty(fork(x,
T, T'))= false

leaf(fork(x,
emptyTree, emptyTree)) = true

leaf(fork(x,
T, T'))

=
false, if not empty(T) or not empty(T')

leaf(emptyTree)
= error

left(fork(x,
T, T')) = T

left(emptyTree)
= error

right(fork(x,
T, T')) = T'

right(emptyTree)
= error

contents(fork(x,
T, T')) = x

contents(emptyTree)
= error

The
Tree Abstract Data Type.

(It
is also common to use curried versions of constructors and
functions, such as fork,
especially in functional languages.)

Many
operations can be defined on trees. For example:

height(emptyTree)
= 0 |

height(fork(e,T,T'))
= 1+max(height(T), height(T'))

weight(emptyTree)
= 0 |

weight(fork(e,T,T'))
= 1+weight(T)+weight(T')

Note
that these functions are binary-recursive as is the definition of
the tree type. (Also note that a tree consisting of a single
leaf
is sometimes defined to be of height zero, rather than 1, as
here.)

Trees
have many uses in computing. For example a parse-tree
can represent the structure of an expression:

input:
a+b*c

---------->
+

.
.

a
*

.
.

b
c

Multiplication
has a higher priority
then addition and binds more tightly. This tree shows that a+b*c
is interpreted as a+(b*c) rather than as (a+b)*c. Such trees are
used in compilers and other programs.

Implementation
of Binary Trees by Pointers and Records

A
tree data type can be implemented as a collection of records and
pointers.

[C/Tree/Tree.h]

[C/Tree/TreeElement.h]

.so
tree/tree.type.t

The
basic operations can create new records and manipulate pointers.

[C/Tree/Ops.c]

.so
tree/tree.cons.t

Not
surprisingly this tree implementation is similar to the
implementation of hierarchical
lists.

An
output routine for trees is a virtual necessity. A tree can be
printed in a style like that used for lists but a graphical
two-dimensional layout is more informative. It is difficult to
print trees down the page, because they quickly grow too wide, but
it is relatively easy to print them across the page so that the
root is at the left and the tree grows to the right.

[C/Tree/Write.c]

.so
tree/tree.put.t

For
an example of tree output, see later sections.

Example:
Parse Trees

Parsing
an input language according to a grammar is frequently necessary
in computing. Here we consider a language of simple arithmetic
expressions. A grammar written in Backus Naur form (BNF) is given
below.

<operand>
::= <identifier> | ( <exp> )

<letter>
::= "a" | "b" | ... | "z"

Grammar
for Simple Expression.

The
grammar can be read as a definition of the syntactic structure of
expressions, <exp>. The symbol `::=' can be read as `is' or
`can be replaced by'. The symbol `|' can be read as `or'. The
names in angle brackets, such as '<exp>', are variables for
parts of the language. The string <exp>+1 is not a legal
expression but it stands for many legal expressions such as x+1,
y+1 and (x+y*z)+1. The first line of the grammar can be read as:
an <exp> is an <exp> plus <term> or a <term>.
An expression is either an expression plus a term or just a term.
Note that the syntax rules are recursive. A little thought shows
that an expression is a sequence of terms separated by plus signs.
Similarly, a term is a sequence of operands separated by
multiplication signs. An operand is either an identifier or a
bracketed subexpression. An identifier is a sequence of letters.

A
parser can be written using the recursive-descent
technique. A procedure is written to recognise each class of
object in the grammar - exp, term, operand. These routines are
recursive, as is the grammar, and call each other to implement the
grammar rules. For example, the routine for expression calls the
routine for term. The repetitive nature of expressions and terms
is coded by the use of a loops. A bracketed subexpression is
inherently recursive and so is the parser at that point. The
complete parser is given below. It is moderately long but not
complex, especially if read with the grammar in mind. A lexical
routine, insymbol, skips white space and packages input letters
into identifiers and other kinds of symbol. It is followed by the
parser proper consisting of the routines Operand, Term and Exp.

[C/Tree/Parser.h]

[C/Tree/Parser.c]

.so
tree/tree.parse.t

Note
the use of mutual recursion. Various errors may be detected during
parsing. If the expression is syntactically correct, the tree
representing its structure is finally printed.

input:
a + b*(c+d)

Parse
Tree:

|
| |d---------|

|
|+---------|

|
| |c---------|

|*---------|

|
|b---------|

+---------|

|a---------|

Recursive
Tree Traversal

There
are three classic ways of recursively traversing
a tree or of visiting every one of its nodes once. In each of
these, the left and right subtrees are visited recursively and the
distinguishing feature is when the element in the root is visited
or processed.

In
a preorder
or prefix
traversal the root is visited first (pre) and then the left and
right subtrees are traversed.

[C/Tree/Prefix.c]

.so
tree/tree.prefix.t

In
an infix
traversal, the left subtree is traversed and then the root is
visited and finally the right subtree is traversed.

[C/Tree/Infix.c]

.so
tree/tree.infix.t

In
a postorder
or postfix
traversal the left and right subtrees are traversed and then the
root is visited afterwards (post).

[C/Tree/Postfix.c]

.so
tree/tree.postfix.t

This
method can be used to generate postfix or reverse
Polish
code for a stack machine.

Given
the following tree,

|type------|

the-------|

|
|rover-----|

|
| |of--------|

|
| | |motor-----|

|land------|

|
|is--------|

|
| | |car-------|

|
| |a---------|

Example
Tree.

the
three traversals give the following results. The results of yet
another method, breadth-first
traversal, are included for comparison; see the next section.

infix:
a car is land motor of rover the type

prefix:
the land is a car rover of motor type

postfix:
car a is motor of rover land type the

b-first:
the land type is rover a of car motor

Traversals.

Note
that the method given for printing a tree is a reversed infix
traversal.

Breadth-First
Traversal

A
breadth-first
traversal of a tree starts at the root of the tree. It next visits
the children, then the grand-children and so on.

.
.

2
3

.
. . .

4
5 6 7

.
. . . .

8
9 10 11 12

.
. .

13
14 15

Example:
Breadth-First Order.

The
numbers indicate the order in which the nodes are visited, not the
contents of the nodes. Because children are only accessible from a
parent, they must be stored while the parent's siblings and
cousins are visited. A [queue]
is used to do this.

[C/Queue/Queue.h]

[C/Tree/QueueElement.h]

[C/Tree/BFirst.c]

.so
tree/tree.bf.t

Note
that the queue is a queue of pointer to node or a queue of tree
type. Initially the queue contains just the root of the tree. At
each iteration of the algorithm, the first element is removed from
the queue. Its children, if any, are pushed onto the end of the
queue and the element is processed. The algorithm terminates when
the queue is empty. See also the chapter on queues.

Recursion

Most
routines on trees are recursive. This is natural because the tree
is a recursive data type. It is possible to write iterative
versions of these operations but it is harder to do so than is the
case for flat lists because the tree type is binary
recursive.
The flat list and hence most of its operations are linear
recursive
and a linear recursive routine usually has a simple iterative
version. It is often necessary to introduce an explicit
stack into a program when writing a non-recursive tree routine.
This is often not worth the effort as the language implementors
can usually do a better job with the system stack.

The
object-oriented programming language Java
has the notion of an Enumeration,
i.e. an iterator, which steps through the elements of a set of
values. An enumerator must implement the predicate hasMoreElements
and the function nextElement.
To program an enumerator which will emit the contents of a tree in
one of the standard orders it is useful to a employ a Stack:

[Java/Tree/egPrefixEnum.txt]

Side-Effects

The
tree operations described so far have no side-effects except for
input, output and manipulation of dynamic storage; they are pure
tree operations. As is the case with lists, it is often necessary
or desirable to use operations having side-effects on efficiency
grounds. This is particularly natural if a program uses a single
tree as a dictionary or database structure. As before, should
multiple trees share components, changing one tree may change
another and if this is not anticipated it will cause program bugs.

Search Trees

A
binary
search tree
can be created so that the elements in it satisfy an ordering
property. This allows elements to be searched for quickly. All of
the elements in the left subtree are less than the element at the
root which is less than all of the elements in the right subtree
and this property applies recursively to all the subtrees. The
great advantage of this is that when searching for an element, a
comparison with the root will either find the element or indicate
which one
subtree to search. The ordering is an invariant property of the
search tree. All routines that operate on the tree can make use of
it provided that they also keep it holding true.

Demonstration: There is a demonstration of Binary Search
(& AVL) Trees [here].

.so
tree/tree.search.t

It
takes O(h) time to search a search tree of height h. Since a tree
of height `h' can hold n=2^h-1 elements, the search
takes O(log(n)) time under favourable circumstances. The
search-tree and its search routine should be compared with the use
of the binary search algorithm on sorted arrays in the chapter on
tables.

The
use of the tree speeds up the insertion and deletion operations at
the price of the space needed to hold the pointers. The tree has
the speed advantage when the data in the structure changes
rapidly.

The
routine given here to insert an element does so as a side-effect
by changing the tree.

[C/Tree/Insert.c]

.so
tree/tree.insert.t

If
elements are inserted in the order d, b, a, c, e, f, g the
following tree is created:

----------->d

.
.

b
e

.
. .

a
c f

Note
that an insertion takes O(h) time. Under favourable circumstances,
a balanced
tree is created, as for b, a, c, giving O(log(n)) search time. If
the input is sorted however an unbalanced tree approximating a
list is created, as for e, f, g, and the search degenerates to an
O(n) linear search. This problem is addressed later.

input:
the land rover is a type of motor car

Search
Tree:

|type------|

the-------|

|
|rover-----|

|
| |of--------|

|
| | |motor-----|

|land------|

|
|is--------|

|
| | |car-------|

|
| |a---------|

Example
Search Tree.

A
new element is added to the tree as a new peripheral, leaf node.
However if an element can also be deleted it is possible for it to
be internal.
This makes deletion rather more difficult than insertion.

A
leaf element is easily deleted by setting the pointer to it to
emptyTree.

T:-----|
T:emptyTree

before
after

Deletion
of a Leaf.

The
node becomes garbage and can be freed.

An
element with one child can be deleted by by-passing it.

T:------|
T:|

|
|

v
|

x
|

.
emptyTree |

.
v

e
e

.
. . .

before
after

Deletion
of a Single-Child Parent.

An
internal element x with two children cannot easily be bypassed
without loosing one of its subtrees. The solution is to overwrite
x with some other element y of the tree and then to delete the
original copy of y. There are two obvious elements to choose from
- either the largest element `A' less than x or the smallest
element `B' greater than x. Each of these has at most one child!
The sortedness of the tree is maintained if x is overwritten with
either of these.

T:----------|
T:-----|

|
|

v
v

x
B

.
. . .

L
R L R

.
. . . . . . .

A
B A C

.
. . . .

.
.

before
after

Deletion
of a Two-Child Parent.

Both
of A and B fall into one of the cases previously dealt with. A can
be found from x by taking one step left and then as many steps
right as possible. B can be found by taking one step right and
then as many steps left as possible.

.so
tree/tree.delete.t

Deletion takes O(h) time.

Notes

[Tries]
and [PATRICIA
trees] are an alternatives to binary search trees.
The [Suffix
Tree] is a data-structure for solving the string
searching problem.

Height-Balanced
Trees

As
mentioned above, if elements are inserted into a search tree in
sorted order, a tree is created that is equivalent to a list. This
will lead to inefficient searches. A height-balanced
tree or an AVL-tree (after G. M. Adel'son-Velskii and E. M.
Landis) is a search tree in which the height of the right subtree
minus the height of the left subtree equals 1, 0, or -1. This
property also applies recursively to all subtrees. It can be shown
that a height-balanced tree of `n' elements has height O(log(n))
and this guarantees efficient search. Fortunately fast O(log(n))
insertion and deletion is still possible.

Demonstration: There is a demonstration of AVL (&
bin. s.) Trees [here].

.so
tree/tree.AVLtype.t

A
flag indicating the balance of each subtree is added to the node
record.

There
are four crucial cases during insertion. In the first case, the
left subtree L grows too tall on its left:

T
L

.
. . .

L
. -----> . T

.
. | | . .

|
| * | |

*
new elt' rebalanced

*
disturbs

*
balance

Left-2
Rotation.

By
rotating about L and T the height balance is restored and the
ordering in the tree is maintained. In the second case, L grows
too tall on its right:

T
LR

.
. . .

L
. L T

.
. | . . . .

.
. | ----> . . . .

.
LR | . . . .

|
.. | | | | |

|
. . | | | | |

|
| | | | | | |

|
| | | * |

Left-3
Rotation.

The
rotation restores the balance while maintaining the tree ordering.
In the above example left(LR) grew; an alternative is that
right(LR) grew but the same operations still restore the balance.
There are mirror-image right-2 and right-3 rotations.

Maintaining
the balance significantly complicates the tree insertion routine.
However a fixed amount of work is done at each node that is
visited and so it takes O(h) time.

.so
tree/tree.AVLinsert.t

Note
that if a tree has just grown in height, it can only be perfectly
balanced if it is a single (new) leaf. Otherwise one subtree must
be higher than the other.

input:
the land rover is a type of motor car

|
|type------|

|the-------|

rover-----|

|
| |of--------|

|
|motor-----|

|
| |land------|

|is--------|

|
| |car-------|

|
|a---------|

Height-Balanced
Tree.

Compare
this with the tree given earlier and created by the non-balancing
insert.

Notes

G. M. Adelson-Velskii and E. M. Landis [AVL]. An algorithm for
the organization of information. Soviet Math. Dokl. 3,
p1259-1263, 1962.
N. Wirth. Algorithms and Data Structures. p218,
Prentice-Hall, 1986.
AVL-tree insertion and deletion.
M. A. Weiss. Data Structures and Algorithm Analysis in C.
s4.4, pp110. Addison Wesley 1997.
[2-3
trees], [2-3-4
trees] and [B-trees]

Implementation
of Binary Trees by Arrays

A
binary tree can be implemented as an array of records.

type
TreeT :0..nmax

var
Tree: array 1..nmax of

record
elt :Element_Type

left,
right :TreeT

end
record

The
empty tree is represented by zero. Left and right are indexes to
left and right subtrees.

This
implementation has no advantage in a language supporting dynamic
storage unless random access to nodes is also needed. It is useful
in a language without dynamic storage.

Full
Trees by Arrays

It
is possible to define a full
or weight
balanced
tree in contrast to a height balanced tree. The empty tree is a
full tree of zero levels. If T and T' are full binary trees of n
levels then fork(e,T,T') is a full binary tree of n+1 levels.

.
.

2
3

.
. . .

4
5 6 7

Full
Binary Tree of 3 Levels.

The
numbering of the nodes corresponds to a breadth-first traversal.
This suggests that such a tree can be stored in an array:

const
n = 2**Levels - 1

array
1..n of Element_Type

type
tree = 0..n

empty(T)
= T=0

left(T)
= 2*T

right(T)
= 2*T+1

parent(T)
= T div 2

leaf(T)
= T >= 2**(Levels-1)

Such
an implementation is very efficient indeed, if the tree is full,
because no space at all is used for pointers. See the chapter on
sorting for an application of this technique in [heap-sort].

Testing
and Debugging

Programming
techniques for trees share a great deal in common with those for
lists. Pre and post conditions and assertions should be included
where possible. Minimise the use of side-effects in general and
the manipulation of global variables in particular.

Note
that there are really just two kinds of tree - emptyTree and
non-emptyTree. Most operations on a tree follow this pattern:

f(emptyTree)
= ... |

f(fork(e,T,T'))
= ...often f(T)...f(T')...

If
a case is missing it probably indicates an error. The empty case
is usually very simple, often returning a constant. The main case
often operates on one or both subtrees recursively.

When
testing or debugging a tree routine, test cases should cover the
above options. For non-emptyTree trees, it may be appropriate to
try a tree of a "few" nodes and a tree of a single node.
As usual it is invaluable to write the output routine first. The
most common problems are: . unassigned pointers, particularly
those that should be emptyTree, . lost pointer values through a
wrong ordering of operations, . knotted pointers maybe introducing
a cycle, . side-effects through shared pointers, intentional or
otherwise.

The
coding of reasonably complex routines such as those on AVL trees
is prone to small typographical errors. Nothing can beat careful
proof reading but one good testing trick is to use a set of
ascending data and then its reversal in which case the mirror
image tree should be produced. This test is not sufficient on its
own! It is important to exercise all the paths through a complex
routine and this requires a great deal of thought.

Exercises

Classify tree operations (height, weight, min_element,
max_element, flatten, insert, lookup, delete, pre,- in- and
post-order traversal) on unordered binary trees and on search
trees as either linear or binary recursive. Note that a
linear-recursive operation may contain two or more calls on
itself but only ever execute at most one of them under the
control of an if statement. Write iterative
versions of one or more of the linear operations.
Add a full set of operators +, -, *, / to the expression parser.
Write a routine to traverse the expression parse tree to generate
reverse Polish code. eg. a*b+c*d ---> a b * c d * +
Write a routine to do symbolic differentiation. Input is the
parse tree of an arithmetic expression which may contain
numerals, variables {x, y, ...}, + and *. Output is the tree of
the expression that is the result of differentiation with respect
to a given variable.

Use the rules:

diff(x, x) = 1

diff(y, x) = 0 if y is a constant or a variable different from x

diff(A+B, x) = diff(A,x)+diff(B,x)

diff(A*B, x) = A*diff(B,x)+diff(A,x)*B

eg. diff(x*x+3*x+4, x) = x*1+1*x+3*1+0*x+0 = 2*x+3

Write a routine to free all of the nodes in a
binary tree. Count the number of new and free
operations and check that they are equal.
Write a routine to collect only the elements in all the leaf
nodes of a binary tree into a list.
The path of a node in a tree is the sequence of elements
contained in nodes from the root, down to and including the node
itself. Give a procedure to print the path of every leaf node in
a tree.
A height-balanced tree is not necessarily full or
weight-balanced. How un-weight-balanced can one be? ie. What is
the minimum possible number `n' of nodes in a height-balanced
tree for height h=1, 2, ..., 8. Is there a pattern? How does n
compare with the value 2^h-1 for a full tree?
(Hard) Implement a delete operation for height-balanced
trees.

CS-IT Lecture Notes

Lesson10

Lesson 1

trees

Binary Trees

Implementation of Binary Trees by Pointers and Records

Example: Parse Trees

Recursive Tree Traversal

Breadth-First Traversal

Recursion

Side-Effects

Search Trees

Notes

Height-Balanced Trees

Notes

Implementation of Binary Trees by Arrays

Full Trees by Arrays

Testing and Debugging

Exercises

Binary
Trees

Implementation
of Binary Trees by Pointers and Records

Example:
Parse Trees

Recursive
Tree Traversal

Breadth-First
Traversal

Height-Balanced
Trees

Implementation
of Binary Trees by Arrays

Full
Trees by Arrays

Testing
and Debugging