Sunday 22 June 2014

DECIMAL NUMBERS


DECIMAL NUMBERS

In the decimal number systems each of the ten digits, 0 through 9, represents a certain quantity. The position of each digit in a decimal number indicates the magnitude of the quantity represented and can be assigned a weight. The weights for whole numbers are positive powers of ten that increases from right to left, beginning with 10º = 1 that is 10³ 10² 10¹ 10º

For fractional numbers, the weights are negative powers of ten that decrease from left to right beginningwith 10¯¹ that is 10² 10¹ 10º. 10¯¹ 10¯² 10¯³

The value of a decimal number is the sum of digits after each digit has been multiplied by its weights asin following examples

Express the decimal number 87 as a sum of the values of each digit.

The digit 8 has a weight of10 which is 10 as indicated by its position. The digit 7 has a weight of 1 which is 10º as indicated by its position.

87 = (8 x 101) + (7 x 100)

Express the decimal number 725.45 as a sum of the values of each digit.

725. 45 = (7 x 10²) + (2 x 10¹) + (5 x 10º) + (4 x 10¯¹) + (5 x 10¯²) = 700 + 20 + 5 + 0.4 + 0.05

BINARY NUMBERS

The binary system is less complicated than the decimal system because it has only two digits, it is a basetwo system. The two binary digits (bits) are 1 and 0. The position of a 1 or 0 in a binary number indicates its weight, or value within the number, just as the position of a decimal digit determines the value of that digit. The weights in a binary number are based on power of two as:

….. 24 2³ 22 21 20. 2-1 2-2 ….

With 4 digits position we can count from zero to 15.In general, with n bits we can count up to a number equal to Ķ - 1. Largest decimal number = Ķ - 1.A binary number is a weighted number. The right-most bit is the least significant bit (LSB) in a binary whole number and has a weight of

2º =1. The weights increase from right to left by a power of two for each bit. The left-most bit is the most significant bit (MSB); its weight depends on the size of the binary number.

BINARY-TO-DECIMAL CONVERSION

The decimal value of any binary number can be found by adding the weights of all bits that are 1 and discarding the weights of all bits that are 0

Example

Let‘s convert the binary whole number 101101 to decimal

Weight:25 24 23 22 21 20

X

Binary no: 1 0 1 1 0 1

Value 32 0 8 4 0 1

Sum = 45

CLASSIFICATION OF COMPUTERS


CLASSIFICATION OF COMPUTERS

There are four classifications of digital computer systems:

super-computer, mainframe computer, minicomputer, and microcomputer.

· Super-computers are very fast and powerful machines. Their internal architecture enables them to run at the speed of tens of MIPS (Million Instructions per Second). Super- computers are very expensive and for this reason are generally not used for CAD applications. Examples of super-computers are: Cray and CDC Cyber 205.

· Mainframe computers are built for general computing, directly serving the needs of business and engineering. Although these computing systems are a step below super- computers, they are still very fast and will process information at about 10 MIPS. Mainframe computing systems are located in a centralized computing center with 20-

100+ workstations. This type of computer is still very expensive and is not readily found in architectural/interior design offices.

· Minicomputers were developed in the 1960's resulting from advances in microchip technology. Smaller and less expensive than mainframe computers, minicomputers run at several MIPS and can support 5-20 users. CAD usage throughout the 1960's used minicomputers due to their low cost and high performance. Examples of minicomputers are: DEC PDP, VAX 11.

· Microcomputers were invented in the 1970's and were generally used for home computing and dedicated data processing workstations. Advances in technology have improved microcomputer capabilities, resulting in the explosive growth of personal computers in industry. In the 1980's many medium and small design firms were finally introduced to CAD as a direct result of the low cost and availability of microcomputers. Examples are: IBM, Compaq, Dell, Gateway, and Apple Macintosh.

The average computer user today uses a microcomputer. These types of computers include PC's, laptops, notebooks, and hand-held computers such as Palm Pilots. Larger computers fall into a mini-or mainframe category. A mini-computer is 3-25 times faster than a micro. It is physically larger and has a greater storage capacity.

A mainframe is a larger type of computer and is typically 10-100 times faster than the micro. These computers require a controlled environment both for temperature and humidity. Both the mini and mainframe computers will support more workstations than will a micro. They also cost a great deal more than the micro running into several hundred thousand dollars for the mainframes.

Processors

The term processor is a sub-system of a data processing system which processes received information after it has been encoded into data by the input sub-system. These data are then processed by the processing sub-system before being sent to the output sub-system where they are decoded back into information. However, in common parlance processor is usually referred to the microprocessor, the brains of the modern day computers.

There are two main types of processors: CISC and RISC.

CISC: A Complex Instruction Set Computer (CISC) is a microprocessor Instruction Set Architecture (ISA) in which each instruction can indicate several low-level operations, such as a load from memory, an arithmetic operation, and a memory store, all in a single instruction. The term was coined in contrast to Reduced Instruction Set Computer (RISC).

Examples of CISC processors are the VAX, PDP-11, Motorola 68000 family and the Intel x86/Pentium CPUs.

RISC: Reduced Instruction Set Computing (RISC), is a microprocessor CPU design philosophy that favors a smaller and simpler set of instructions that all take about the same amount of time to execute. Most types of modern microprocessors are RISCs, for instance ARM, DEC Alpha, SPARC, MIPS, and PowerPC.

The microprocessor contains the CPU which is made up of three components--the control unit supervises all that is going on in the computer, the arithmetic/logic unit which performs the math and comparison operation, and temporary memory. Because of the progress in developing better microprocessors, computers are continually evolving into faster and better units.

Notebooks:
A laptop computer (also known as notebook computer) is a small mobile personal computer, usually weighing around from 1 to 3 kilograms (2 to 7 pounds). Notebooks smaller than an A4 sheet of paper and weighing around 1 kg are sometimes called sub-notebooks and those weighing around 5 kg a desk note (desktop/notebook). Computers larger than PDAs but smaller than notebooks are also sometimes called "palmtops". Laptops usually run on batteries.

Notebook Processor:

A notebook processor is a CPU optimized for notebook computers. All computing devices require a CPU. One of the main characteristics differentiating notebook processors from other CPUs is low-power consumption.

