Please answer this questions ONLY if you are sure about that. I had bad experien
ID: 3694547 • Letter: P
Question
Please answer this questions ONLY if you are sure about that. I had bad experience several times. So please only answers if you are confident with the questions. Thank you.
True/False Questions
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 prestructuring.
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.
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.
Briefly describe what is searching with presorting. Briefly describe and explain the logic of binary search.
Define what is Dynamic programming and discuss the main ideas and provide an example .
Describe and outline the Linear programming applications. Provide 2 example of the applications of linear programming method?
Explanation / Answer
Solution:
1)True
2)True
3)True
4)False
5)True
6)True
7)True
8)False
9)True
10)True
a)Binary search:
A binary search is a binary tree data structure that works based on the principle of binary search.The records of the tree are arranged in sorted order, and traversal of the tree is performed using a logarithmic time binary search-like algorithm. Insertion and deletion also require logarithmic time in binary search trees.
This is faster than the linear time insertion and deletion of sorted arrays, and binary trees retain the ability to perform all the operations possible on a sorted array.
A binary search is usually more efficient for searching as binary search trees will most likely be imbalanced, at least resulting in slightly worse performance than binary search.
There exist data structures that may beat binary search in some cases for both searching and other operations available for sorted arrays.
For example, searches, approximate matches, and a subset of the operations available to sorted arrays can be performed much more efficiently than binary search on specialized data structures such as van Emde Boas trees, fusion trees, tries, and bit arrays.
Problem: Search for a given K in A[0..n-1]
Presorting-based algorithm:
Stage 1 Sort the array by an efficient sorting algorithm
Stage 2 Apply binary search
Efficiency: O(nlog n) + O(log n) = O(nlog n)
Library support:
Java offers a set of overloaded binarySearch() static methods in the classes Arrays and Collections in the standard java.util package for performing binary searches on Java arrays and on Lists, respectively.
C provides the function bsearch() in its standard library, which is typically implemented via binary search.
standard library package contains the functions Search, SearchInts, SearchFloat, and SearchStrings, which implement general binary search, as well as specific implementations for searching slices of integers, floating-point numbers, and strings, respectively.
b)Dynamic programming:
It is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions ideally, using a memory-based data structure.
The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a modest expenditure in storage space.
Dynamic programming is both a mathematical optimization method and a computer programming method. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.
While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively.
Example:
implementation of a function finding the nth member of the Fibonacci sequence, based directly on the mathematical definition:
ex: function fib(n)
if n <= 1 return n
return fib(n 1) + fib(n 2)
C)Linear Programming Application:
the linear-programming model so they may allocate the resources of the enterprise most efficiently, particularly in situations where important constraints are placed on the actions that may be taken.
The chapter begins by developing the formulation and graphical solution to a profit-maximization production problem. The following section discusses the concept of dual variables and their interpretations.
A computer solution to a cost-minimization problem is presented next.
More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.
Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron.
A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists
Linear programs are problems that can be expressed in canonical form as
Maximum cT x
Subject to Ax<=b and x>=0.