Data Structure



Data Structure Unit 1 !!

1. What is Data Structure ? What are basic Types of Data Structure ? Support your answers with diagrams if needed.
	Data Structure is way to store and structure the data in a view that it should take less time to access the data and occupy less space to store the data. Data structure refers to how the data are to be stored rather than what data are to be stored. It provides basis model of processing the data. 


1.1 DATA STRUCTURE INTRODUCTION
Data structure is the representation of the logical relationship between individual elements of data. It is a way of organizing all data items that considers not only the elements stored but also their relationship to each other. 
 
Data Structure Specifies :
1. Organizing of Data
2. Accessing Methods
3. Degree of Associativity 
4. Processing alternatives for information 

1.2 BASIC TYPES OF DATA STRUCTURE
1. Primitive Data Structure
2. Non Primitive Data Structure 

1.	Primitive Data Structure

These are basic structures and are directly operated upon by the machine instructions. These have different representation on different computers. Integer, floating point numbers, character constants, pointers and so on  fall in this category. Non Primitive Data Structure 
These are more sophisticated (Complex) data structures. The non primitive data structures emphasize on structuring of a group of homogeneous or hetrogeneous data items. Arrays, List, Stack, Tree, Queue and Files are in the list.
1.3 OPERATIONS ON DATA STRUCTURE

The Operations performed on data structures are :
1. Create
2. Delete or Destroy
3. Selection 
4. Updation 
5. Searching
6. Sorting
7. Merging 




2. What is algorithm? Write short notes on Analysis and Complexity of algorithm.
	ALGORITHM
A well defined list of steps for solving a particular problem, which can be expressed either as an informal high level description as pseudocode or using a flowchart. Algorithm name can be given by author Abu Jafar Muhammad ibn Musa 820 BC. It is a finite set of instruction that is used to find the solution of a problem.

2.1	ANALYSIS OF ALGORITHM

An algorithm is said to be efficient and fast, if it takes less time to execute and consumes less memory space.

2.1.1 COMPLEXITY 
The complexity of an algorithm is a function f (n) which measures the time and space used by an algorithm in terms of input size n. In computer science, the complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones. A complexity of any algorithm tells you how much resources will the execution use over some input size n. ALGORITHM

The performance of an algorithm is measured on the basis of following properties:

1. Time Complexity: related to CPU time.
2. Space Complexity: related to RAM memory.









1. Time complexity can be seen as the measure of how fast or slow an algorithm will perform for the input size. Time complexity is always given with respect to some input size (say n). Here’s an example to clear the text :
11 people are standing in a row in ascending order with respect to their heights. Now you are asked to tell the median of their heights. You have 2 methods to do it :
1.	Starting from the first(smallest) person, you record the height of every person in the line and then calculate the median of the data. Notice, in this method, we asked (compute) heights of all 11 men. That means we did the work given to us in the order of total men standing in the line. What if there were n men ? then our computation would have been n. So we can say that time complexity is directly related to n or O(n).

2.	You act smartly this time. You knew that everyone is standing in ascending order so its not required to go to every person. You then go the the person standing on the 6th position and asked his height. He tell you his height and you declare the answer. In this approach, it didn’t matter if there were 10 or 100 men, you would just go the the middle person and get the answer. So here you had to work only once, or we can say that the time complexity is independent of the input size and can be written as O(1).



2. Space complexity can be seen as the amount of extra memory you require to execute your algorithm. Like the time complexity, it is also given with respect to some input size (n). Another example :
10 bags are to be transported from one site to another. Again you have two options.
1.	You choose a small vehicle which has only one seat and you cannot keep more than one bag on the seat. So you take a bag and transport it. You make 10 trips (time complexity) but only one seat (space complexity). Similarly if you had n bags and you intend to transport them with the same medium, then also you will need only one seat. So you can say that space complexity for this solution will be constant or independent of the input size (number of bags) or O(1).

2.	Now you were fed up making a lot of trips between the two sites. You choose a bus with exactly same seats as the number of bags. You keep one bag per seat in the bus. Here, we have to make only one trip (time complexity) but we have used 10 seats (space complexity). Here you can say that number of seats (extra memory) is directly proportional to the input size (number of bags). So the space complexity is O(n).


We generally compute time complexity by total number of instructions executed by the algo. and this is represented by function of n (input size) means T(n)=f(n).

The complexity of an algorithm is a function f(n) which measures the time and space used by the algorithm in terms of input size n. 

2.1.SPACE TIME TRADE OF

The space time tradeoff refers to a choice between algorithmic solution of a data procesesing problem that allows one to decrease the running time of an algorithmic solution by increasing the space to store the data and vice versa. 
The complexity of search algorithm is given by the number of comparisions between ITEM and DATA. 

2.3. EXECUTION TIME CASSES

