Assignments for B.Sc.

(IT)

Assignment: TA (Compulsory) 1. Define an algorithm. What are the properties of an algorithm ? Ans.- An algorithm is a set of instructions that provide step-by-step specifications to perform a Task. The properties of an algorithm are: Input: Specifies the data set that is applied to the algorithm to check its validity. Output: Specifies the data set that is produced as a result of the algorithm execution. Definiteness: Specifies that the instructions described in the algorithm should be well defined and should not create any ambiguity. Termination: Specifies that the instructions described in the algorithm must contain a proper termination condition. Effectiveness: Specifies that the algorithm take less time and less memory space during its execution.

2. Write a note on i) devising

ii) validating

and iii) testing of algorithms.

Ans.- 1. Devising The process of devising an algorithm is both an art and a science This is one part that cant be automated fully. Given a problem description, one have To think of converting this into a series of steps, which ,when executed in a given Series of steps, which when executed in a given sequence solve the problem. 2. Validating - one simply way is to code it into a program. However converting the algorithms into programmers is a time consuming process. hence, it is essentials to be reasonably sure about the effectiveness of the algorithm before it is coded. This process, at the algorithm before it is coded. This process, at the algorithm level, is called validation. Several mathematical and other empirical methods of validation are available. Providing the validation of an algorithm is fairly complex process and most often a complete theoretical validation. 3. Testing of algorithms The ultimate test of an algorithm is that the programs based On the algorithm should run satisfactorily. Testing a program really involves two phases (a) debugging and (b) profiling. Debugging is the process of executing programs with sample datasets to determine if the results obtained are satisfactory. When unsatisfactory results are generated, suitable changes are made in the program to get the desired results. On the other hand, profiling or performance measurement is the process of executing a correct program on different data sets to measure the time and space that it takes to compute the results.

3. What is a linear data structure ? Give examples. Describe how an array is represented.

Ans.- Linear data structure is which every data element has got exactly tow neighbors or two adjacent elements except two elements having exactly one data element is called a linear data structure. Example 1 3 1000 2 7 1002 -8 1004 3 4 10 1006 15 1008 5 6 5 1010 ----------------50

The first element is at (1000+0)th location 2nd element is at (1000+2)th location ------ith element is at (1000+(i-1)*2)th location. 4. Write algorithms to implement the following operations on a stack - create, push, pop. Ans.- Stack- algorithms : create Output- S, Stack created Method: Declare S [SIZE] Declare and initialize T=0 Algorithm ends Input: S , Stack Output: Boolean Method: If(T==0) Return(yes) Else Return (no) If end Algorithm end

Push Algorithm : Push

Method : If(Isfull(s)) then Print(stack overflow) Else T=T+1; S[T]=e If end Algorithm ends

Pop Method :

If(Isempty(s))then Print(stack is empty) Else e = S[T] T=T-1; If end Algorithm ends 5. What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it create, insertion, deletion, for testing overflow and empty conditions. Ans.- A queue is an ordered list in which all insertions take place at one end called the rear end, while all deletions take place at the other end called the front end . queue is a linear data structure which works based on the strategy first-in first out(FIFO). Create : Method : Declare Q[SIZE] Declare and initialize F=0,R=0

Insertion : Method : If(Isfull(Q)) then Print(overflow) Else R=R+1; Q[R]=e If(F==0) F=1; If end If end Algorithm ends Deletion : Method : If(Isempty(Q))then Print(Queue is empty) Else e= Q[F] If(F==R) F=R=0; Else F=F+1; If end If end Algorithm ends

Isempty: Method : If(f==0) Return(yes) Else Return (no) If end Algorithm ends

6. What is a graph ? What are the two ways of representing a graph ? Describe with the help of illustrative examples. Ans.- A graph G= (V,E) is a consists of a set of objects V={ v1, v2,} called vertices,and Another set E=[e1,e2,.} whose elements are called edges.

Example 100 80 60 40 20 0 1s t Qtr 2ndQtr 3rdQtr 4thQtr E a s t Wes t N orth

8.What is a circular queue ? Write algorithms to implement the insertion and deletion operations. Ans.- A circular queue uses the same conventions as that of linear queue. Using front will always point one position counterclock wise from the first element in the queue.

Algorithm : Insertion

Method : If(Isfull(CQ))then Print(overflow) Else R=R mod SIZE+1; CQ[R]=e If(Isempty(CQ)) F=1; If end If end Algorithm ends Algorithm : Deletion Method: If (Isempty(CQ))then Print(Queue is empty) Else e= CQ[F] If(F==R) F=R=0; Else F=F mod SIZE +1; If end If end Algorithm ends

9.Write an algorithm to find the roots of a quadratic equation. Ans.- Algorithm : quadratic_solver Input : a,b,c the co-efficient of the quadratic equation

Output : The two roots of the Equation Method disc =((b*b)-(4*a*c)) if (disc=0) display roots are real and equal r1=-b/2a r2=-b/2a display r1 display r2 else if(disc>0) display roots are real and distinct r1=(-b+sqrt(disc))/2a r2=(-b-sqrt(disc))/2a else display roots are complex display real part, b/2a display imaginary partsqrt(absolute_value_of(disc)) display the two exists in conjugates end _if Algorithm ends 10.Design an algorithm to check whether a given string is a palindrome or not. Ans. - Algorithm: check whether the string is a palindrome or not input: string, flag Output: string is a palindrome Method: count = 0 while (the next character ch in the string is not empty) a(count) = ch count = count+1 end while

half = count/2palin = true for (i=1 to half in steps of 1 and j=count to half in steps of 1 do) if (a (i)! =a (j)) palin = false break end if if (palin = true) Display 'String is a palindrome' else Display 'String is not a palindrome' end for 11.Develop an algorithm to generate all the prime numbers between the given 2 limits. Ans.- Algorithm: to generate all prime numbers between the given 2 Limits. Input: l1 and l2 Output: Prime numbers between l1 and l2 Method: for (n=l1 to l2 in steps of 1 do) prime=true for (i=2 to n/2 in steps of 1 do) if (n % i =0) prime = false break end_if end_for if (prime = true) Display 'Prime number is =', n end_for end if