Test 1 Flashcards
When confronted with a new ___________ , there may be several possible solutions.
problem
A __________ is a question which requires an answer.
problem
A problem usually includes variables, called __________.
parameters
What is an algorithm?
A step - by- step procedure to solve all instances of a problem.
What are problems of an algorithm?
Difficult for complex algorithms
Hard to translate to a programming language
It is possible for sequential search to examine _______ element before solving the problem . It can be used whether the array is sorted or not.
every
A much faster algorithm is available if the array is sorted:
Binary Search
works by comparing x with the middle of the array. The algorithm then “ discards” either the first or second half of the array .
Binary search
It can be shown by mathematical induction that the recursive version performs approximately _________ operations.
2 ^ (n / 2)
The iterative version if recursion performs ____ operations.
n + 1
when the basic operation is done the same number of times for every instance of size n. In algorithm 1.2 (sum of array values), T(n) = n
Every-Case Time Complexity
when the amount of work performed by the algorithm depends on the values of other parameters. W(n) is the largest number of times the basic operation will be performed for an instance of size n. In algorithm (sequential search) W(n) = n
Worst-Case Time Complexity
When analyzing the Complexity of an algorithm, it is useful to observe some simplifying abstractions:
Do not worry about actual CPU time
Determine the number of times a basic operation is done as a function of n (the size of the input)
The total amount of work done by the algorithm is proportional to the number of times the basic operation is performed .
Once we determine the number of operations performed as a function of n(T (n) or W(n)) , we are interested in classifying algorithms according to their ________ or ____________ class.
order
complexity
Algorithms with time complexities such as n,100n, and 50n + 10 are called ____________ algorithms
linear -time
Algorithms with time complexities such as n ^ 2, 0.5n ^ 2 , and n ^ 2 + 10n + 1 are called _____________ algorithms
quadratic-time
Any linear -time algorithm is ______________________ than any quadratic-time algorithm.
eventually more efficient
In order to define order formally, it is useful to define a similar concept:
Big O notation.
Big notation is used to establish an _____________ on the growth of a function .
upper bound
Big Theta is defined in a similar way as Big O, except that it provides both _______ (big O ) and ______ (big Omega) bounds on the growth of the function
upper
lower
What is wrong with an algorithm such as Exchange ( Bubble ) Sort?
Usually, the least efficient of all sorting algorithms , because of the excessive number of swap operations
Exchange sort requires n - 1 major loop iterations, and up to n - 1 swaps in each iteration, resulting in a worst case of sim n^ 2 element swaps!!
This sorting causes each iteration, selection sort. Finds the smallest entry in the unsorted portion of the array , and Swaps it with the element in the corresponding position.
Selection sorting
This type of sorting works by extending the length of the sorted portion one step at a time:
After zero iterations, A[1] is sorted After one iteration, A[1..2] is sorted After two iterations, A[1..3] is sorted After three iterations A[1.4] is sorted, and so on, until A[1..N] is sorted .
Insertion sorting
For a list of length n, an average selection sort makes about key comparisons and exactly ______ swap operations .
n - 1
Selection sort is not affected by the __________ of the array elements.
original order
The insertion sort is particularly appropriate for small arrays that are _____________
nearly sorted
The divide -and-conquer strategy solves a problem by:
- Breaking it into subproblems that are themselves smaller instances of the same type of problem
- Recursively solving these subproblems
- Appropriately combining their answers
Finds the middle element, if one exists If target is equal to middle element Target found , return location
Recursive binary search
What do you do if the recursive binary search hits an else?
- DIVIDE the array into two smaller subarrays . Choose either left or right subarray , AND
- CONQUER by recursively applying binary search to the smaller subarray .
- OBTAIN overall solution from subarray result.
Let ____ be the number comparisons performed by recursive binary search for an array of size n. ____ can be expressed with a recurrence relation:
W(n)-worst case time complexity
Given an array with n items, Mergesort involves three steps:
- Divide the array into two subarrays each with n / 2 items
- Conquer (solve) each subarray by sorting it.
- Unless the array is sufficiently small, use recursion to do this Combine the solutions to the subarrays by merging them into a single sorted array
Mergesort uses additional storage: an array of the _______ as the one being ________
same size
sorted
Quicksort is another sort based on the ______________ pattern .
divide-and-conquer
Quicksort the most efficient general sorting algorithm in existence for _____________.
random arrays
Quicksort worst-case time complexity is:
O(n ^ 2)
For Quicksort, the worst-case time complexity of Theta(n ^ 2) occurs when the array is:
already sorted!!
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist ). This algorithm offers guaranteed n log (n) performance .
Collections.sort()
The sorting algorithm is a tuned quicksort , adapted from Jon L. Bentley and M. Douglas Mcllroy. This algorithm offers n^ * log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance .
Arrays.sort()
In a _________________ solution, the “basic operationsto be counted are usually performed as part of recursive calls.
Divide-and-Conquer
It is essential to formulate a recursive definition to “_______” basic operations :
count
A useful alternative in estimating Big theta complexity is to use the _________________ whenever we have a recurrence relation of the form:
Master Theorem
The master theorem is:
T(n) = a * T(n/b) + f(n)
