CSE 2050 Exam 2 || 100% Faultless Answers.
Write a O(n) contains function with one line of code correct answers return any(obj == item for i
in L)
What is the run time of binary search with slicing? correct answers O(nlogn)
What is the run time of binary search with reference? correct answers O(logn)
Why is iteration better than recursion? correct answers Iteration is generally faster and takes less
memory space
Dynamic Programming correct answers Sub-problems are solved from the bottom up. Each
problem is trivially solved as the combination of previously-solved subproblems.
Greedy Algorithm correct answers an algorithm that always tries the solution path that appears to
be the best.
Memoization correct answers Before attempting to solve a new sub-problem, a collection is
referenced to see if this sub-problem has already been solved.
Drawbacks of Recursion correct answers Can be slow, take a lot of memory space, can solve the
same subproblems repeatedly
Recursion can help (?) correct answers Explore branching paths
Recursion correct answers the process of calling the function by itself until it reaches a base case
Binary Search correct answers An ordered list is divided in 2 with each comparison.
Prune and Search correct answers method for finding an optimal value by iteratively dividing a
search space into two parts
Invariant correct answers something that holds true throughout the execution of a code
Invariant for Bubble Sort correct answers The biggest items of the list are in their sorted, final
position after each loop
Invariant for Selection Sort correct answers Same thing with Bubble Sort, where the biggest
items of the list are in their sorted, final position after each loop
Invariant for Insertion Sort correct answers After each loop, a small portion of the list, or sub list,
are sorted, but does not mean that each element are in their final position
Best and Worst Case for Bubble Sort correct answers Best Case: if only one item (particularly
the rabbit) is unsorted, O(n)
Worst Case: O(n^2), has to go through every item (reversed sorted list, turtle, randomized)
Write a O(n) contains function with one line of code correct answers return any(obj == item for i
in L)
What is the run time of binary search with slicing? correct answers O(nlogn)
What is the run time of binary search with reference? correct answers O(logn)
Why is iteration better than recursion? correct answers Iteration is generally faster and takes less
memory space
Dynamic Programming correct answers Sub-problems are solved from the bottom up. Each
problem is trivially solved as the combination of previously-solved subproblems.
Greedy Algorithm correct answers an algorithm that always tries the solution path that appears to
be the best.
Memoization correct answers Before attempting to solve a new sub-problem, a collection is
referenced to see if this sub-problem has already been solved.
Drawbacks of Recursion correct answers Can be slow, take a lot of memory space, can solve the
same subproblems repeatedly
Recursion can help (?) correct answers Explore branching paths
Recursion correct answers the process of calling the function by itself until it reaches a base case
Binary Search correct answers An ordered list is divided in 2 with each comparison.
Prune and Search correct answers method for finding an optimal value by iteratively dividing a
search space into two parts
Invariant correct answers something that holds true throughout the execution of a code
Invariant for Bubble Sort correct answers The biggest items of the list are in their sorted, final
position after each loop
Invariant for Selection Sort correct answers Same thing with Bubble Sort, where the biggest
items of the list are in their sorted, final position after each loop
Invariant for Insertion Sort correct answers After each loop, a small portion of the list, or sub list,
are sorted, but does not mean that each element are in their final position
Best and Worst Case for Bubble Sort correct answers Best Case: if only one item (particularly
the rabbit) is unsorted, O(n)
Worst Case: O(n^2), has to go through every item (reversed sorted list, turtle, randomized)
