Data Structures and Algorithm Answer True or False 1.Efficiency of algorithms in
ID: 3575187 • Letter: D
Question
Data Structures and Algorithm
Answer True or False
1.Efficiency of algorithms involving sorting does not depends on efficiency of sorting.
2.Transform and Conquer techniques solves a problem by a transformation to a simpler/more convenient instance of the same problem (instance simplification) .
3.Given a string ‘S’, the problem of string matching deals with finding whether a pattern ‘p’ occurs in ‘S’ and if ‘p’ does occur then returning position in ‘S’ where ‘p’ occurs.
4.Two varieties of space-for-time algorithms are input enhancement and pre structuring.
5.String searching cannot be performed by brute force.
6.Dynamic Programming is a general algorithm design technique for solving problems defined by recurrences with sub problems without overlapping. F
7.Greedy Technique Constructs a solution to an optimization problem piece by piece through a sequence of choices that are not feasible and locally optimal and irrevocable.
8.The Simplex Method is the classic method for solving LP problems and one of the most important algorithms ever invented.
9.Maximum Flow Problem Is maximizing the flow of a material through a transportation network.
10.Three possible outcomes in solving an LP problem are: 1) has a finite optimal solution , 2)
unbounded, 3) infeasible.
Essay Questions:
Please provide detail and comprehensive answer to the following questions.
1.Briefly describe what is searching with presorting. Briefly describe and explain the logic of binary search.
2.Define what is Dynamic programming and discuss the main ideas and provide an example.
3.Write an algorithm for Depth First search.
4.Write an algorithm to compute the Prime numbers between 1 to 100.
Explanation / Answer
1.Efficiency of algorithms involving sorting does not depends on efficiency of sorting. TRUE.
Efficiency of an algorithm may or may not depend on the efficiency of sorting. It depends on
the algorithm logic.
2.Transform and Conquer techniques solves a problem by a transformation to a simpler/more
convenient instance of the same problem (instance simplification) . TRUE.
The concept of transform and conquer is, first transform the problem into a simpler or well known
form, and then solve the problem.
3.Given a string ‘S’, the problem of string matching deals with finding whether a pattern
‘p’ occurs in ‘S’ and if ‘p’ does occur then returning position in ‘S’ where ‘p’ occurs. TRUE.
This is what the concept of pattern matching algorithm.
4.Two varieties of space-for-time algorithms are input enhancement and pre structuring. TRUE.
5.String searching cannot be performed by brute force. FALSE.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.