Mergesort

Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.

Idea:

• Divide the unsorted list into N sublists, each containing 1 element.
• Take adjacent pairs of two singleton lists and merge them to form a list of 2 elements. N will now convert into N/2 lists of size 2.
• Repeat the process till a single sorted list of obtained.

While comparing two sublists for merging, the first element of both lists is taken into consideration. While sorting in ascending order, the element that is of a lesser value becomes a new element of the sorted list. This procedure is repeated until both the smaller sublists are empty and the new combined sublist comprises all the elements of both the sublists.

As one may understand from the image above, at each step a list of size M is being divided into 2 sublists of size M/2, until no further division can be done. 

To understand better, consider a smaller array A containing the elements (9,7,8).

At the first step this list of size 3 is divided into 2 sublists the first consisting of elements (9,7) and the second one being (8).

 Now, the first list consisting of elements (9,7) is further divided into 2 sublists consisting of elements (9) and (7) respectively.

As no further breakdown of this list can be done, as each sublist consists of a maximum of 1 element, we now start to merge these lists.

 The 2 sub-lists formed in the last step are then merged together in sorted order using the procedure mentioned above leading to a new list (7,9). Backtracking further, we then need to merge the list consisting of element (8) too with this list, leading to the new sorted list (7,8,9).

An implementation has been provided below :

 void merge(int A[ ] , int start, int mid, int end) {

 //stores the starting position of both parts in temporary variables.

int p = start ,q = mid+1;

int Arr[end-start+1] , k=0;

for(int i = start ;i <= end ;i++) {

    if(p > mid)      //checks if first part comes to an end or not .

       Arr[ k++ ] = A[ q++] ;

   else if ( q > end)   //checks if second part comes to an end or not

       Arr[ k++ ] = A[ p++ ];

   else if( A[ p ] < A[ q ])     //checks which part has smaller element.

      Arr[ k++ ] = A[ p++ ];

   else

      Arr[ k++ ] = A[ q++];

 }

  for (int p=0 ; p< k ;p ++) {

   /* Now the real array has elements in sorted manner including both

        parts.*/

     A[ start++ ] = Arr[ p ] ;                         

  }

}

Here, in merge function, we will merge two parts of the arrays where one part has starting and ending positions from start to mid respectively and another part has positions from mid+1 to the end.

A beginning is made from the starting parts of both arrays. i.e. p and q. Then the respective elements of both the parts are compared and the one with the smaller value will be stored in the auxiliary array (Arr[ ]). If at some condition ,one part comes to end ,then all the elements of another part of array are added in the auxiliary array in the same order they exist.

Now consider the following 2 branched recursive function :

   void merge_sort (int A[ ] , int start , int end )

   {

           if( start < end ) {

           int mid = (start + end ) / 2 ;           // defines the current array in 2 parts .

           merge_sort (A, start , mid ) ;                 // sort the 1st part of array .

           merge_sort (A,mid+1 , end ) ;              // sort the 2nd part of array.

         // merge the both parts by comparing elements of both the parts.

          merge(A,start , mid , end );  

   }                   

}

Time Complexity:
The list of size N is divided into a max of logN parts, and the merging of all sublists into a single list takes O(N) time, the worst case run time of this algorithm is O(NLogN)

question

Question of software engineering

1.       Explain waterfall  model in detail.

2.       Explain prototype  model in detail.

3.       Explain the spiral model in detail. What is the difference between the waterfall model and the spiral model?

4.       Explain COCOMO model in brief.

5.       What is testing? What are the different types of testing?

6.       Explain verification and validation testing.

7.       What is difference between white box and black box testing?

8.       What is software relaibilty? What are different reliability metrics?

9.       Write different types of integration testing.

10.   Write short notes on

a.       LOC              b. function point             c. DFD

d. E-R diagram

assignment

                                                                 Assignment

1.       Write a program in C to enter a number from user and check whether a number is positive or negative.

2.       Write a program in C to enter three coefficients from user and find roots by a quadratic equation.

3.       Write a program in C to print 1 to 100.

4.       Write a program in C to print even numbers between 1 to 100.

5.       Write a program in C to print sum of even numbers between 1 to 100.

