Algorithms- correctness of algorithms

Question 1

I/O interface

Answer 1

transfer information between internal storage and external I/O devices is known as I/O interface. The CPU is interfaced using special communication links by the peripherals connected to any computer system. These communication links are used to resolve the differences between CPU and peripheral. There exists special hardware components between CPU and peripherals to supervise and synchronize all the input and output transfers that are called interface units.

Question 2

Mode of transfer in I/O:
The binary information that is received from an external device is usually stored in the memory unit. The information that is transferred from the CPU to the external device is originated from the memory unit. CPU merely processes the information but the source and target is always the memory unit. Data transfer between CPU and the I/O devices may be done in different modes. Data transfer to and from the peripherals may be done in any of the three possible ways

Answer 2

Programmed I/O.
Interrupt- initiated I/O.
Direct memory access( DMA).

Question 3

programmed I/O

Answer 3

It is due to the result of the I/O instructions that are written in the computer program. Each data item transfer is initiated by an instruction in the program. Usually the transfer is from a CPU register and memory. In this case it requires constant monitoring by the CPU of the peripheral devices.
Example of Programmed I/O: In this case, the I/O device does not have direct access to the memory unit. A transfer from I/O device to memory requires the execution of several instructions by the CPU, including an input instruction to transfer the data from device to the CPU and store instruction to transfer the data from CPU to memory. In programmed I/O, the CPU stays in the program loop until the I/O unit indicates that it is ready for data transfer. This is a time consuming process since it needlessly keeps the CPU busy. This situation can be avoided by using an interrupt facility. This is discussed below.

Question 4

Interrupted- initiated I/O

Answer 4

the CPU can be kept busy unnecessarily. This situation can very well be avoided by using an interrupt driven method for data transfer. By using interrupt facility and special commands to inform the interface to issue an interrupt request signal whenever data is available from any device. In the meantime the CPU can proceed for any other program execution. The interface meanwhile keeps monitoring the device. Whenever it is determined that the device is ready for data transfer it initiates an interrupt request signal to the computer. Upon detection of an external interrupt signal the CPU stops momentarily the task that it was already performing, branches to the service program to process the I/O transfer, and then return to the task it was originally performing.

Question 5

The I/O transfer rate is limited by the

Answer 5

speed with which the processor can test and service a device.

Question 6

The processor is tied up in managing an I/O transfer; a number of instructions must be executed for each

Answer 6

I/O transfer

Question 7

Hardware Interrupts

Answer 7

Interrupts present in the hardware pins.

Question 8

Software interrupts

Answer 8

These are the instructions used in the program whenever the required functionality is needed.

Question 9

Vectored interrupts

Answer 9

These interrupts are associated with the static vector address.

Question 10

Non-vectored interrupts

Answer 10

These interrupts are associated with the dynamic vector address.

Question 11

Maskable interrupts

Answer 11

These interrupts can be enabled or disabled explicitly.

Question 12

Non-maskable interrupts

Answer 12

These are always in the enabled state. we cannot disable them.

Question 13

external interrupts

Answer 13

Generated by external devices such as I/O.

Question 14

internal interrupts

Answer 14

These devices are generated by the internal components of the processor such as power failure, error instruction, temperature sensor, etc.

Question 15

synchronous interrupts

Answer 15

These interrupts are controlled by the fixed time interval. All the interval interrupts are called as synchronous interrupts.

Question 16

Asynchronous interrupts

Answer 16

These are initiated based on the feedback of previous instructions. All the external interrupts are called as asynchronous interrupts.

Question 17

Direct memory access

Answer 17

The data transfer between a fast storage media such as magnetic disk and memory unit is limited by the speed of the CPU. Thus we can allow the peripherals directly communicate with each other using the memory buses, removing the intervention of the CPU. This type of data transfer technique is known as DMA or direct memory access. During DMA the CPU is idle and it has no control over the memory buses. The DMA controller takes over the buses to manage the transfer directly between the I/O devices and the memory unit.

Bus grant request time.

Transfer the entire block of data at transfer rate of device because the device is usually slow than the speed at which the data can be transferred to CPU.

Release the control of the bus back to CPU So, total time taken to transfer the N bytes = Bus grant request time + (N) * (memory transfer rate) + Bus release control time.

Buffer the byte into the buffer

Inform the CPU that the device has 1 byte to transfer (i.e. bus grant request)

