Question bank for First IAT covering 1.5 Module

Name of the faculty: Gouri Patil / Margesh K

Sem:      V A and B                                    Subject: ATC                                                     Subject code:17CS54

Sl.No.	Question	Blooms Taxonomy Level	CO	PO
1	Define DFA, NFA, є-NFA, Regular expressions	1	1	1,6,8
2	List the hierarchy of languages.	1	1	1,6,8
3	Show that if ∑ ≠Ф then ∑* is countably infinite	2	1	1,6,8
4	Compare DFSM and NDFSM	2	1	1,6,8
5	Construct  DFA to accepts a strings of 0’s ,1’s and 2’s beginnig with 0 followed by odd number of 1’s and ending with 2	3	2	1,2,3,4,7,8,9,10,12
6	Construct DFA to accept strings of  a’s and b’s having a sub string aa	3	2	1,2,3,4,7,8,9,10,12
7	Construct DFA to accept strings of a’s and b’s having even number of a’s and odd number of b’s.	3	2	1,2,3,4,7,8,9,10,12
8	Construct є-NFA to accept the following language L = {w | w є abab n or aba n where n є 0}	3	2	1,2,3,4,7,8,9,10,12
9	Simplify DFA using table filling algorithm δ 0 1 —> q1 q2 q3 q2 q3 q5 *q3 q4 q3 q4 q3 q5 *q5 q2 q5	3	2	1,2,3,4,7,8,9,10,12
10	Simplify above DFA using splitting method δ a b —> 1 2 4 *2 3 6 3 2 4 *4 6 5 5 2 4 6 6 6	3	2	1,2,3,4,7,8,9,10,12
11	Simplify RE using Kleen star	3	2	1,2,3,4,7,8,9,10,12
12	Prove that if M be a FA recognizing the language L, then there exists an equivalent regular expression R for the regular language L such that L=L(R) Hint: Kleen’s theorem	4	3	1,2,3,4,8,9,10,12
13	Classify various languages by hierarchy	4	3
14	Choose one of design technique to write DFSM L = {w | w є {a,b}*, No two consecutive characters are same}	5	4	1,2,3,4,8,9,10,12
15	Choose one of design technique to write DFSM to accept decimal strings divisible by 3	5	4	1,2,3,4,8,9,10,12
16	Choose one of design technique to write DFSM L = {w : |w| mod3= 0}	5	4	1,2,3,4,8,9,10,12
17	Design DFSM to accept strings of a’s and b’s having even number a’s and odd number of b’s	6	5	1,2,3,4,8,9,10,12
18	Design DFA from є-NFA δ є a b c —> p Ф p q r q p q r Ф *r q r Ф p	6	5	1,2,3,4,8,9,10,12
19	Design a regular expression for L={anbn : (m+n) is even} L={a2nb2m: n,m≥0} L={anbm: n≥4, m≤3}	6	5	1,2,3,4,8,9,10,12

10cs43 DAA UNIT 1 QUESTION BANK

UNIT 1

INTRODUCTION

QUESTION BANK

1. With the help of flow chart , Explain the various steps of design and analysis process?

2.If f₁(n)€O(g₁(n)) and If f₂(n)€O(g₂(n)) prove that f₁(n)+ f₂(n) €O(max{g₁(n),g₂(n)})

3.What is algorithm? What are properties of Algorithm?.Explain with example.

4.Explain briefly various Asymptotic Notation?

5. Design a recursive Algorithm for solving Tower of Hanoi problem and give general plan of analyzing that algorithm. Show that time complexity of tower of Hanoi algorithm is exponential in nature.

6.Write an algorithm for computing GCD.

              a)Using Euclid Algorithm.

             b)Repetitive subtraction

            c) Consecutive Integer Checking

7.Explain the Sieve of Eratosthenes Alogrithm to generate prime factor?

8.Write general plans for non recursive algorithm for analyzing time efficiency?Explain with algorithm Element Uniqueness problem.Show that time efficiency is Quadratic in nature.

9.Explain non recursive algorithm to find Maximum of n-elements .Also provide time efficiency

10.Explain  non recursive algorithm for matrix multiplication.Also provide time efficiency

11. Explain non recursive algorithm to count the number of binary digits.Also provide time efficiency.

12. Write general plans for  recursive algorithm for analyzing time efficiency?Explain time efficiency of factorial of a given number with algorithm.

13.Write a recursive algorithm for fibonaaci number.Also provide the Explicit formula to obtain n^th Fibonacci number.

