Recursion and Iteration
What is recursion
a function calling itself
Name the searching algorithms and a key difference between the two.
Name the simple sorting algorithms and describe each.
Binary Search and Linear Search. Binary search requires list to be sorted
Bubble, Insertion, and Selection
Bubble sort moves down using nested loops and swaps two items if the first is greater than the second.
Selection sort divides the list into sorted and unsorted lists and the smallest item in the unsorted moves to end of the sorted list.
Insertion sort divides the list into sorted and unsorted portions and inserts the item of the unsorted list in the correct place of the sorted list.
What are the errors built into the exception library? What can they identify? An example?
Logic error: a common type are syntax errors; can be identified before the program is ran.
an example: looping an array of 5, 10 times
Runtime error: occurs during the execution phase, while program is running.
an example: zero division
What is a LIFO structure?
What is a FIFO structure?
Last in First out, Stack
First in First out, Queue
What makes all the simple sorts complexity O(N2)?
What do the structures do?
The nested loops make up the N2 time complexity. Each loop has a big O that is N and you multiply both to get N2.
The inner loop handles comparing elements and moving them if greater than. The outer loop restarts at the beginning of the array/ linked list each time to prepare to run back through comparisons.
What stops a recursive call
Base case
Time complexity for heapsort. Why?
Typical: O(N log N); same as Quick and Merge.
Worse case: O (N2)
The time complexity is N log N because the logN comes from the recursive case of operating the heap and the N comes from rebuilding the array in the correct order.
What is a throw, catch, and try?
Try defines a block of code to be tested for errors during execution
Throw detects the error and sends to the catch(the bridge)
Catch is a statement that is executed based on the throw type sent and if the error occurs.
A try must have a catch but can also have multiple.
How do you add/delete an instance in a stack
stack.pop(), stack.push()
T/F: A try will reach as long as the program detects an error. No throw required.
FALSE; try sections MUST have one throw to reach a catch.
The error you get when you try to infinitely recurse
Stack Overflow, or Max recursion depth exceeded
Best way to search through a sorted list to find a number.
What if it is the first element?
Binary search
The best way would be linear then because it would be found instantly.
What throw is needed to execute this catch?
catch (const char *err)
{
//code to be executed
}
throw("Something went wrong")
The pointer that a Queue pushes to?
What is last/ tail
FREE RESPONSE: Choose one topic for the test and break it down to the class.
Varies depending on students' choice: should include keywords, purpose, and pros and cons of the concept
Explain how the following recursive case works:
int factorial( int n)
{ if(n==0)
return 1;
return ( n* factorial(n-1) )
}
Expected answers:
-explains base case
-how it is not infinite
- what if n was passed as 5
Describe quick sort
Get a pivot value and create 3 lists that contain values less than, equal to, and greater than the pivot. This is recursively done until all lists are of size one, then combined together to sort the list.
What is the expected catch for the following throw?
throw runtime_error("Try again. Sorry")
catch(runtime_error &err)
{
cout<<err.what();
}
The stack that results from the following operations:
Push(1)
Push(2)
Push(3)
Pop()
Pop()
Push(4)
Push(5)
Push(6)
Pop()
Push(7)
1 4 5 7 <- Top
Given the following array:
[15, 35, 40, 56, 98, 101, 125, 145, 166, 255]
Using linear search, how many searches are done to find 166?
Using binary search, how many searches are done to find 166?
Linear: 9
Binary: 3
What's the difference between a recursive and iterative case?
Recursive case uses more space in memory, every recursive call requires additional space in the stack. The recursive case only terminates when a base case is recognized so as the call is repeated, the more structures are open.
Iterative case is mean for loop-based repetition. More efficient and faster. Uses less memory as it loops until the condition is met.
Describe Merge sort
Recursively divides the list down to lists of size one, then merges them back together to sort the list
What is the structure of a default catch? When is the default catch used?
catch(...)-- no spaces
A default catch is used as a catch all statement, in the case that an exception type was forgotten.
What is a Stack based process you use daily?
What is a Queue based process you use daily?
Stack: undo button, browsers back and forward, etc.
Queue: printers, buffers, to do list, etc.
Trace code practice: looking at the following block of code, what is the potential output.
cout<<"Enter a number";
int n;
cin>> n;
//input 0
n=9;
try{
if (n==0)
throw 0;
}
catch(int num_exception)
{cout<< "Zero division"}
cout<< 1/n;
cout<< "goodbye"<<endl;
1/9goodbye