Worst Case: It is represented by Big Oh notation which is a upper bound or maximum time required by computer to execute an algorithm.
Worst Case occurs when the data item is the last element in the array or is not there at all. 
C(n)=n 

Best Case: Represented by Omega notation which is lower bound or minimum time required by computer to execute an algorithm. 

Average Case: Average time required by computer to execute an algorithm. Represented by all Big Oh, Omega and Theta notation. 

Item does appear in the array and is equally likely to occur at any position in the array. The number of comparisions can be any of the numbers from 1..2.. to n. and each number occurs with the probablity (p) is p = 1/n. 
Then C(n)=1. 1/n + 2. 1/n + 3. 1/n +. . . . + n.1/n.
=> 1/n( 1+2+3..+n) => [n(n+1)/2] . 1/n
=> (n+1)/2




3. Write short notes on Asymptotic Notations highlighting Big O Notation, Omega Notation, Theta Notation with diagrams if required.
	BIG O NOTATION 

Suppose M is an algorithm and n is the size of input data. The complexity of M increases as n increases. The big notation defines the upper bound function g(n) for f(n) which represents the time - space complexity of the algorithm on an input characteristic n. 
(fn) = O(g(n)) , if there are positive constants n-( n not) and C such that to the right of n-(n not ), the value of f(n) always lies on or below C(g(n)).

Lower Bound (Omega Notation)
The omega notation is used when the function g(n) defines a lower bound for the function f(n). f(n) = Omega g(n) if there are positive constants n-(n not) and C such that to the right of n-(n not) the value of f(n) lies on or above Cg(n).

Tightly Bound : The theta notation is used when the function f(n) is bounded both from above and below by the function g(n). The notation bounds a function to with in a constant factors. 

f(n) = Theta (g(n) if there exists positive constant n-( n not ),c1 and c2 such that the value of f(n) always lies between c1g(n) and c2g(n) inclusive.





4. What is linear Search ?
	This unit defines the working structure. Data when stored needs to be searched and sorted. Searching should take minimum time and for this data needs to be sorted as sorted data can be accessed in less time. Following this we have different searching and sorting algorithm which we would seeing here : 

LINEAR SEARCH 

A linear search is the basic and simple search algorithm. Linear search is also called as sequential search. Linear search is a method for finding a particular value in a list. In this searching technique, every items is checked one by one and if a match founds then that particular item is returned otherwise search continues till the end of the data collection. Linear array is a list of finite number n of homogeneous data elements.




5. Program for Merge Sort
	#include 
// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.
// merge sort function
void mergeSort(int a[], int p, int r)
{
    int q;
    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q+1, r);
        merge(a, p, q, r);
    }
}
// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
    int b[5];   //same size of a[]
    int i, j, k;
    k = 0;
    i = p;
    j = q + 1;
    while(i <= q && j <= r)
    {
        if(a[i] < a[j])
{
            b[k++] = a[i++];    // same as b[k]=a[i]; k++; i++;
        }
        else
        {
            b[k++] = a[j++];
        }
    }
  
    while(i <= q)
    {
        b[k++] = a[i++];
    }
  
    while(j <= r)
    {
        b[k++] = a[j++];
    }
  
    for(i=r; i >= p; i--)
    {
        a[i] = b[--k];  // copying back the sorted list to a[]
    } 
}

// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("
");
}
 