14. Write an algorithm for selection sort and show that time complexity of this algorithm is quadratic.Is Selection sort Stable?.Sort the list 89,45,68,90,29,34,17 using selection sort

15.Explain Brute force method for design and analysis .Explain the brute force string matching algorithm with its efficiency.

16. Write an algorithm for Bubble sort .Explain briefly time efficiency of Bubble sort?Sort the list E,X,A,M,P,L,E in alphabetical order using Bubble sort

17.Write an algorithm for sequential Search(linear search).Explain Best Case,Worst Case and Average Case time efficiency .

18.Express using Aysmptotic Notation i) N! ii) 6 * 2ⁿ+n²

19. Algorithm X(int N)

     {

     int P;

    for i←1 to N

   { printf(“\n %d \t * \t %d=%d”,N,i,p);

    P=P+N;

}

}

i)What does this algorithm computes?

ii)What is the basic operation?

iii)How many time the basic operation is executed?

iv)What is efficiency of algorithm?

20.Solve the recurrence relation

  i)   F(n)=0                             if n=0

                f(n-1)+n                   if n>0

ii)f(n)=3f(n-1) for n>1,f(1)=4

iii)f(n)=f(n/2)+n   for n>1,f(1)=1 n=2^k

  

DESIGN AND ANALYSIS OF ALGORITHMS

(Common to CSE & ISE)

Subject Code: 10CS43 I.A. Marks : 25

Hours/Week : 04 Exam Hours: 03

Total Hours : 52 Exam Marks: 100

PART – A

UNIT – 1                                                                                                                                    7 Hours

INTRODUCTION: Notion of Algorithm, Review of Asymptotic Notations,Mathematical Analysis of Non-Recursive and Recursive Algorithms Brute Force Approaches: Introduction, Selection Sort and Bubble Sort,Sequential Search and Brute Force String Matching.
UNIT - 2                                                                                                                                     6 Hours
DIVIDE AND CONQUER: Divide and Conquer: General Method,Defective Chess Board, Binary Search, Merge Sort, Quick Sort and its performance.
UNIT - 3                                                                                                                                     7 Hours
THE GREEDY METHOD: The General Method, Knapsack Problem, Job Sequencing with deadlines, Minimum-Cost Spanning Trees: Prim’s Algorithm, Kruskal’s Algorithm; Single Source Shortest Paths.
UNIT - 4                                                                                                                                      6 Hours
DYNAMIC PROGRAMMING: The General Method, Warshall’s Algorithm, Floyd’s Algorithm for the All-Pairs Shortest Paths Problem, Single-Source Shortest Paths: General Weights, 0/1 Knapsack, The Traveling Salesperson problem.

PART – B

UNIT - 5                                                                                                                                      7 Hours
DECREASE-AND-CONQUER APPROACHES, SPACE-TIME TRADEOFFS: Decrease-and-Conquer Approaches: Introduction, Insertion Sort, Depth First Search and Breadth First Search, Topological Sorting Space-Time Tradeoffs: Introduction, Sorting by Counting, Input
Enhancement in String Matching.
UNIT – 6                                                                                                                                     7 Hours
LIMITATIONS OF ALGORITHMIC POWER AND COPING WITH THEM: Lower-Bound Arguments, Decision Trees, P, NP, and NP-Complete Problems, Challenges of Numerical Algorithms.
UNIT - 7                                                                                                                                     6 Hours
COPING WITH LIMITATIONS OF ALGORITHMIC POWER:Backtracking: n - Queens problem, Hamiltonian Circuit Problem, Subset –Sum Problem. Branch-and-Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem.Approximation Algorithms for NP-Hard Problems – Traveling Salesperson Problem, Knapsack Problem
UNIT – 8                                                                                                                                      6 Hours
PRAM ALGORITHMS: Introduction, Computational Model, Parallel Algorithms for Prefix Computation, List Ranking, and Graph Problems.

Text Books:
1. Anany Levitin: Introduction to The Design & Analysis of Algorithms, 2nd Edition, Pearson Education, 2007. (Listed topics only from the Chapters 1, 2, 3, 5, 7, 8, 10, 11).
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran: Fundamentals of Computer Algorithms, 2nd Edition, Universities Press, 2007. (Listed topics only from the Chapters 3, 4, 5, 13)
Reference Books:
1. Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition, PHI, 2010.
2. R.C.T. Lee, S.S. Tseng, R.C. Chang & Y.T.Tsai: Introduction to the Design and Analysis of Algorithms A Strategic Approach, Tata McGraw Hill, 2005.