The notebook processor is becoming an increasing important market segment in the semiconductor industry. Notebook computers are an increasingly popular format of the broader category of mobile computers. The objective of a notebook computer is to provide the performance and functionality of a desktop computer in a portable size and weight. Wireless networking and low power consumption are primary consideration in the choice of a notebook processor.

Integrated Components
Unlike a desktop computer, a notebook has most of the components built-in or integrated into the computer. For desktop systems, determining which computer to buy is generally not based on what type of keyboard or mouse that is available. If you don't like the keyboard or mouse, you can always purchase something else. However, in the case of a notebook computer, the size of the keyboard or type of pointing device may be something that you need to consider unless you intend to use a regular mouse or full-sized keyboard. There are some notebooks that have a keyboard that expands when the notebook is opened which is a nice feature if you find the normal keyboard to be too small. Pointing devices vary from a touch pad to a stick within the keyboard to a roller or track-ball. Most notebooks have the video, sound, and speakers integrated into the computer and some notebooks even have a digital camera built-in which is very handy for video conferencing.

BOOTING:

In computing, booting is a bootstrapping process that starts operating systems when the user turns on a computer system. A boot sequence is the set of operations the computer performs when it is switched on which load an operating system.

Everything that happens between the times the computer switched on and it is ready to accept commands/input from the user is known as booting.

The process of reading disk blocks from the starting of the system disk (which contains the Operating System) and executing the code within the bootstrap. This will read further information off the disk to bring the whole operating system online. Device drivers are contained within the bootstrap code that support all the locally attached peripheral devices and if the computer is connected to a network, the operating system will transfer to the Network Operating system for the "client" to log onto a server

The Process of loading a computer memory with instructions needed for the computer to operate. The process and functions that a computer goes through when it first starts up, ending in the proper and complete loading of the Operating System. The sequence of computer operations from power-up until the system is ready for use

COLD BOOTING:

The cold booting is the situation, when all the computer peripherals are OFF and we start the computer by switching ON the power. WARM BOOTING:

The warm booting is the situation, when we restart the computer by pressing the RESET button and pressing CTRL+ ALT + DEL keys together.

Graphic User Interface (GUI)

A program interface that takes advantage of the computer's graphics capabilities to make the program easier to use. Well-designed graphical user interfaces can free the user from learning complex command languages.On the other hand, many users find that they work more effectively with a command-driven interface, especially if they already know the command language.

MEMORY OR PRIMARY STORAGE


MEMORY OR PRIMARY STORAGE

Purpose of Storage

The fundamental components of a general-purpose computer are arithmetic and logic unit, control circuitry, storage space, and input/output devices. If storage was removed, the device we had would be a simple calculator instead of a computer. The ability to store instructions that form a computer program, and the information that the instructions manipulate is what makes stored program architecture computers versatile.

Primary Storage

Primary storage is directly connected to the central processing unit of the computer. It must be present for the CPU to function correctly, just as in a biological analogy the lungs must be present (for oxygen storage) for the heart to function (to pump and oxygenate the blood). As shown in the diagram, primary storage typically consists of three kinds of storage:

Processors Register

It is the internal to the central processing unit. Registers contain information that the arithmetic and logic unit needs to carry out the current instruction. They are technically the fastest of all forms of computer storage.

Main memory

It contains the programs that are currently being run and the data the programs are operating on. The arithmetic and logic unit can very quickly transfer information between a processor register and locations in main storage, also known as a "memory addresses". In modern computers, electronic solid-state random access memory is used for main storage, and is directly connected to the CPU via a "memory bus" and a "data bus".

Cache memory

It is a special type of internal memory used by many central processing units to increase their performance or "throughput". Some of the information in the main memory is duplicated in the cache memory, which is slightly slower but of much greater capacity than the processor registers, and faster but much smaller than main memory.

Memory

Memory is often used as a shorter synonym for Random Access Memory (RAM). This kind of memory is located on one or more microchips that are physically close to the microprocessor in your computer. Most desktop and notebook computers sold today include at least 512 megabytes of RAM (which is really the minimum to be able to install an operating system). They are upgradeable, so you can add more when your computer runs really slowly.

The more RAM you have, the less frequently the computer has to access instructions and data from the more slowly accessed hard disk form of storage. Memory should be distinguished from storage, or the physical medium that holds the much larger amounts of data that won't fit into RAM and may not be immediately needed there.

Storage devices include hard disks, floppy disks, CDROMs, and tape backup systems. The terms auxiliary storage, auxiliary memory, and secondary memory have also been used for this kind of data repository.

RAM is temporary memory and is erased when you turn off your computer, so remember to save your work to a permanent form of storage space like those mentioned above before exiting programs or turning off your computer.




STORAGE DEVICES


STORAGE DEVICES

The purpose of storage in a computer is to hold data or information and get that data to the CPU as quickly as possible when it is needed. Computers use disks for storage: hard disks that are located inside the computer, and floppy or compact disks that are used externally.

• Computers Method of storing data & information for long term basis i.e. even after PC is switched off.

• It is non - volatile

• Can be easily removed and moved & attached to some other device

• Memory capacity can be extended to a greater extent

• Cheaper than primary memory

Storage Involves Two Processes

a) Writing data b) Reading data

Floppy Disks

The floppy disk drive (FDD) was invented at IBM by Alan Shugart in 1967. The first floppy drives used an 8-inch disk (later called a "diskette" as it got smaller), which evolved into the 5.25- inch disk that was used on the first IBM Personal Computer in August 1981. The 5.25 -inch disk held 360 kilobytes compared to the 1.44 megabyte capacity of today's 3.5-inch diskette.

The 5.25-inch disks were dubbed "floppy" because the diskette packaging was a very flexible plastic envelope, unlike the rigid case used to hold today's 3.5-inch diskettes.

By the mid-1980s, the improved designs of the read/write heads, along with improvements in the magnetic recording media, led to the less-flexible, 3.5-inch, 1.44- megabyte (MB) capacity FDD in use today. For a few years, computers had both FDD sizes (3.5- inch and 5.25-inch). But by the mid-1990s, the 5.25-inch version had fallen out of popularity, partly because the diskette's recording surface could easily become contaminated by fingerprints through the open access area.