int main()
{
    int arr[] = {32, 45, 67, 2, 7};
    int len = sizeof(arr)/sizeof(arr[0]);
 
    printf("Given array: 
");
    printArray(arr, len);
    
    // calling merge sort
    mergeSort(arr, 0, len - 1);
 
    printf("
Sorted array: 
");
    printArray(arr, len);
    return 0;
}





6. Program for Merge Sort
	#include // lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted. // merge sort function void mergeSort(int a[], int p, int r) { int q; if(p < r) { q = (p + r) / 2; mergeSort(a, p, q); mergeSort(a, q+1, r); merge(a, p, q, r); } } // function to merge the subarrays void merge(int a[], int p, int q, int r) { int b[5]; //same size of a[] int i, j, k; k = 0; i = p; j = q + 1; while(i <= q && j <= r) { if(a[i] < a[j]) { b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++; } else { b[k++] = a[j++]; } } while(i <= q) { b[k++] = a[i++]; } while(j <= r) { b[k++] = a[j++]; } for(i=r; i >= p; i--) { a[i] = b[--k]; // copying back the sorted list to a[] } } // function to print the array void printArray(int a[], int size) { int i; for (i=0; i < size; i++) { printf("%d ", a[i]); } printf("
"); } int main() { int arr[] = {32, 45, 67, 2, 7}; int len = sizeof(arr)/sizeof(arr[0]); printf("Given array: 
"); printArray(arr, len); // calling merge sort mergeSort(arr, 0, len - 1); printf("
Sorted array: 
"); printArray(arr, len); return 0; } 




7. Give Proper Introduction to PHP?
	PHP is one of the most popular language in the world of web development. It has the best connectivity with database and an expert language in insertion, deletion , updation and extraction of data from database. 

It is referred as back end language. It just displays the value from the database in case of front end. As the name implies it is preprocessor. It actually refers to compilation or reading of codes before actual execution. There are various framework which php runs as Macromedia Dreamweaver, Brackets, Notepad Plus plus and many other. Any local server works perfect for PHP like wamp, xxamp, mamp .

PHP makes a website dynamic. That refers to all the things that you see on web site comes from database for examples www.noidatut.com What ever you see on the web site it comes from the database. There are various functions used in php to encrypt the data in case of password or sensitive data. 

PHP stands zero without database connectivity or Sql. It uses Sql to create , insert, delete, modify update. PHP super Global variables makes this language special in the world of web development. Using PHP you can insert larger data in the database as well. PHP has the ability to read all the queries from the web page. There are various framework verison of PHP. PHP laveral, PDO are different frame versions of PHP.  




8. Explina the pin configuration of Intel 8085 with proper diagram if required.
	PIN DESCRIPTION OF 8085
A8-A15 (output)-These are address bus and are used for the most significant bits of the memory
address or 8 bits of I/O address.
AD0-AD7 (input/output)-these are time multiplexed address /data bus that is they serve dual
purpose .they are used for the least significant 8 bits of the memory address or I/O address during
the first clock cycle of a machine cycle. Again they are used for data during second and third
clock cycles.
ALE (output)-it is an address latch enable signal. It goes high during first clock cycle of a
machine cycle and enables the lower 8 bits of the address to be latched either into the memory or
external latch.
IO/M(output)-it is a status signal which distinguishes whether the address is for memory or I/O.
when it goes high the address on the address bus is for an I/O device. When it goes low the
address on the address bus is for a memory location.
RD (output)-it is a signal to control READ operation .when it goes low the selected memory or
I/O device is read.
WR(output)-it is a signal to control WRITE operation .when it goes low the data on the data bus
is written into the selected memory or I/O operation.
READY(input)-it is used by the microprocessor to sense whether a peripheral is ready to
transfer data or not .a slow peripheral may be connected to the microprocessor through READY
line. if READY is high the peripheral is ready .if it is low the microprocessor waits till it goes
high.
HOLD (input)-it indicates that another device is requesting for the use of the address and data
bus. Having received a HOLD request the microprocessor relinquishes the use of the buses as
soon as the current machine cycle is completed. Internal processing may continue. the processor
regains the bus after the removal of the HOLD signal. when a HOLD is acknowledged .
HLDA (output)-it is a signal for HOLD acknowledgement. It indicates that the HOLD request
has been received. after the removal of a HOLD request the HLDA goes low. the CPU takes over
the buses half clock cycle after the HLDA goes low.
INTR (input)-it is an interrupt request signal. Among interrupts it has the lowest priority. An
interrupt is used by io devices to transfer data to the microprocessor without wasting its time.
INTA (output)-it is an interrupt acknowledgement sent by the microprocessor after INTR is
received.
RST5.5, RST6.5, RST 7.5(input)-these are interrupts. Signals are the restart interrupt, they
causes an internal restart to be automatically inserted each of them of a programmable mask.
TRAP-TRAP has the highest priority. It is used in emergency situation. it is an non-mask able
interrupt.




9. What is Phishing and how is it related to piracy?
	Phishing is electronic way of fraudant which includes gaining the personal content like email address , password, date of birth and other personal details. It eventually came from the word fishing which took over as phishing which relates to fish some ones data. Phishing includes sending emails to some one and asking them to register to a particular site which resembles the brand and provides same services. 
For example : www.noidatut.com is a web site which has hundreds of supporters. Phishing the site – some one can make a web site www.noidatu.com . Both the site will have the similar design and services. Instead the fake one will have a slight change in the  original name. You can see in the above example the original site is www.noidatut.com where else the fake one is www.noidatu.com 

Phishing can be taken as electronic or e piracy. In the world of technology we have also lived in a time when we used have cd players, and cassettes. There were various situations where we could easily get the pirated version of the original in a cheaper way. 




10. What do you mean by Dynamic Web Applications?
	The literal meaning of Dynamic is which keeps on changing. On the other hand we have static  which refers to fix and not changing. In the world of web development when we say Super Dynamic refers to the context that the content of the web site comes from Database. The working structure of the web site goes like way that there is two section one is Admin panel and other is client or user panel. In the admin panel the can upload the content of the web site including images and other details which can be viewed from the client section. The admin is authorized to edit , update , delete , modify the content of the web site. 




Download in Word


Our Proud Members

Courses For Free


Register Now

Noidatut is an E Learning Platform for students to get CLASS NOTES AND LAB MANUALS. This is simple E Learning Platform where we aim to have the largest collection of E - Books and other study resources. We have the notes for different curces starting from Engineering to Diploma.