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, the root
1
/\
2 3
/\ \
4 5 7
Leaf: 4, 5, or 7
Example Parent and Child: 4 as a child to 2
Example Subtree: 2, 4, 5
Root: 1
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 a condition a condition [among program variables] that is necessarily true immediately before and immediately after each iteration of a loop. (Note that this says nothing about its truth or falsity part-way through an iteration.)
What is a loop variant?
This is a synchronization construct that allows multiple threads to wait at a specific point until all participating threads have reached that point.
What is a barrier?
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(n) 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 condition variable is provided by the Object class and wakes up all threads that are waiting on the same object, giving them a chance to resume execution
What is notifyAll()?
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?
This property must hold true for all nodes in a balanced binary search tree to ensure logarithmic height.
What is that the height difference between the left and right subtrees of any node is at most 1?
These two following sorting algorithms are considered stable because they preserve the relative order of elements with equal values.
What is Insertion sort and 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 these two sequences can deadlock occur? If yes, propose an alteration to one of the sequences.
Deadlock can occur if these processes happen simultaneously.
Swapping step 4 and step 5 in process 2 would help the processes avoid deadlock because the resources are acquired in the same order.
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 tree below/drawn on the board?
1
/ \
2 3
/ \ \
4 5 6
What is 4,5,2,6,3,1?
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;
}
}
Write code to execute a function on a new thread using Java's Thread class API.
Runnable task = () -> {
// Code to be executed on a new thread
System.out.println("Task executed on thread: " + Thread.currentThread().getName());
};
Thread thread = new Thread(task);
thread.start();
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: 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. Return -1 if the target is not within the array.
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;
}
}
Complete the implementation of the Counter class by adding synchronization blocks to the increment and decrement methods to protect the counter from concurrent access issues.
public class Counter {
private int count;
public Counter(int initialValue) {
this.count = initialValue;
}
public void increment() {
// _______________ (this) {
count++;
}
}
public void decrement() {
__________________ {
count--;
}
}
public int getCount() {
return count;
}
}
public class Counter {
private int count;
public Counter(int initialValue) {
this.count = initialValue;
}
public synchronized void increment() {
// Synchronized block to increment the counter
synchronized (this) {
count++;
}
}
public synchronized void decrement() {
// Synchronized block to decrement the counter
synchronized (this) {
count--;
}
}
public synchronized int getCount() {
return count;
}
}