When you look at a floppy disk, you'll see a plastic case that measures 3 1/2 by 5 inches. Inside that case is a very thin piece of plastic that is coated with microscopic iron particles. This disk is much like the tape inside a video or audio cassette. Basically, a floppy disk drive reads and writes data to a small, circular piece of metal-coated plastic similar to audio cassette tape.

At one end of it is a small metal cover with a rectangular hole in it. That cover can be moved aside to show the flexible disk inside. But never touch the inner disk - you could damage the data that is stored on it. On one side of the floppy disk is a place for a label. On the other side is a silver circle with two holes in it. When the disk is inserted into the disk drive, the drive hooks into those holes to spin the circle. This causes the disk inside to spin at about 300 rpm! At the same time, the silver metal cover on the end is pushed aside so that the head in the disk drive can read and write to the disk.

Floppy disks are the smallest type of storage, holding only 1.44MB.

3.5-inch Diskettes (Floppy Disks) features:

• Spin rate: app. 300 revolutions per minute (rpm)

• High density (HD) disks more common today than older, double density (DD) disks

• Storage Capacity of HD disks is 1.44 MB

Floppy Disk Drive Terminology

Floppy disk - Also called diskette. The common size is 3.5 inches.

Floppy disk drive - The electromechanical device that reads and writes floppy disks. Track - Concentric ring of data on a side of a disk.

Sector - A subset of a track, similar to wedge or a slice of pie.

It consists of a read/write head and a motor rotating the disk at a high speed of about 300 rotations per minute. It can be fitted inside the cabinet of the computer and from outside, the slit where the disk is to be inserted, is visible. When the disk drive is closed after inserting the floppy inside, the monitor catches the disk through the Central of Disk hub, and then it starts rotating.

There are two read/write heads depending upon the floppy being one sided or two sided. The head consists of a read/write coil wound on a ring of magnetic material. During write operation, when the current passes in one direction, through the coil, the disk surface touching the head is magnetized in one direction. For reading the data, the procedure is reverse. I.e. the magnetized spots on the disk touching the read/write head induce the electronic pulses, which are sent to CPU.

The major parts of a FDD include:

Read/Write Heads: Located on both sides of a diskette, they move together on the same assembly. The heads are not directly opposite each other in an effort to prevent interaction between write operations on each of the two media surfaces. The same head is used for reading and writing, while a second, wider head is used for erasing a track just prior to it being written. This allows the data to be written on a wider "clean slate," without interfering with the analog data on an adjacent track.

Drive Motor: A very small spindle motor engages the metal hub at the center of the diskette, spinning it at either 300 or 360 rotations per minute (RPM).

Stepper Motor : This motor makes a precise number of stepped revolutions to move the read/write head assembly to the proper track position. The read/write head assembly is fastened to the stepper motor shaft.

Mechanical Frame : A system of levers that opens the little protective window on the diskette to allow the read/write heads to touch the dual-sided diskette media. An external button allows the diskette to be ejected, at which point the spring-loaded protective window on the diskette closes.

Circuit Board : Contains all of the electronics to handle the data read from or written to the diskette. It also controls the stepper-motor control circuits used to move the read/write heads to each track, as well as the movement of the read/write heads toward the diskette surface.

Electronic optics check for the presence of an opening in the lower corner of a 3.5-inch diskette (or a notch in the side of a 5.25-inch diskette) to see if the user wants to prevent data from being written on it.

Hard Disks

Your computer uses two types of memory: primary memory which is stored on chips located

on the motherboard, and secondary memory that is stored in the hard drive. Primary memory holds all of the essential memory that tells your computer how to be a computer. Secondary memory holds the information that you store in the computer.

Inside the hard disk drive case you will find circular disks that are made from polished steel. On the disks, there are many tracks or cylinders. Within the hard drive, an electronic reading/writing device called the head passes back and forth over the cylinders, reading information from the disk or writing information to it. Hard drives spin at 3600 or more rpm (Revolutions Per Minute) - that means that in one minute, the hard drive spins around over 7200 times!

Optical Storage

• Compact Disk Read-Only Memory (CD-ROM)

• CD-Recordable (CD-R)/CD-Rewritable (CD-RW)

• Digital Video Disk Read-Only Memory (DVD-ROM)

