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 :
2. Delete or Destroy
|2. What is algorithm? Write short notes on Analysis and Complexity of 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.
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.
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
|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.
|11. Write Short notes on Visual Communication
One of the industries which most prominently uses Visual communication is the medical industry. New medicines which come into the market have to be shown to doctors and the advantages have to be explained. At such times, the medical representatives carry informative pamphlets which are shown to the doctors and dropped with the doctors.
These informative pamphlets have all the information about the medicine so that doctors can feel confident in suggesting the medicine to their patients. Similarly, many different industries are using visual communication to help interaction with their customers so that they can communicate their ideas better. Explainer videos as a concept is rising and is becoming as one of the best types of communication observed on websites.