In general, a recursive solution to a problem in more memory efficient than an i
ID: 3694657 • Letter: I
Question
In general, a recursive solution to a problem in more memory efficient than an iterative solution. Tail recursion often indicates that the problem could be solved more efficiently using iteration. Quick sort should NOT use when the data is almost sorted. (21) Quick sort is always quick. Merge sort requires extra space. Selection sort recognizes if the values are already sorted. Binary searehing is always faster than linear searehing. HeapSort is inherently unstable. Briefly answer the following questions. What is Abstract Data Type (ADT)? What are the three different levels of data?Explanation / Answer
18. False. Neither of iteration or recursion can be called as memory efficient approach. Both is same in terms of memory efficiency.
19. True. Any problem solved by recursion also can be solved by iteration. Recursion just makes programmers life easy by using recursive approach so that designing the solution becomes more easy.
20. True.In the very early versions of QuickSort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. This "median-of-three" rule counters the case of sorted (or reverse-sorted) input, and gives a better estimate of the optimal pivot (the true median) than selecting any single element, when no information about the ordering of the input is known.
21. False. It has O(n^2) worst case time complexity. So when the number of inputs increases significantly Quicksort starts performing very bad.
22. Indeed. Because the mergesort algorithm is recursive, so it requires O(log n) stack space, for both the array and linked list cases. But the array case also allocates an additional O(n) space, which dominates the O(log n) space required for the stack. So the array version is O(n), and the linked list version is O(log n).
23. Yes. It uses a flag variable to store information about in a full run of inner loop any swaps occurred or not. If no swap occurred then the list is already sorted hence program ca exit.
24. No. Binary searching is faster in case of large number of input. But in case of small number of input deviding list can be a computational overhead.
25. Yes. Heap sort is not stable because operations on the heap can change the relative order of equal items.
26. An abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementers, not a user.
Formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations"; this is analogous to an algebraic structure in mathematics. What is meant by "behavior" varies by author, with the two main types of formal specifications for behavior being axiomatic (algebraic) specification and an abstract model; these correspond to axiomatic semantics and operational semantics of an abstract machine, respectively. Some authors also include the computational complexity ("cost"), both in terms of time (for computing operations) and space (for representing values).
27. 3 different level of data
i) Physical level.
The lowest level of abstraction describes how the data are
actually stored. The physical level describes complex low-level data
structures in detail.
ii) Logical level.
The next-higher level of abstraction describes what data are
stored in the database, and what relationships exist among those data. The
logical level thus describes the entire database in terms of a small number of
relatively simple structures.
iii) View level.
The highest level of abstraction describes only part of the entire
database. The variety of information stored in a large database. Many users
of the database system do not need all this information; instead, they need
to access only a part of the database. The view level of abstraction exists to
simplify their interaction with the system.