All Flashcards
What are the differences between Linear Search and Binary Search?
Linear Search: Works on unsorted lists, O(n) time complexity. Binary Search: Requires sorted lists, O(log n) time complexity.
What are the differences between Insertion Sort and Selection Sort?
Insertion Sort: Builds sorted array incrementally, adaptive. Selection Sort: Finds the minimum element in each iteration, not adaptive.
What are the differences between Insertion Sort and Merge Sort?
Insertion Sort: Simple, in-place, O(n^2) time complexity. Merge Sort: More complex, requires extra space, O(n log n) time complexity.
What are the differences between Selection Sort and Merge Sort?
Selection Sort: Simple, in-place, O(n^2) time complexity. Merge Sort: More complex, requires extra space, O(n log n) time complexity.
What are the differences between iterative and recursive Linear Search?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Binary Search?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Insertion Sort?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Selection Sort?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Merge Sort?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
When is Merge Sort preferred over Insertion Sort?
Merge Sort is preferred for larger datasets due to its O(n log n) time complexity, while Insertion Sort is better for small datasets or nearly sorted data.
What are the general steps of Binary Search?
- Find the middle element. 2. If the target equals the middle, return the index. 3. If the target is less than the middle, search the left half. 4. If the target is greater than the middle, search the right half. 5. Repeat until found or the search space is empty.
What are the steps involved in Merge Sort?
- Divide the list into sublists. 2. Recursively sort each sublist. 3. Merge the sorted sublists.
What are the steps in recursive Insertion Sort?
- Base case: If the index reaches the end of the list, the list is sorted. 2. Take the element at the current index. 3. Shift the element to the left until it's in the correct sorted position. 4. Recursively call the function for the next index.
What are the steps in recursive Selection Sort?
- Base case: If the index reaches the end of the list, the list is sorted. 2. Find the smallest element in the unsorted portion of the list. 3. Swap the smallest element with the element at the current index. 4. Recursively call the function for the next index.
What are the steps in recursive Linear Search?
- Base case 1: If the element at the current index matches the target, return the index. 2. Base case 2: If the current index is the last element and no match is found, return -1. 3. Recursive step: Call the function again with the next index.
What are the steps in iterative Insertion Sort?
- Assume the first element is sorted. 2. Select the next element. 3. Compare to the sorted elements and shift until correct position is found. 4. Insert the element.
What are the steps in iterative Selection Sort?
- Find the minimum element in the unsorted portion. 2. Swap it with the first unsorted element. 3. Repeat for the remaining unsorted portion.
What are the steps in iterative Linear Search?
- Iterate through each element in the array. 2. Compare the current element with the target. 3. If a match is found, return the index. 4. If no match is found after checking all elements, return -1.
What are the steps in iterative Binary Search?
- Initialize left and right pointers. 2. While left <= right, calculate the middle index. 3. If the middle element equals the target, return the index. 4. If the target is less than the middle element, move the right pointer. 5. If the target is greater than the middle element, move the left pointer. 6. If the target is not found, return -1.
How to call the recursiveBinarySearch method?
Call recursiveBinarySearch(array, n, 0, array.size() - 1); where array is the sorted ArrayList, n is the value to search, 0 is the starting index, and array.size() - 1 is the ending index.
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
Collections.sort(arr);
System.out.println(arr);
[1, 2, 5, 8, 9]
Identify the error in the following code:
java
public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) {
int middle = (left + right) / 2;
if (left > right) { return -1; }
else if (n == array.get(middle)) { return middle; }
else if (n < array.get(middle)) { recursiveBinarySearch(array, n, left, middle - 1); }
else if (n > array.get(middle)) { recursiveBinarySearch(array, n, middle + 1, right); }
}
The recursive calls don't return a value. Should be return recursiveBinarySearch(...).
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
recursiveInsertionSort(arr, 0);
System.out.println(arr);
Assuming recursiveInsertionSort is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
recursiveSelectionSort(arr, 0);
System.out.println(arr);
Assuming recursiveSelectionSort is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
mergeSort(arr);
System.out.println(arr);
Assuming mergeSort is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
int index = recursiveLinearSearch(arr, 8, 0);
System.out.println(index);
2
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 5, 8, 9));
int index = recursiveBinarySearch(arr, 5, 0, arr.size() - 1);
System.out.println(index);
2
Identify the error in the following code:
java
public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) {
if (array.get(startingIndex) == n) { return startingIndex; }
else if (startingIndex == array.size() - 1) { return -1; }
else { recursiveLinearSearch(array, n, startingIndex); }
}
The recursive call does not increment startingIndex, leading to infinite recursion. Should be recursiveLinearSearch(array, n, startingIndex + 1).
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
int index = recursiveLinearSearch(arr, 10, 0);
System.out.println(index);
-1
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 5, 8, 9));
int index = recursiveBinarySearch(arr, 10, 0, arr.size() - 1);
System.out.println(index);
-1