6.       Write a program in C to enter a number from user and display its reverse.

7.       Write a program in C to enter a number from user and check whether a number is prime or not.

8.       Write a program in C display the multiplication table of any no.

9.       Write a program in C to enter a string from user and copy it to another string.

10.   Write a program in C to enter a string from user and find its length.

11.   Write a function in C to calculate factorial of a number.

12.   Write a program in C to store ten numbers from user in one-dimensional array and find its sum and average.

13.   Write a program in C to store ten numbers from user in one-dimensional array and find largest of them.

14.   Write a program in C to store nine [3 x 3] elements in two-dimensional array and display them.

15.   Write a program in C to store ten records in one-dimensional array. Record contains Roll Number and name. And display all records.

question

Practice following questions

1.       Write a program in JAVA to enter a number from user and check whether a number is positive or negative.

2.       Write a program in JAVA to enter three coefficients from a user and find roots by quadratic equation.

3.       Write a program in JAVA to print 1 to 100.

4.       Write a program in JAVA to print even numbers between 1 to 100.

5.       Write a program in JAVA to print sum of even numbers between 1 to 100.

6.       Write a program in JAVA to enter a number from the user and display its reverse.

7.       Write a program in JAVA to enter a number from user and check whether a number is prime or not.

8.       Write a program in JAVA display the multiplication table of any no.

9.       Write a program in JAVA to enter a string from user and copy it to another string.

10.   Write a program in JAVA to enter a string from user and find its length.

11.   Write a function in JAVA to calculate factorial of a number.

12.   Write a program in JAVA to store ten numbers from user in one-dimensional array and find its sum and average.

13.   Write a program in JAVA to store ten numbers from user in one-dimensional array and find largest of them.

14.   Write a program in JAVA to store nine [3 x 3] elements in two-dimensional array and display them.

Datatransmission

*Signals

When data is sent over physical medium, it needs to be first converted into electromagnetic signals. Data itself can be analog such as human voice, or digital such as file on the disk.Both analog and digital data can be represented in digital or analog signals.

·      Digital Signals

Digital signals are discrete in nature and represent sequence of voltage pulses. Digital signals are used within the circuitry of a computer system.

·      Analog Signals

Analog signals are in continuous wave form in nature and represented by continuous electromagnetic waves.

*Transmission Impairment

When signals travel through the medium they tend to deteriorate. This may have many reasons as given:

·      Attenuation

For the receiver to interpret the data accurately, the signal must be sufficiently strong.When the signal passes through the medium, it tends to get weaker.As it covers distance, it loses strength.

·      Dispersion

As signal travels through the media, it tends to spread and overlaps. The amount of dispersion depends upon the frequency used.

·      Delay distortion

Signals are sent over media with pre-defined speed and frequency. If the signal speed and frequency do not match, there are possibilities that signal reaches destination in arbitrary fashion. In digital media, this is very critical that some bits reach earlier than the previously sent ones.

·      Noise

Random disturbance or fluctuation in analog or digital signal is said to be Noise in signal, which may distort the actual information being carried. Noise can be characterized in one of the following class:

o   Thermal Noise

Heat agitates the electronic conductors of a medium which may introduce noise in the media. Up to a certain level, thermal noise is unavoidable.

o   Intermodulation

When multiple frequencies share a medium, their interference can cause noise in the medium. Intermodulation noise occurs if two different frequencies are sharing a medium and one of them has excessive strength or the component itself is not functioning properly, then the resultant frequency may not be delivered as expected.

o   Crosstalk

This sort of noise happens when a foreign signal enters into the media. This is because signal in one medium affects the signal of second medium.

o   Impulse

This noise is introduced because of irregular disturbances such as lightening, electricity, short-circuit, or faulty components. Digital data is mostly affected by this sort of noise.

*Transmission Media

The media over which the information between two computer systems is sent, called transmission media. Transmission media comes in two forms.

·      Guided Media

All communication wires/cables are guided media, such as UTP, coaxial cables, and fiber Optics. In this media, the sender and receiver are directly connected and the information is send (guided) through it.

·      Unguided Media

Wireless or open air space is said to be unguided media, because there is no connectivity between the sender and receiver. Information is spread over the air, and anyone including the actual recipient may collect the information.

