Recursion
This specific code within a recursive function is one of the components of the function and usually acts on one special input value. Without it, the recursive function runs indefinitely.
Identify an example of a leaf, parent and child, a subtree, a root, and an interior node
Leaf: 4, 5, or 7
Example Parent and Child: 4 as a child to 2
Example Subtree: 2, 4, 5
Root: 1
Interior node: 2, 4, 5
This is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to obtain the final sorted array.
What is merge sort?
This is typically a numeric expression that decreases with each iteration, ensuring that the loop will terminate. For example, in a sorting algorithm like insertion sort, the size of the unsorted portion of the array decreases with each iteration.
What is a loop variant?
This is a graph where edges have a specific direction and are ordered pairs of vertices, indicating the source and the target of the edge.
What is a digraph/directed graph?
Explain the space complexity, in Big O notation, of a recursive function countNodes(node) that traverses a binary tree. Assume n is the number of nodes in the tree.
What is O(h) where h is the height of the tree?
What is the minimum and maximum possible height of a binary tree of size 10?
Min: 4
Max: 9
Given some properties about an array to be sorted and performance constraints, this sorting algorithm would be most appropriate if only a couple of elements are out of order.
What is insertion sort?
These four questions make up the 'loopy questions' also known as the loop checklist (Explain each question in your own words and describe what they mean for designing and verifying loops)
This graphical representation has the following time and space complexities
Efficiency(Space to store): O(|V|^2)
Efficiency(time to visit all edges): O(|V|^2)
Efficiency(time to determine whether edge from v1 to v2 exists): O(1)
What is an adjacency matrix?
During the execution of a recursive function fibonacci(n), draw the call stack when n = 5. Alternatively, state the maximum depth of recursion reached during the computation of fibonacci(n).
fibonacci(5)
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
What is a max depth of 5?
Which of the following is a valid binary search tree?
D is the valid search tree
Which of the following algorithms are stable and why?
Selection sort
Insertion sort
Merge sort
Quick sort
Insertion sort, merge sort
Describe the linear and binary search algorithms in your own words.
Linear Search: Iteratively checks each element in a sequence (e.g., array) from start to end until finding the target value.
Binary Search: Divides the search interval in half with each step, comparing the target value to the middle element. If the middle element matches the target, the search ends;
Given the adjacency list, adj = [[1,2], [0,2,3], [0,4], [1,4], [2,3]], and V = {0, 1, 2, 3, 4}, provide a valid graph and BFS transversal for the information given.
Will be drawn
Implement a recursion function to calculate the nth number in a fibonacci sequence
int fibonacci(int n, int curr, int prev) {
if (n == 1 || n == 2) {
return curr; // Base case: fibonacci(1) and fibonacci(2) are 1
}
return fibonacci(n - 1, curr + prev, curr); // Recursive call
}
What is the postorder traversal of the below tree? - Tree D from the previous problem
1,5,3,9,8,7.
Given a loop invariant, determine whether it is consistent with the outer loop of selection sort, the outer loop of insertion sort, an insertion procedure for insertion sort, or a partitioning algorithm for quicksort.
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
// Inner loop invariant for finding the minimum element
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// Swap elements to place the minimum at the beginning
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
Loop invariant for the outer loop of selection sort
You are given Java code for a loop with missing pieces How would you correct and complete the loop to ensure correctness?
// Precondition: array is not null and contains elements
// Loop Invariant: The elements before current index are not equal to the target
// Postcondition: index is the position of the target in the array or -1 if not found
int[] array = {5, 2, 7, 1, 9};
int target = 7;
int index = -1;
for (int i = 0; i < _______ ; i++) {
if (_________ ) {
index = ___;
break;
}
}
// Precondition: array is not null and contains elements
// Loop Invariant: The elements before current index are not equal to the target
// Postcondition: index is the position of the target in the array or -1 if not found
int[] array = {5, 2, 7, 1, 9};
int target = 7;
int index = -1;
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
index = i;
break;
}
}
Given the following weighted graph and starting at node A, this is the order in which nodes are settled by Dijkstra’s algorithm.
Graph (edges are shown as: Node1 --(weight)--> Node2): Starting Node is A
A --(1)--> B
A --(4)--> C
B --(2)--> C
B --(5)--> D
C --(1)--> D
D --(3)--> E
Settle A → It has the smallest distance (0).
B gets updated to 1 (via A).
C gets updated to 4 (via A).
→ Settled order so far: A
Settle B → Smallest distance (1).
C gets updated to 1 + 2 = 3 (better than 4).
D gets updated to 1 + 5 = 6.
→ Settled order: A, B
Settle C → Smallest distance (3).
D gets updated to 3 + 1 = 4 (better than 6).
→ Settled order: A, B, C
Settle D → Smallest distance (4).
E gets updated to 4 + 3 = 7.
→ Settled order: A, B, C, D
Settle E → Only one left, with distance 7.
→ Settled order: A, B, C, D, E
Write a recursive method 'int sumDigits(int number)' that returns the sum of the digits of a given number. The method should sum the digits of the number until only a single digit remains.
Example: Input: 1234
Output: 1 (because 1 + 2 + 3 + 4 = 10, then 1 + 0 = 1) Implement the 'sumDigits' method.
public static int sumDigits(int number) {
if (number < 10) {
return number;
}
int sum = number % 10 + sumDigits(number / 10);
return sum < 10 ? sum : sumDigits(sum);
}
Turn getHeight() into an instance method in the TreeNode class.
Hint: have a public function called getHeight that calls a private recursive function, both in the TreeNode class
Hint 2: You can utilize Math.max()
public int getHeight() {
return getHeightRecursive(this);
}
private static int getHeightRecursive(TreeNode node) {
if (node == null) {
return 0; // Base case: empty subtree has height 0
}
int leftHeight = getHeightRecursive(node.left);
int rightHeight = getHeightRecursive(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
Given a class with two observers, declare and implement a Comparator that orders instances of the class first by one observable, then, in the case of a tie, by the other.
import java.util.Comparator;public class MyClassComparator implements Comparator<MyClass> {
@Override
public int compare(MyClass obj1, MyClass obj2) {
//code here
}
import java.util.Comparator;
public class MyClassComparator implements Comparator<MyClass> {
@Override
public int compare(MyClass obj1, MyClass obj2) {
if (obj1.getObservable1() != obj2.getObservable1()) {
return Integer.compare(obj1.getObservable1(), obj2.getObservable1());
} else {
return Integer.compare(obj1.getObservable2(), obj2.getObservable2());
}
}
}
Implement a method binarySearch in Java that performs a binary search on a sorted array of integers. Define and explain the loop invariant that ensures correctness throughout the binary search algorithm.
public class BinarySearchExample {
// Method to perform binary search on a sorted array of integers
public static int binarySearch(int[] array, int target) {
int low = 0;
int high = array.length - 1;
// Loop invariant: The target, if present, is within the range [low, high]
while (low <= high) {
int mid = low + (high - low) / 2;
// If target is found at mid, return mid index
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
// If target is greater, ignore left half
low = mid + 1;
} else {
// If target is smaller, ignore right half
high = mid - 1;
}
}
// Target not found in the array
return -1;
}
}
This counts as valid code/psuedocode for Djistkra's algorithm.
What is
while(!frontier.isEmpty()){
Vertex v = frontier.removeMin();
for (Edge e : v.outgoing){
Vertex neighbor = e.to;
double dist = v.dist + e.weight;
if (dist < neighbor.dist){
neighbor.dist = dist;
frontier.addOrUpdate(neighbor, dist);
}
}
}