• DVD Recordable (DVD-R/DVD Rewritable (DVD-RW)

• Photo CD

Optical Storage Devices Data is stored on a reflective surface so it can be read by a beam of laser light. Two Kinds of Optical Storage Devices

• CD-ROM (compact disk read-only memory)

• DVD-ROM (digital video disk read-only memory)

Compact Disks
Instead of electromagnetism, CDs use pits (microscopic indentations) and lands (flat surfaces) to store information much the same way floppies and hard disks use magnetic and non-magnetic storage. Inside the CD-Rom is a laser that reflects light off of the surface of the disk to an electric eye. The pattern of reflected light (pit) and no reflected light (land) creates a code that represents data.

CDs usually store about 650MB. This is quite a bit more than the 1.44MB that a floppy disk stores. A DVD or Digital Video Disk holds even more information than a CD, because the DVD can store information on two levels, in smaller pits or sometimes on both sides.

Recordable Optical Technologies

• CD-Recordable (CD-R)

• CD-Rewritable (CD-RW)

• PhotoCD

• DVD-Recordable (DVD-R)

• DVD-RAM

CD ROM - Compact Disc Read Only Memory.

Unlike magnetic storage device which store data on multiple concentric tracks, all CD formats store data on one physical track, which spirals continuously from the center to the outer edge of the recording area. Data resides on the thin aluminum substrate immediately beneath the label. The data on the CD is recorded as a series of microscopic pits and lands physically embossed on an aluminum substrate. Optical drives use a low power laser to read data from those discs without physical contact between the head and the disc which contributes to the high reliability and permanence of storage device.

To write the data on a CD a higher power laser are used to record the data on a CD. It creates the pits and land on aluminum substrate. The data is stored permanently on the disc. These types of discs are called as WORM (Write Once Read Many). Data written to CD cannot subsequently be deleted or overwritten which can be classified as advantage or disadvantage depending upon the requirement of the user. However if the CD is partially filled then the more data can be added to it later on till it is full. CDs are usually cheap and cost effective in terms of storage capacity and transferring the data.

The CD‘s were further developed where the data could be deleted and re written. These types of CDs are called as CD Rewritable. These types of discs can be used by deleting the data and making the space for new data. These CD‘s can be written and rewritten at least 1000 times.

CD ROM Drive

CD ROM drives are so well standardized and have become so ubiquitous that many treat them as commodity items. Although CD ROM drives differ in reliability, which standards they support and numerous other respects, there are two important performance measures.

· Data transfer rate

· Average access

Data transfer rate: Data transfer rate means how fast the drive delivers sequential data to the interface. This rate is determined by drive rotation speed, and is rated by a number followed by

‗X‘. All the other things equal, a 32X drive delivers data twice the speed of a 16X drive. F ast data transfer rate is most important when the drive is used to transfer the large file or many sequential smaller files. For example: Gaming video.

CD ROM drive transfers the data at some integer multiple of this basic 150 KB/s 1X rate. Rather than designating drives by actual KB/s output drive manufacturers use a multiple of the standard

1X rate. For example: a 12X drive transfer data at (12*150KB/s) 1800 KB/s and so on.

The data on a CD is saved on tracks, which spirals from the center of the CD to outer edge. The portions of the tracks towards center are shorter than those towards the edge. Moving the data

under the head at a constant rate requires spinning the disc faster as the head moves from the center where there is less data per revolution to the edge where there is more data. Hence the rotation rate of the disc changes as it progresses from inner to outer portions of the disc.

CD Writers

CD recordable and CD rewritable drives are collectively called as CD writers or CD burners.

They are essentially CD ROM drives with one difference. They have a more powerful laser that, in addition to reading discs, can record data to special CD media.

Pen Drives / Flash Drives

· Pen Drives / Flash Drives are flash memory storage devices.

· They are faster, portable and have a capability of storing large data.

· It consists of a small printed circuit board with a LED encased in a robust plastic

· The male type connector is used to connect to the host PC

· They are also used a MP3 players

NUMBER SYSTEMS
BinaryDecimalOctalHexadecimal
00000000
00010111
00100222
00110333
01000444
01010555
01100666
01110777
100008108
100109119
10101012A
10111113B
11001214C
11011315D
11101416E
11111517F

TYPES OF RAM


TYPES OF RAM

There are two types of RAM used in PCs - Dynamic and Static RAM.

Dynamic RAM (DRAM): The information stored in Dynamic RAM has to be refreshed after every few milliseconds otherwise it will get erased. DRAM has higher storage capacity and is cheaper than Static RAM.

Static RAM (SRAM): The information stored in Static RAM need not be refreshed, but it remains stable as long as power supply is provided. SRAM is costlier but has higher speed than DRAM.

Additional kinds of integrated and quickly accessible memory are Read Only Memory (ROM), Programmable ROM (PROM), and Erasable Programmable ROM (EPROM). These are used to keep special programs and data, such as the BIOS, that need to be in your computer all the time. ROM is "built-in" computer memory containing data that normally can only be read, not written to (hence the name read only).

ROM contains the programming that allows your computer to be "booted up" or regenerated each time you turn it on. Unlike a computer's random access memory (RAM), the data in ROM is not lost when the computer power is turned off. The ROM is sustained by a small long life battery in your computer called the CMOS battery. If you ever do the hardware setup procedure with your computer, you effectively will be writing to ROM. It is non volatile, but not suited to storage of large quantities of data because it is expensive to produce. Typically, ROM must also be completely erased before it can be rewritten,

PROM (Programmable Read Only Memory)

A variation of the ROM chip is programmable read only memory. PROM can be programmed to record information using a facility known as PROM-programmer. However once the chip has been programmed the recorded information cannot be changed, i.e. the PROM becomes a ROM and the information can only be read.

EPROM (Erasable Programmable Read Only Memory)

As the name suggests the Erasable Programmable Read Only Memory, information can be erased and the chip programmed a new to record different information using a special PROM- Programmer. When EPROM is in use information can only be read and the information remains on the chip until it is erased.



BASIC COMPUTER ORGANIZATION


BASIC COMPUTER ORGANIZATION


A standard fully featured desktop configuration has basically four types of featured devices

1. Input Devices 2. Output Devices 3. Memory 4. Storage Devices



SECONDARY STORAGE

Introduction to CPU

§ CPU

§ The Arithmetic / Logic Unit (ALU)

§ The Control Unit

§ Main Memory

§ External Memory

§ Input / Output Devices

§ The System Bus

CPU OPERATION

The fundamental operation of most CPUs

- To execute a sequence of stored instructions called a program.

1. The program is represented by a series of numbers that are kept in some kind of computer memory.

2. There are four steps that nearly all CPUs use in their operation: fetch, decode, execute, and write back.

3. Fetch:

o Retrieving an instruction from program memory.

o The location in program memory is determined by a program counter (PC)

o After an instruction is fetched, the PC is incremented by the length of the instruction word in terms of memory units.

Decode :

1.The instruction is broken up into parts that have significance to other portions of the CPU.

2.The way in which the numerical instruction value is interpreted is defined by the CPU's instruction set architecture (ISA).

3.Opcode, indicates which operation to perform.

4.The remaining parts of the number usually provide information required for that instruction, such as operands for an addition operation.

5.Such operands may be given as a constant value or as a place to locate a value: a register or a memory address, as determined by some addressing mode.

Execute :

1.During this step, various portions of the CPU are connected so they can perform the desired operation.

2.If, for instance, an addition operation was requested, an arithmetic logic unit (ALU) will be connected to a set of inputs and a set of outputs.

3.The inputs provide the numbers to be added, and the outputs will contain the final sum.

4. If the addition operation produces a result too large for the CPU to handle, an arithmetic overflow flag in a flags register may also be set.

Write back :

1.Simply "writes back" the results of the execute step to some form of memory.

2.Very often the results are written to some internal CPU register for quick access by subsequent instructions.

3.In other cases results may be written to slower, but cheaper and larger, main memory.

Some types of instructions manipulate the program counter rather than directly produce result data.

INPUT DEVICES

Anything that feeds the data into the computer. This data can be in alpha-numeric form which needs

to be keyed-in or in its very basic natural form i.e. hear, smell, touch, see; taste & the sixth sense

…feel?

Typical input devices are:

1. Keyboard 2. Mouse

3. Joystick 4. Digitizing Tablet

5. Touch Sensitive Screen 6. Light Pen

7. Space Mouse 8.Digital Stills Camera

9. Magnetic Ink Character 10.OpticalMarkReader

Recognition (MICR) (OMR)

11. Image Scanner 12. Bar Codes

13. Magnetic Reader 14. Smart Cards

15. Voice Data Entry 16. Sound Capture

17. Video Capture

The Keyboard is the standard data input and operator control device for a computer. It consists of the standard QWERTY layout with a numeric keypad and additional function keys for control purposes.

The Mouse is a popular input device. You move it across the desk and its movement is shown on the screen by a marker known as a 'cursor'. You will need to click the buttons at the top of the mouse to select an option.

Track ball looks like a mouse, as the roller is on the top with selection buttons on the side. It is also a pointing device used to move the cursor and works like a mouse. For moving the cursor in a particular direction, the user spins the ball in that direction. It is sometimes considered better than a mouse, because it requires little arm movement and less desktop space. It is generally used with Portable computers.

Magnetic Ink Character Recognition (MICR) is used to recognize the magnetically charged characters, mainly found on bank cheques. The magnetically charged characters are written by special ink called magnetic ink. MICR device reads the patterns of these characters and compares them with special patterns stored in memory. Using MICR device, a large volume of cheques can be processed in a day. MICR is widely used by the banking industry for the processing of cheques.

The joystick is a rotary lever. Similar to an aircraft's control stick, it enables you to move within the screen's environment, and is widely used in the computer games industry.

A Digitising Tablet is a pointing device that facilitates the accurate input of drawings and designs. A drawing can be placed directly on the tablet, and the user traces outlines or inputs coordinate positions with a hand-held stylus.

A Touch Sensitive Screen is a pointing device that enables the user to interact with the computer by touching the screen. There are three types of Touch Screens: pressure-sensitive, capacitive surface and light beam.

A Light Pen is a pointing device shaped like a pen and is connected to a VDU. The tip of the light pen contains a light-sensitive element which, when placed against the screen, detects the light from the screen enabling the computer to identify the location of the pen on the screen. Light pens have the advantage of 'drawing' directly onto the screen, but this can become uncomfortable, and they are not as accurate as digitising tablets.

The Space mouse is different from a normal mouse as it has an X axis, a Y axis and a Z axis. It can be used for developing and moving around 3-D environments.

Digital Stills Cameras capture an image which is stored in memory within the camera. When the memory is full it can be erased and further images captured. The digital images can then be downloaded from the camera to a computer where they can be displayed, manipulated or printed.

The Optical Mark Reader (OMR) can read information in the form of numbers or letters and put it into the computer. The marks have to be precisely located as in multiple choice test papers.

Scanners allow information such as a photo or text to be input into a computer. Scanners are usually either A4 size (flatbed), or hand-held to scan a much smaller area. If text is to be scanned, you would use an Optical Character Recognition (OCR) program to recognise the printed text and then convert it to a digital text file that can be accessed using a computer.

A Bar Code is a pattern printed in lines of differing thickness. The system gives fast and error-free entry of information into the computer. You might have seen bar codes on goods in supermarkets, in libraries and on magazines. Bar codes provide a quick method of recording the sale of items.

Card Reader: This input device reads a magnetic strip on a card. Handy for security reasons, it provides quick identification of the card's owner. This method is used to run bank cash points or to provide quick identification of people entering buildings.

Smart Card: This input device stores data in a microprocessor embedded in the card. This allows information, which can be updated, to be stored on the card. This method is used in store cards which accumulate points for the purchaser, and to store phone numbers for cellular phones.

OUTPUT DEVICES :

Output devices display information in a way that you can you can understand. The most common output device is a monitor. It looks a lot a like a TV and houses the computer screen. The monitor allows you to 'see' what you and the computer are doing together.

Brief of Output Device

Output devices are pieces of equipment that are used to get information or any other response out from computer. These devices display information that has been held or generated within a computer. Output devices display information in a way that you can understand. The most common output device is a monitor.

Types of Output Device

Printing: Plotter, Printer

Sound : Speakers

Visual : Monitor

A Printer is another common part of a computer system. It takes what you see on the computer screen and prints it on paper. There are two types of printers; Impact Printers and Non-Impact Printers.

Speakers are output devices that allow you to hear sound from your computer. Computer speakers are just like stereo speakers. There are usually two of them and they come in various sizes.




GENERATIONS OF COMPUTERS


GENERATIONS OF COMPUTERS

The Zeroth Generation

The term Zeroth generation is used to refer to the period of development of computing, which predated the commercial production and sale of computer equipment. The period might be dated as extending from the mid-1800s. In particular, this period witnessed the emergence of the first electronics digital computers on the ABC, since it was the first to fully implement the idea of the stored program and serial execution of instructions. The development of EDVAC set the stage for the evolution of commercial computing and operating system software. The hardware component technology of this period was electronic vacuum tubes. The actual operation of these early computers took place without be benefit of an operating system. Early programs were written in machine language and each contained code for initiating operation of the computer itself. This system was clearly inefficient and depended on the varying competencies of the individual programmer as operators.

The First Generation, 1951-1956

The first generation marked the beginning of commercial computing. The first generation was characterized by high-speed vacuum tube as the active component technology. Operation continued without the benefit of an operating system for a time. The mode wa s called "closed shop" and was characterized by the appearance of hired operators who would select the job to be run, initial program load the system, run the user‘s program, and then select another job, and so forth. Programs began to be written in higher level, procedure-oriented languages, and thus the operator‘s routine expanded. The operator now selected a job, ran the translation program to assemble or compile the source program, and combined the translated object program along with any existing library programs that the program might need for input to the linking program, loaded and ran the composite linked program, and then handled the next job in a similar fashion. Application programs were run one at a time, and were translated with absolute computer addresses. There was no provision for moving a program to different location in storage for any reason. Similarly, a program bound to specific devices could not be run at all if any of these devices were busy or broken.

At the same time, the development of programming languages was moving away from the basic machine languages; first to assembly language, and later to procedure oriented languages, the most significant being the development of FORTRAN

The Second Generation, 1956-1964

The second generation of computer hardware was most notably characterized by transistors replacing vacuum tubes as the hardware component technology. In addition, some very important changes in hardware and software architectures occurred during this period. For the most part, computer systems remained card and tape-oriented systems. Significant use of random access devices, that is, disks, did not appear until towards the end of the second generation. Program processing was, for the most part, provided by large centralized computers operated under mono-programmed batch processing operating systems.

The most significant innovations addressed the problem of excessive central processor delay due to waiting for input/output operations. Recall that programs were executed by processing the machine instructions in a strictly sequential order. As a result, the CPU, with its high speed electronic component, was often forced to wait for completion of I/O operations which involved mechanical devices (card readers and tape drives) that were order of magnitude slower.These hardware developments led to enhancements of the operatin g system. I/O and data channel communication and control became functions of the operating system, both to relieve the application. programmer from the difficult details of I/O programming and to pr otect the integrity of the system to provide improved service to users by segmenting jobs and running shorter jobs first (during "prime time") and relegating longer jobs to lower priority or night time runs. System libraries became more widely available and more comprehensive as new utilities and application software components were available to programmers.

The second generation was a period of intense operating system development. Also it was the period for sequential batch processing. Researchers began to experiment with multiprogramming and multiprocessing.

The Third Generation, 1964-1979

The third generation officially began in April 1964 with IBM‘s announcement of its System/360 family of computers. Hardware technology began to use integrated circuits (ICs) which yielded significant advantages in both speed and economy. Operating System development continued with the introduction and widespread adoption of multiprogramming. This marked first by the appearance of more sophisticated I/O buffering in the form of spooling operating systems. These systems worked by introducing two new systems programs, a system reader to move input jobs from cards to disk, and a system writer to move job output from disk to printer, tape, or cards.

The spooling operating system in fact had multiprogramming since more than one program was resident in main storage at the same time. Later this basic idea of multiprogramming was extended to include more than one active user program in memory at time. To accommodate this extension, both the scheduler and the dispatcher were enhanced. In addition, memory management became more sophisticated in order to assure that the program code for each job or at least that part of the code being executed was resident in main storage. Users shared not only the system‘ hardware but also its software resources and file system disk space.

The third generation was an exciting time, indeed, for the development of both computer hardware and the accompanying operating system. During this period, the topic of operating systems became, in reality, a major element of the discipline of computing.

The Fourth Generation, 1979 - Present

The fourth generation is characterized by the appearance of the personal computer and the workstation. Miniaturization of electronic circuits and components continued and Large Scale Integration (LSI), the component technology of the third generation, was replaced by Very Large Scale Integration (VLSI), which characterizes the fourth generation. However, improvements in hardware miniaturization and technology have evolved so fast that we now have inexpensive workstation-class computer capable of supporting multiprogramming and time-sharing. Hence the operating systems that supports today‘s personal computers and workstations look much like those which were available for the minicomputers of the third generation. Examples are Microsoft‘s DOS for IBM-compatible personal computers and UNIX for workstation. However, many of these desktop computers are now connected as networked or distributed systems. Computers in a networked system each have their operating system augmented with communication capabilities that enable users to remotely log into any system on the network and transfer information among machines that are connected to the network. The machines that make up distributed system operate as a virtual single processor system from the user‘s point of view; a central operating system controls and makes transparent the location in the system of the particular processor or processors and file systems that are handling any given program.




Tuesday 10 June 2014

Binary Search Tree Interview Questions


Binary Search Tree

Binary Search tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x. This is called binary-search-tree property.
The basic operations on a binary search tree take time proportional to the height of the tree. For a complete binary tree with node n, such operations runs in (lg n) worst-case time. If the tree is a linear chain of n nodes, however, the same operations takes (n) worst-case time.



The height of the Binary Search Tree equals the number of links from the root node to the deepest node.



Implementation of  Binary Search Tree

Binary Search Tree can be implemented as a linked data structure in which each node is an object with three pointer fields. The three pointer fields left, right and p point to the nodes corresponding to the left child, right child and the parent respectively NIL in any pointer field signifies that there exists no corresponding child or parent. The root node is the only node in the BTS structure with NIL in its p field.


 

 

 

Inorder Tree Walk

During this type of walk, we visit the root of a subtree between the left subtree visit and right subtree visit.
INORDER-TREE-WALK (x)
If x  NIL then
    INORDER-TREE-WALK (left[x])
    print key[x]
    INORDER-TREE-WALK (right[x])

It takes (n) time to walk a tree of n nodes. Note that the Binary Search Tree property allows us to print out all the elements in the Binary Search Tree in sorted order.

 

 

Preorder Tree Walk

In which we visit the root node before the nodes in either subtree.
PREORDER-TREE-WALK (x)
If x not equal NIL then
    PRINT key[x]
    PREORDER-TREE-WALK (left[x])
    PREORDER-TREE-WALK (right[x])

 


Postorder Tree Walk

In which we visit the root node after the nodes in its subtrees.
POSTORDER-TREE-WALk (x)
If x not equal NIL then
    POSTORDER-TREE-WALK (left[x])
    PREORDER-TREE-WALK (right[x])
    PRINT key [x]

It takes O(n) time to walk (inorder, preorder and  pastorder) a tree of n nodes.

 

Binary-Search-Tree property Vs Heap Property

In a heap, a nodes key is greater than equal to both of its children's keys. In binary search tree, a node's key is greater than or equal to its child's key but less than or equal to right child's key. Furthermore, this applies to entire subtree in the binary search tree case. It is very important to note that the heap property does not help print the nodes in sorted order because this property does not tell us in which subtree the next item is. If the heap property could used to print the keys (as we have shown above) in sorted order in O(n) time, this would contradict our known lower bound on comparison sorting.
The last statement implies that since sorting n elements takes Ω(lg n) time in the worst case in the comparison model, any comparison-based algorithm for constructing a Binary Search Tree from arbitrary list n elements takes Ω(lg n) time in the worst case.
We can show the validity of this argument (in case you are thinking of beating Ω(lg n) bound) as follows: let c(n) be the worst-case running time for constructing a binary tree of  a set of n elements. Given an n-node BST, the inorder walk in the tree outputs the keys in sorted order (shown above). Since the worst-case running time of any computation based sorting algorithm is Ω(lg n) , we have

                    
c(n) + O(n) = Ω(n lgn)
Therefore,                c(n) = Ω(lgn).

 



Querying a Binary Search Tree

The most common operations performed on a BST is searching for a key stored in the tree. Other operations are MINIMUM, MAXIMUM, SUCCESSOR and PREDESESSOR. These  operations run in O(h) time where h is the height of the tree i.e., h is the number of links root node to the deepest node.
The TREE-SEARCH (x, k) algorithm searches the tree root at for a node whose key value equals k. It returns a pointer to the node if it exists otherwise NIL
TREE-SEARCH (x, k)
if x = NIL     .OR.     k = key[x]
    then return x
if k < key[x]
    then return TREE-SEARCH (left[x], k)
    else return TREE-SEARCH (right[x], k)


Clearly, this algorithm runs in O(h) time where h is the height of the tree. 
The iterative version of above algorithm is very easy to implement.
ITERATIVE-TREE-SEARCH (x, k)
  1. while x not equal NIL     .AND.     key ≠ key[x] do
  2.          if k < key [x]
  3.                  then x  left[x]
  4.                  else x  right [x]
  5. return x

 


The TREE-MINIMUN (x) algorithm returns a point to the node of the tree at x whose key value is the minimum of all keys in the tree. Due to BST property, an minimum element can always be found by following left child pointers from the root until NIL is uncountered.
TREE-MINIMUM (x)
while left[x] ≠ NIL do
    x  left [x]
return x
Clearly, it runs in O(h) time where h is the height of the tree. Again thanks to BST property, an element in a binary search tree whose key is a maximum can always be found by following right child pointers from root until a NIL is encountered.
TREE-MAXIMUM (x)
while right[x] ≠ NIL do
    x  right [x]
return x
Clearly, it runs in O(h) time where h is the height of the tree.
The TREE-SUCCESSOR (x) algorithm returns a pointer to the node in the tree whose key value is next higher than key [x].
TREE-SUCCESSOR (x)
if right [x] ≠ NIL
    then return TREE-MINIMUM (right[x])
    else y  p[x]
        while y ≠ NIL     .AND.    x = right[y] do
                x  y
                y  p[y]
        return y

Note that algorithm TREE-MINIMUM, TRE-MAXIMUM, TREE-SUCCESSOR, and TREE-PREDESSOR never look at the keys.
An inorder tree walk of an n-node BST can be implemented in (n)-time by finding the minimum element in the tree with TREE-MINIMUM (x) algorithm and then making n-1 calls to TREE-SUCCESSOR (x).

Another way of Implementing Inorder walk on Binary Search Tree

Algorithm
  • find the minimum element in the tree with TREE-MINIMUM
  • Make n-1 calls to TREE-SUCCESSOR

Let us show that this algorithm runs in (n) time. For a tree T, let mT be the number of edges that are traversed by the above algorithm. The running time of the algorithm for T is (mT). We make following claim:
mT is zero if T has at most one node and 2e - r otherwise, where e is
the number of edges in the tree and 
r is the length of the path from
root to the node holding the maximum key.
Note that e = n - 1 for any tree with at least one node. This allows us to prove the claim by induction on e (and therefore, on n).
Base case   Suppose that e = 0. Then, either the tree is empty or consists only of a single node. So, e = r = 0. Therefore, the claim holds.
Inductive step    Suppose e > 0 and assume that the claim holds for all e' < e. Let T be a binary search tree with e edges. Let x be the root, and T1 and T2 respectively be the left and right subtree of x. Since T has at least one edge, either T1 or T2 respectively is nonempty. For each i = 1, 2, let ei be the number of edges in Ti, pi the node holding the maximum key in Ti, and ri the distance from pi to the root of Ti. Similarly, let ep and r be the correspounding values for T. First assume that both T1 and T2 are nonempty. Then e = e1 + e2 + 2, p = p2, and r = r2 + 1. The action of the enumeration is as follows:
  • Upon being called, the minimum-tree(x) traverses the left branch of x and enters T1.
  • Once the root of T1 is visited, the edges of T1 are traversed as if T1 is the input tree. This situation will last until p1 is visisted.
  • When the Tree-Successor is called form p1. The upward path from p1 and x is traversed and x is discovered to hold the successor.
  • When the tree-Successor called from x, the right branch of x is taken.
  • Once the root of T2 is visited, the edges of T2 are traversed as if T2 is the input tree. This situation will last until p2 is reached, whereby the algorithm halts.
By the above analysis, the number of edges that are traversed by the above algorithm, mT, is
mT = 1 + (2e1 - r1) + (r1 + 1) + 1 + (2e2 - r2)
      = 2(e1 + e2 + 2) - (r2 + 1)
      = 2e -r
Therefore, the claim clearly holds for this case.

 

Next suppose that T2 is emply. Since e > 0, T1 is nonempty. Then e = e1 + 1. Since x does not have a right child, x holds the maximum. Therefore, p = x and r = 0. The action of the enumeration algorithm is the first two steps. Therefore, the number of edges that are traversed by the algorithm in question is
m= 1 + (2e1 - r1) + ( r1 +1)
      = 2(e1 + 1) - 0
      = 2e - r
Therefore, the claim holds for this case.

Finally, assume that T1 is empty. Then T2 is nonempty. It holds that 
e = e2 + 1p = p2, and r = r2 + 1. This time x holds the minimum key and the action of the enumeration algorithm is the last two steps. Therefore, the number of edges that are traversed by the algorithm is
mT = 1 + (2e2 - r2)
      = 2(e2+1) - (r2 + 1)
      = 2e -r
Therefore, the claim holds for this case.

The claim is proven since 
e = n - 1mT    2n. On the other hand, at least one edge has to be traversed when going from on node to another, so m   n - 1. Therefore, the running time of the above algorithm is (n).

Consider any binary search tree T and let y be the parent of a leaf z. Our goal is to show that key[y] is
either   the smallest key in T larger than key[x]
or          the largest key in the T smaller than key[x].

Proof        Suppose that x is a left child of y. Since key[y key[x], only we have to show that there is no node z with key[y] > key[z] > key[x]. Assume, to the contrary, that there is such a z. Choose z so that it holds the smallest key among such nodes. Note for every node  zx, key[z  dey[u] if and only if key[x  key[u]. If we search key[z], then the search path is identical to that of key[x] until the path rearches z or x. Since x is a leaf (meaning it has no children), the search path never reaches x. Therefore,  z is an ancestor of x. Since y is the parent of x (it is given, in case you've forgotton!) and is not zz has to be an ancestor of y. So, key[y] > dey[z] >dey[x]. However, we are assuming key[y] > key[z] > key[x], so this is clearly impossible. Therefore, there is no such z
The case when x is a right child of y is easy. Hint: symmetric. 

INSERTION

To insert a node into a BST
  1. find a leaf st the appropriate place and
  2. connect the node to the parent of the leaf. 

TREE-INSERT (T, z)
 NIL
 root [T]
while x ≠ NIL do
    y  x
    if key [z]  key[x]
        then x  left[x]
        else x  right[x]
p[z]  y
if y = NIL
    then root [T]  z
    else if key [z] < key [y]
        then left [y]  z
        else right [y]  z

Like other primitive operations on search trees, this algorithm begins at the root of the tree and traces a path downward. Clearly, it runs in O(h) time on a tree of height h.

 

Sorting

We can sort a given set of n numbers by first building a binary search tree containing these number by using TREE-INSERT (x) procedure repeatedly to insert the numbers one by one and then printing the numbers by an inorder tree walk.

Analysis

Best-case running time
Printing takes O(n) time and n insertion cost O(lg n) each (tree is balanced, half the insertions are at depth lg(n) -1). This gives the best-case running time O(n lg n).
 
Worst-case running time
Printing still takes O(n) time and n insertion costing O(n) each (tree is a single chain of nodes) is O(n2). The n insertion cost 1, 2, 3, . . . n, which is arithmetic sequence so it is n2/2.

 

 

Deletion

Removing a node from a BST is a bit more complex, since we do not want to create any "holes" in the tree. If the node has one child then the child is spliced to the parent of the node. If the node has two children then its successor has no left child; copy the successor into the node and delete the successor instead TREE-DELETE (T, z) removes the node pointed to by z from the tree T. IT returns a pointer to the node removed so that the node can be put on a free-node list, etc.
TREE-DELETE (T, z)
  1. if left [z] = NIL    .OR.     right[z] = NIL
  2.     then y  z
  3.     else y  TREE-SUCCESSOR (z)
  4. if left [y] ≠ NIL
  5.     then x  left[y]
  6.     else x  right [y]
  7. if x ≠ NIL
  8.     then p[x]  p[y]
  9. if p[y] = NIL
  10.     then root [T]  x
  11.     else if y = left [p[y]]
  12.         then left [p[y]]  x
  13.         else right [p[y]]  x
  14. if y ≠ z
  15.     then key [z]  key [y]
  16.         if y has other field, copy them, too
  17. return y

The procedure runs in O(h) time on a tree of height h.

Virtual Memory Inter View Questions



Virtual Memory Inter View Questions

Source - 1

Definition of:virtual memory

Simulating more random access memory (RAM) than actually exists, allowing the computer to run larger programs and multiple programs concurrently. A common function in most every OS and hardware platform, virtual memory uses the hard disk to temporarily hold what was in real memory.

Virtual memory allows multiple programs to load in memory at the same time. Each application addresses memory starting at zero, but virtual memory takes control of the memory addressing and lets each application function as if it had unlimited memory.

Note that virtual "memory" and virtual "machine" are not the same. Virtual memory is used all the time, whereas a virtual machine is an optional approach for running applications (see virtual machine).

Virtual Memory Pages
The computer's real memory is broken up into smaller segments, called "pages," typically 4KB in size. When real memory fills up, pages not currently in use by open applications are written to a virtual memory "swap file" on the disk for temporary storage. When any swapped out page is required again, once again a page in real memory is written to the disk to make room, and the disk page is retrieved. Memory is the computer's workspace, and since there is often a hundred times more disk space than memory space, virtual memory dramatically increases the computer's capacity to do work. However, there is a penalty. When a user has too many open programs, there can be excessive amounts of page swapping, causing applications to slow down. In addition, switching between applications is no longer immediate (see thrashing).

Hardware Is Required
Virtual memory can be implemented in software only, but efficient operation requires specialized hardware circuits. All modern, general-purpose CPUs have memory management units (MMUs) that support virtual memory. They provide "page tables" that are used to translate between the program's "virtual" addresses and the "real" addresses in memory and disk, which may change at any time. Although a program may initially load as a contiguous block of code, it can wind up in pages randomly scattered around real memory.

Virtual memory claims are sometimes made for specific applications that bring additional parts of the program in as needed; however, true virtual memory is built into the operating system and hardware and works with all applications. See Windows swap file.





Memory Is Extended to Disk
Virtual memory allows more programs to be opened simultaneously by using the hard disk as temporary storage of memory pages.






Page Out, Page In
When memory is full and the current program needs instructions that are not in memory, pages are swapped. In this example, program A needs a page from the disk, and a page from program C is swapped out to make room.

Source - 2


Memory is hardware that your computer uses to load the operating system and run programs. It consists of one or more RAM chips that each have several memory modules. The amount of real memory in a computer is limited to the amount of RAM installed. Common memory sizes are 256MB, 512MB, and 1GB.

Because your computer has a finite amount of RAM, it is possible to run out of memory when too many programs are running at one time. This is where virtual memory comes in. Virtual memory increases the available memory your computer has by enlarging the "address space," or places in memory where data can be stored. It does this by using hard disk space for additional memory allocation. However, since the hard drive is much slower than the RAM, data stored in virtual memory must be mapped back to real memory in order to be used.

The process of mapping data back and forth between the hard drive and the RAM takes longer than accessing it directly from the memory. This means that the more virtual memory is used, the more it will slow your computer down. While virtual memory enables your computer to run more programs than it could otherwise, it is best to have as much physical memory as possible. This allows your computer to run most programs directly from the RAM, avoiding the need to use virtual memory. Having more RAM means your computer works less, making it a faster, happier machine.