Fundamentals
The fundamental technique in recursion that involves identifying the simplest version of a problem that can be solved directly
base case
What acronym describes the last in first out access pattern. what ADT uses this?
This ADT provides storage for information with an order imposed on it's elements, but without strict access limitations
List
Given some Bounded Array Based Queue, describe ALL the requirements for removing an element from the queue
is there an element to remove
remove the element, decrement position counter
These two fundamental language constructs are used to implement ADT's in Java
Arrays and linked lists
Recursive problem solving requires us to answer three main questions when trying to problem solve - what are they?
Base case
general case - does the recursive step correctly solve the general problem
smaller caller - do recursive cals operate on smaller and smaller problems leading to the base case
This queue implementation technique involves using a circular pattern to efficiently manage a fixed size array
Floating point technique
This time complexity characterizes the worst-case scenario for inserting an element in the middle of a list.
What is O(n)?
Given some linked list queue, describe ALL the requirements for removing an element from the queue
is there an element to remove
remove the element by changing head reference as needed
A set of possible values for an encapsulated data type, plus the specification of operations that can be performed on it
ADT
The recursive processing technique that involves searching a sorted array by dividing the search interval in half
Binary Search
In a linked list implementation of a queue, these two references are crucial for efficient enqueue and dequeue operations.
Head and rear
When searching an unsorted list for a specific element, this time complexity represents a sequential search.
O(N)
Given a LinkedList walk through the steps required to sum every third element
Traverse LL, keep counter, if counter %3, increment sum
What are the three levels of detail used to describe how we view ADT's, what does each concern.
What are the specification (abstract), application (client), and implementation levels
What are the main pro's and cons to recursion
pro - code clarity
con- stack overhead
Why?
Array based - not unbounded
If I have a O(N2) algorithm, what are the cases above this that I want to work towards?
What is O(N2) called?
0(1) – Bounded time
The amount of work is bounded by a constant and is not dependent on the size of the problem
0(log2N) – Logarithmic time
The amount of work depends on the logarithm in base 2, of the size of the problem
These algorithms successively cut the amount of data to be processed in half at each step
0(N) – Linear time
The amount of work is some constant times the size of the problem
Algorithms that work through all the data to arrive at a conclusion
(N log2N) - Log-Linear Complexity
The amount of work is some constant times the size of the problem
Algorithms that apply logarithmic algorithms N times
O(N2) - quadratic
You're given a function that searches an unsorted array with O(n) time complexity. Describe the specific algorithmic transformation that would reduce the time complexity to O(log n), explaining the key principles that enable this optimization.
Include the tradeoffs of this, when is this trade off worth it?
The trade off is the added complexity in the add case
this trade off is worth it if we are searching far more than adding/removing
Explain why O(N) + O(N) resolves to O(N) but O(N) * O(N) is treated differently?
What is sequential operation dominance
Write a recursive Java method that calculates the sum of all even numbers from N down to 0.
The function should decrement N by 1 with each recursive call until it reaches 0.
public static int sumEvenNumbers(int n) {
if (n <= 0) {
return 0;
}
if (n % 2 == 0) {
return n + sumEvenNumbers(n - 1);
}
else {
return sumEvenNumbers(n - 1);
}
You're the lead architect designing a massive text editor with an unlimited undo/redo stack capable of handling millions of actions.
Explain which data structure you would use to build out this application
Array :)
Linked lists suffer from
Excessive memory overhead (each node requires additional reference pointers)
What are the three complexity cases we consider, which one is the driving force behind BigO and why?
Best case
Average case
Worst case
Walk through the roles of each main phase of our ADT building structure. Outline the requirements each phase is required to implement and their purpose.
Walk through how this works when building the list ADT
Abstract, implementation, application
build interface, build class, apply program