Transfer the byte (at system bus speed)

Release the control of the bus back to CPU.

Question 18

Advantage of I/O:
Standardization

Answer 18

I/O interfaces provide a standard way of communicating with external devices. This means that different devices can be connected to a computer using the same interface, which makes it easier to swap out devices and reduces the need for specialized hardware.

Question 19

Advantage of I/O:
Modularity

Answer 19

With I/O interfaces, different devices can be added or removed from a computer without affecting the other components. This makes it easier to upgrade or replace a faulty device without affecting the rest of the system.

Question 20

Advantage of I/O:
Efficiency

Answer 20

I/O interfaces can transfer data between the computer and the external devices at high speeds, which allows for faster data transfer and processing times.

Question 21

Advantage of I/O:
Compatibility

Answer 21

I/O interfaces are designed to be compatible with a wide range of devices, which means that users can choose from a variety of devices that are compatible with their computer’s I/O interface.

Question 22

Disadvantes of I/O:

Cost: I/O interfaces can be expensive, especially if specialized hardware is required to connect a particular device to a computer system.

Complexity: Some I/O interfaces can be complex to configure and require specialized knowledge to set up and maintain. This can be a disadvantage for users who are not familiar with the technical aspects of computer hardware.

Answer 22

Compatibility issues: While I/O interfaces are designed to be compatible with a wide range of devices, there can still be compatibility issues with certain devices. In some cases, device drivers may need to be installed to ensure proper functionality.

Security risks: I/O interfaces can be a security risk if they are not properly configured or secured. Hackers can exploit vulnerabilities in I/O interfaces to gain unauthorized access to a computer system or steal data.

Question 23

Direct Memory Access (DMA)

Answer 23

feature of computer systems that allows certain hardware subsystems to access main system memory independently of the central processing unit (CPU).

Question 24

An “empirical” analysis is one based on actual experimentation and observation of the results. In the world of algorithms, that means the algorithm must actually be translated into a programming language and executed on a computer.
Let’s conduct an empirical analysis of an algorithm that finds the maximum value in a list of numbers.
Here’s pseudocode that expresses that algorithm:

maxNum ← -1
FOR num IN numbers {
if (num > maxNum) {
maxNum ← num
}
}

Answer 24

Next, we’ll translate that into the JavaScript language with four levels of empirical analysis:

function findMaxVal(numbers) {
var maxNum = numbers[0];
for (var i = 0; i < numbers.length; i++) {
if (numbers[i] > maxNum) {
maxNum = numbers[i];
}
}
return maxNum;
}
Program.assertEqual(
findMaxVal([-13, -4, -24, -7]),
-4);
Program.assertEqual(
findMaxVal([13, 4, 24, 7]),
24);
Program.assertEqual(
findMaxVal([13, -4, 24, -7]),
24);
Program.assertEqual(
findMaxVal([5/2, -2.22, Math.PI, 99]),
99);

Question 25

One form of reasoning is a “proof by induction”, a technique that’s also used by mathematicians to prove properties of numerical sequences.

Answer 25

pseudocode for an algorithm that computes the factorial of a positive integer:

PROCEDURE calcFactorial(n) {
factorial ← 1
i ← 1
REPEAT UNTIL (i > n) {
factorial ← factorial * i
i ← i + 1
}
RETURN factorial
}

The factorial of a number is the product of that number with all the numbers less than it, down to 1. For example, the factorial of 4 or 4! is
4×3×2×1=24

Before we go down the route of proving this algorithm successfully computes n!, let’s actually try it out for the n of
4. If the algorithm works, it should return 24.

The variables factorial and i both start off at 1.

Since i (1) is not greater than n (4), we enter the loop.

Iteration #1: factorial is set to 1 (from 1 * 1) and i increases to 2.

Iteration #2: factorial is set to 2 (from 1 * 2) and i increases to 3.

Iteration #3: factorial is set to 6 (from 2 * 3) and i increases to 4.

Iteration #4: factorial is set to 24 (from 6 * 4) and i increases to 5.

At this point, i (5) is greater than n (4), so we exit the loop.

The procedure returns the value of 24.

Great, we verified that the algorithm computes the correct result for a single integer.

Base case: This is where we verify that the algorithm holds for the very first number in the range of possible inputs.

Induction step: This is where we show that if it works for any arbitrary number, it also works for the number right after it.