*Channel Capacity

The speed of transmission of information is said to be the channel capacity. We count it as data rate in digital world. It depends on numerous factors such as:

·      Bandwidth:  The physical limitation of underlying media.

·      Error-rate:  Incorrect reception of information because of noise.

·      Encoding:  The number of levels used for signaling.

*Data

Data or information can be stored in two ways, analog and digital. For a computer to use the data, it must be in discrete digital form.Similar to data, signals can also be in analog and digital form. To transmit data digitally, it needs to be first converted to digital form.

*Digital-to-Digital Conversion

This section explains how to convert digital data into digital signals. It can be done in two ways, line coding and block coding. For all communications, line coding is necessary whereas block coding is optional.

Line Coding

The process for converting digital data into digital signal is said to be Line Coding. Digital data is found in binary format.It is represented (stored) internally as series of 1s and 0s.

Digital signal is denoted by discreet signal, which represents digital data.There are three types of line coding schemes available:

Uni-polar Encoding

Unipolar encoding schemes use single voltage level to represent data. In this case, to represent binary 1, high voltage is transmitted and to represent 0, no voltage is transmitted. It is also called Unipolar-Non-return-to-zero, because there is no rest condition i.e. it either represents 1 or 0.

Polar Encoding

Polar encoding scheme uses multiple voltage levels to represent binary values. Polar encodings is available in four types:

·      Polar Non-Return to Zero (Polar NRZ)

It uses two different voltage levels to represent binary values. Generally, positive voltage represents 1 and negative value represents 0. It is also NRZ because there is no rest condition.

NRZ scheme has two variants: NRZ-L and NRZ-I.

NRZ-L changes voltage level at when a different bit is encountered whereas NRZ-I changes voltage when a 1 is encountered.

·       Return to Zero (RZ)

Problem with NRZ is that the receiver cannot conclude when a bit ended and when the next bit is started, in case when sender and receiver’s clock are not synchronized.

RZ uses three voltage levels, positive voltage to represent 1, negative voltage to represent 0 and zero voltage for none. Signals change during bits not between bits.

·       Manchester

This encoding scheme is a combination of RZ and NRZ-L. Bit time is divided into two halves. It transits in the middle of the bit and changes phase when a different bit is encountered.

·       Differential Manchester

This encoding scheme is a combination of RZ and NRZ-I. It also transit at the middle of the bit but changes phase only when 1 is encountered.

Block Coding

To ensure accuracy of the received data frame redundant bits are used. For example, in even-parity, one parity bit is added to make the count of 1s in the frame even. This way the original number of bits is increased. It is called Block Coding.

Block coding is represented by slash notation, mB/nB.Means, m-bit block is substituted with n-bit block where n > m. Block coding involves three steps:

• Division,
• Substitution
• Combination.

After block coding is done, it is line coded for transmission

*Analog-to-Digital Conversion

Microphones create analog voice and camera creates analog videos, which are treated is analog data. To transmit this analog data over digital signals, we need analog to digital conversion.

Analog data is a continuous stream of data in the wave form whereas digital data is discrete. To convert analog wave into digital data, we use Pulse Code Modulation (PCM).

PCM is one of the most commonly used method to convert analog data into digital form. It involves three steps:

• Sampling
• Quantization
• Encoding.

Sampling

The analog signal is sampled every T interval. Most important factor in sampling is the rate at which analog signal is sampled. According to Nyquist Theorem, the sampling rate must be at least two times of the highest frequency of the signal.

Quantization

Sampling yields discrete form of continuous analog signal. Every discrete pattern shows the amplitude of the analog signal at that instance. The quantization is done between the maximum amplitude value and the minimum amplitude value. Quantization is approximation of the instantaneous analog value.

Encoding

In encoding, each approximated value is then converted into binary format.

*Data Transmission

The transmission mode decides how data is transmitted between two computers.The binary data in the form of 1s and 0s can be sent in two different modes: Parallel and Serial.

Parallel Transmission

The binary bits are organized in-to groups of fixed length. Both sender and receiver are connected in parallel with the equal number of data lines. Both computers distinguish between high order and low order data lines. The sender sends all the bits at once on all lines.Because the data lines are equal to the number of bits in a group or data frame, a complete group of bits (data frame) is sent in one go. Advantage of Parallel transmission is high speed and disadvantage is the cost of wires, as it is equal to the number of bits sent in parallel.

Serial Transmission

In serial transmission, bits are sent one after another in a queue manner. Serial transmission requires only one communication channel.

Serial transmission can be either asynchronous or synchronous.

Asynchronous Serial Transmission

It is named so because there’is no importance of timing. Data-bits have specific pattern and they help receiver recognize the start and end data bits.For example, a 0 is prefixed on every data byte and one or more 1s are added at the end.

Two continuous data-frames (bytes) may have a gap between them.

Synchronous Serial Transmission

Timing in synchronous transmission has importance as there is no mechanism followed to recognize start and end data bits.There is no pattern or prefix/suffix method. Data bits are sent in burst mode without maintaining gap between bytes (8-bits). Single burst of data bits may contain a number of bytes. Therefore, timing becomes very important.

It is up to the receiver to recognize and separate bits into bytes.The advantage of synchronous transmission is high speed, and it has no overhead of extra header and footer bits as in asynchronous transmission.

---------------------------------------------------------

To send the digital data over an analog media, it needs to be converted into analog signal.There can be two cases according to data formatting.

Bandpass:The filters are used to filter and pass frequencies of interest. A bandpass is a band of frequencies which can pass the filter.

Low-pass: Low-pass is a filter that passes low frequencies signals.

When digital data is converted into a bandpass analog signal, it is called digital-to-analog conversion. When low-pass analog signal is converted into bandpass analog signal, it is called analog-to-analog conversion.

Digital-to-Analog Conversion

When data from one computer is sent to another via some analog carrier, it is first converted into analog signals. Analog signals are modified to reflect digital data.

An analog signal is characterized by its amplitude, frequency, and phase. There are three kinds of digital-to-analog conversions:

·      Amplitude Shift Keying

In this conversion technique, the amplitude of analog carrier signal is modified to reflect binary data.

When binary data represents digit 1, the amplitude is held; otherwise it is set to 0. Both frequency and phase remain same as in the original carrier signal.

·      Frequency Shift Keying

In this conversion technique, the frequency of the analog carrier signal is modified to reflect binary data.

This technique uses two frequencies, f1 and f2. One of them, for example f1, is chosen to represent binary digit 1 and the other one is used to represent binary digit 0. Both amplitude and phase of the carrier wave are kept intact.

·      Phase Shift Keying

In this conversion scheme, the phase of the original carrier signal is altered to reflect the binary data.

When a new binary symbol is encountered, the phase of the signal is altered. Amplitude and frequency of the original carrier signal is kept intact.

·      Quadrature Phase Shift Keying

QPSK alters the phase to reflect two binary digits at once. This is done in two different phases. The main stream of binary data is divided equally into two sub-streams. The serial data is converted in to parallel in both sub-streams and then each stream is converted to digital signal using NRZ technique. Later, both the digital signals are merged together.

Analog-to-Analog Conversion

Analog signals are modified to represent analog data. This conversion is also known as Analog Modulation. Analog modulation is required when bandpass is used. Analog to analog conversion can be done in three ways:

·      Amplitude Modulation

In this modulation, the amplitude of the carrier signal is modified to reflect the analog data.

Amplitude modulation is implemented by means of a multiplier. The amplitude of modulating signal (analog data) is multiplied by the amplitude of carrier frequency, which then reflects analog data.

The frequency and phase of carrier signal remain unchanged.

·      Frequency Modulation

In this modulation technique, the frequency of the carrier signal is modified to reflect the change in the voltage levels of the modulating signal (analog data).

The amplitude and phase of the carrier signal are not altered.

·      Phase Modulation

In the modulation technique, the phase of carrier signal is modulated in order to reflect the change in voltage (amplitude) of analog data signal.

Phase modulation is practically similar to Frequency Modulation, but in Phase modulation frequency of the carrier signal is not increased. Frequency of carrier is signal is changed (made dense and sparse) to reflect voltage change in the amplitude of modulating signal.