COMPUTER SCIENCE CSCI 1112 Final Exam

COMPUTER SCIENCE CSCI 1112 Final Exam "Justify why a while loop is recommended for iteration in a linked list instead of a for loop? - CORRECT ANSWER It is recommended because a linked list does not have a fixed length that can be easily expressed as an index range." "What is an iterator? - CORRECT ANSWER An object that enables the traversal of a data structure and access to its elements without exposing its underlying implementation." "How does using an iterator for iteration differ from indexed based iteration? - CORRECT ANSWER Iterator-based iteration does not rely on index values to access elements, but instead uses a next() method to move through the elements of the data structure one by one. In contrast, indexed based iteration relies on accessing elements by their index position." "Why should iterator based iteration be used for linked lists over index based iteration? - CORRECT ANSWER Linked lists are not indexed-based data structures, meaning that accessing elements by their index position would require iterating through the list until the desired element is reached. This process can be inefficient and time-consuming, especially for large lists. In contrast, using an iterator allows for efficient traversal of a linked list, since it moves from one element to the next without the need to iterate through the entire list." "What is a policy layer? - CORRECT ANSWER An abstraction layer that prescribes the interface for a data type but also specifies one or more rules that the data type behaviors must always ensure such as FIFO and LIFO." "Explain First-in First-out (FIFO) - CORRECT ANSWER The oldest item must be the next item removed" "Explain Last-in First-out (LIFO) - CORRECT ANSWER The newest item must be the next item removed" "Define the interface for a stack - CORRECT ANSWER push(object) - adds an element to the top of the stack pop() - removes the element at the top of the stack isEmpty() - determines if the stack has any elements" "Define the interface for a queue - CORRECT ANSWER enqueue(object) - appends an element to the end of the queue dequeue() - removes the element at the front of the queue isEmpty() - determines if the queue has any elements" "Define the insertion/removal policy for a stack - CORRECT ANSWER A stack is a linear data structure in which the insertion and deletion operations are only performed at the top of the stack (LIFO)" "Define the insertion/removal policy for a queue - CORRECT ANSWER Elements are removed in the same order they are inserted (FIFO)" "Describe the implementation of a stack using an array - CORRECT ANSWER The push operation is implemented by storing the new element at the first index and shifting all subsequent elements down one index. The pop operation is implemented by returning the element at the first index and shifting all subsequent elements up one index." "Analyze the efficiency of stack operations when implemented using an array - CORRECT ANSWER For push and pop operations, all elements must be shifted; therefore, it has a linear time complexity. Additionally, arrays require reallocation to accommodate for multiple push calls; therefore, it is generally a linear time operation." "Describe the implementation of a stack using a linked list - CORRECT ANSWER Linked lists can implement a stack by creating a singly-linked-list with only a head to achieve all stack behaviors in constant time as elements can be pushed an popped from the top of the list without having to reallocate an array." "Analyze the efficiency of stack operations when implemented using a linked list - CORRECT ANSWER The efficiency of push and pop operations are O(1) or constant time as the head can be used to add and remove elements by simply altering its pointer." "Describe the implementation of a queue using an array - CORRECT ANSWER The enqueue operation is implemented by adding a new element after the last element and the dequeue operation requires the removal and return of the element at the first index and then shifts all subsequent elements one index to the left." "Analyze the efficiency of queue operations when implemented using an array - CORRECT ANSWER The efficiency of enqueue and dequeue operations using an array is typically linear time as an array must be periodically reallocated to support multiple enqueue operations and the dequeue operation requires the shift of each successive element." "Describe the implementation of a queue using a linked list - CORRECT ANSWER With the use of a tail, enqueue simply alters the tail pointer to the new element and dequeue alters the head pointer to point to the second element, resulting int he removal of the first element." "Give an example in Java of a deep copy. - CORRECT ANSWER int [] A = new int[5]; A[0] = 1; A[1] = 10; int[] B = new int[5]; for i=0 to 5-1 B[i]=A[i]" "When a primitive value is copied, is that a deep copy or a shallow copy? - CORRECT ANSWER Deep copy" "When a reference or non-primitive value is copied, is that a deep copy or a shallow copy? - CORRECT ANSWER Shallow copy" "Define "state" in terms of computing. - CORRECT ANSWER The combination of a variable or object's original values plus any modifications that occurred up to a certain point in a program." "What does it mean to say that a program evolves through its execution? - CORRECT ANSWER As a program executes, the values of some variables - whether they'd be primitive or reference - changes, therefore, influencing the outcome of a program." "Why is timing a program a poor way to measure its performance? - CORRECT ANSWER Some programs may be more complex than others which will cause them to take longer regardless of whether it is the most efficient solution." "What variable affect the execution time of a program? - CORRECT ANSWER Hardware, software, and CPU" "Why do we use algorithmic time complexity to measure a program's efficiency rather than execution time? - CORRECT ANSWER Time complexity refers to the number of times a statement iterates rather than determining the actual time a program takes to execute because that can rely on many factors that may be out of the programmer's control." "What are the benefits of using an abstract measure like algorithmic time complexity over a rigidly specific measure like execution time? - CORRECT ANSWER It allows programmers to not bother with constants of proportionality (coefficients) as they are irrelevant in comparison. Smaller terms also do not have much of an effect in a function; therefore, they can be omitted (ex. 3n^3 + 12n^2 + 16n -> O(n^3) depicts the real growth of the function)." "Why can we ignore coefficients and smaller terms in an algorithmic time complexity analysis? - CORRECT ANSWER Constants of proportionality are irrelevant when determining time complexity analysis." "What is Big Oh notation? - CORRECT ANSWER A special notation developed for approximate analysis that is usually written as a function to demonstrate the time it takes for a program to execute" "Why does the growth rate meaningfully capture the efficiency of a program over its entire input? - CORRECT ANSWER It demonstrates the decrease in efficiency as a program's input is increased. Some decreases in efficiency are more substantial than others." "Why do we generalize time complexity analysis to an evaluation in terms of "n - the size of the input"? - CORRECT ANSWER Because n is what is modified by adding loops that increase the time complexity of a program." "Why does time complexity analysis capture information about arbitrarily large data sets that cannot be captured by measurement of execution time? - CORRECT ANSWER When measuring execution time of arbitrarily large data sets, the length of time could also be arbitrarily large; however, measuring time complexity allows us to predict the performance of an arbitrarily sized data set." "Why does time complexity analysis allow us to measure efficiency of pseudo code? - CORRECT ANSWER We can measure the amount of operations in our pseudocode to determine the most efficient solution when writing our program." "Iteration - characteristics and behaviors - CORRECT ANSWER A function that repeats a block of code in a specified order until a condition is reached." "Recursion - characteristics and behaviors - CORRECT ANSWER A function calling itself directly or indirectly until a specific condition is reached." "Iterative approach of Power - CORRECT ANSWER power(b,e) result=1; for i=1 to e: result = result * b; return result; time complexity: O(n) where n is the size of e" "What is the default value assigned by Java to every variable if an initial value is not explicitly provided? - CORRECT ANSWER 0" "A memory location contains the value 100. If the value at that location is interpreted as a boolean, what value will be produced? - CORRECT ANSWER True because if a value is 0 it will be interpreted as false; however, any value other than 0 will be interpreted as true" "A memory location contains the value 0. If the value at that location is interpreted as a non-primitive, what value will be produced? - CORRECT ANSWER null" "What are the two "meta-types" in java? - CORRECT ANSWER Primitive and Non-primitive" "Give examples of primitive types in Java - CORRECT ANSWER -int -float -char -double -boolean" "Give examples of non-primitive or reference types in Java - CORRECT ANSWER -String -Object -Arrays -Classes" "How is the value stored in a non-primitive type interpreted? - CORRECT ANSWER The variable stores a memory location (address) where the object is stored" "Assuming an infinite universe, why would it be impossible to prove that life does NOT exist elsewhere in the universe? - CORRECT ANSWER There will always be other places to look" "What does it mean to use a "proof by exhaustion" or "brute force" strategy? - CORRECT ANSWER By looking everywhere or trying every possible combination" "On this computer, why does the number of operations remain constant for the subtract function? - CORRECT ANSWER Because subtraction requires two functions: negation and addition; therefore, it doesn't change no matter the numbers." "On this computer, why does the number of operations in the multiply function vary with the size of the parameters? - CORRECT ANSWER The second number (right) determines how many iterations are done in a for-loop which utilizes addition each time it iterates, therefore, increasing the number of operations by one for each iteration." "What is stored in the program block and what is stored in the data block? - CORRECT ANSWER Code is stored in the program block and data is stored in the data block." "The data block is divided into three segments. What are these three segments? - CORRECT ANSWER Global, stack, and heap" "Define variable scope. - CORRECT ANSWER The block of a program where a variable is declared, used, and can be modified." "What are the three scoping levels associated with Java? - CORRECT ANSWER Local, global, and instance" "What is the lifespan of a variable and how does variable lifespan relate to variable scope? - CORRECT ANSWER The lifespan of a variable starts when the variable is allocated and ends when the variable is deallocated. Scope determines the lifespan of a variable." "What is the visibility of a variable and how does variable visibility relate to variable scope? - CORRECT ANSWER The visibility of a variable controls how much of the rest of the program may access it. Scope determines the visibility of a variable." "What is the lifespan and visibility of a global variable? - CORRECT ANSWER Global variables are visible everywhere and survive as long as the program is running." "What is the lifespan and visibility of a local variable? - CORRECT ANSWER Local variables are found within functions and survive from the start of the function to the end of the function." "What is the lifespan and visibility of an instance variable? - CORRECT ANSWER Instance variables are visible within a class except within static methods and survives as long as the object stays in memory." "How does the scope of a variable relate to the memory allocation of that variable? - CORRECT ANSWER A variable declared within a function has a function scope which is then allocated in memory once that function is called. Once the function returns something, the execution of the function ends and the variable goes out of scope which deletes it from memory." "How does the declaration of a variable relate to its scope? - CORRECT ANSWER A variable only exists in the scope at which it is created." Compute the powers of 2 from 2^0 to 2^8 - CORRECT ANSWER 1, 2, 4, 8, 16, 32, 64, 128, 256" "Explain why the base 2 logarithm predicts the maximum number of times a discrete set can be repeatedly subdivided in half - CORRECT ANSWER Logs are "reverse powers" and base 2 models repeated halving ex. log(16) = 4 -> 2^4" "With diminishing rainfall over the years, water reservoirs are stressed throughout the country. Imagine a scenario where half the preceding years rainfall is collected each year. If the local reservoir has 50 feet of water this year, in how many years will the depth be less than 1 foot? - CORRECT ANSWER 2^6 = 64 (64 is the closest base 2 log to 50), therefore, it would take 6 years for the depth of the reservoir to reach less than 1 foot" "You are given a 416 card deck (eight 52 card decks) of playing cards for blackjack. You divide the deck precisely in half resulting in two decks of 208 cards. You repeat this process again on each of the generated decks which results in you having four decks of 104 cards. Model this process with a simple mathematical expression and use that model to predict the maximum number of times you can repeat this process before ending up with decks consisting of either 1 or zero cards. - CORRECT ANSWER 2^9 = 512 (512 is the closest base 2 log to 416), therefore, it would take 9 times to end up with a deck consisting of 1 or 0 cards" "You are given a deck of 26 cards each with a different letter of the English alphabet on it. You divide the deck in half resulting in two decks of 13 cards each. You repeat this process resulting in four decks containing either 6 or 7 cards. If you continue to repeat this process, eventually you will end when you have a number of decks consisting of either 0 or 1 cards. - CORRECT ANSWER 2^6 = 32, therefore, it would take 6 times" "You have found a crypto coin that is projected to double in value year over year for the next seven years. If the coin is currently worth $0.20, the projection predicts it to be worth $0.40 next year and $0.80 the year after that, and so forth. Model the expected growth for this coin through seven years using either a diagram or mathematical formula. - CORRECT ANSWER 2^7 = 128, therefore, the value of the coin will be $12.80 after 7 years" "What two minimum pieces of information are required for every Java variable declaration? - CORRECT ANSWER Type and label" "Given the following code snippet, explain what is copied on line 2? int[] A = new int [10]; Int[] B = A - CORRECT ANSWER A shallow copy is created; the address that refers to the same data as array A, therefore, altering array B will alter array A." "Explain what is meant by the term "deep copy". - CORRECT ANSWER Creating a copy at the most fundamental level using the "new" keyword." "Explain what is meant by the term "shallow copy". - CORRECT ANSWER Points to the same address, therefore, altering one will alter the other." "Contrast the idea of a deep copy with a shallow copy. - CORRECT ANSWER A deep copy creates an independent variable while a shallow copy references the same data as the original." "Give an example in Java of a shallow copy. - CORRECT ANSWER int[] one = new int{3,4,5,6,7}; int[] two = one; two[2] = 8; //one = {3,4,8,6,7}, two = {3,4,8,6,7}" "Recursive approach of Power - CORRECT ANSWER power(b,e) if(e==0) return 1; return b* power(b, e-1) time complexity: O(n) where n is the size of e" "Iterative approach of Fibonacci - CORRECT ANSWER fib(x) f(i-2)=0 f(i-1)=1 f(x)=f(i-2) for(i=1 to x) fib(x)=fib(i-1)+fib(i-2) fib(i-2)=fib(i-1) fib(i-1)-fib(x) return fib(x) time complexity: O(n) where n is the size of x" "Recursive approach of Fibonacci - CORRECT ANSWER fib(x) if(x==0) return 0; if(x==1) return 1; return fib(x-1) + fib(x-2) time complexity: O(n^2) where n is the size of x" "What types of problems are good candidates for recursive implementations? - CORRECT ANSWER Self-similar subproblems" "What is meant by "a problem that can be reduced into self-similar subproblems"? - CORRECT ANSWER A problem that can be broken down into problems of the same type with smaller inputs." "Why are reductive problems good candidates for recursion? - CORRECT ANSWER Reducing a method's parameters to its simplest problem (base case) allows control over recursion." "What is a base case? - CORRECT ANSWER The most simple problem that cannot be solved using a recursive approach." "What is the self-similar subproblem in a maze? - CORRECT ANSWER The decision made at each intersection as the maze just becomes a smaller maze at each point." "Why is a maze an exploration problem? - CORRECT ANSWER Because the subject explores all options from a certain point in the maze and if no options are a solution, then the subject returns to its previous position." "Describe backtracking in a Maze problem - CORRECT ANSWER At a certain point, the subject in the maze explores all options from that point. If none of those lead to a solution, then the subject returns to its previous position." "Describe the N-Queens problem - CORRECT ANSWER It determines if it is possible to place "n" amount of queens where n is the length of the chess board (a 4x4 chess board looks to see if 4 queens can fit) without them threatening one another." "What is the self-similar subproblem in N-Queens? - CORRECT ANSWER After placing one queen, you render a row and a column unusable, causing you to now look at a smaller board." "Why is the N-Queens problem an exploration problem? - CORRECT ANSWER Because all possible solutions are explored before determining if the problem has a solution." "Describe backtracking in the N-Queens example - CORRECT ANSWER If a conflict is found (aka a queen placed threatens another queen), then the algorithm backtracks to its previous decision." "Describe the Towers of Hanoi problem - CORRECT ANSWER Determines how long it will take monks to move "n" discs given the limitation that monks may not place larger discs on smaller discs." "Does Towers of Hanoi involve backtracking? - CORRECT ANSWER No, because the problem is always going to have a solution, it is only a matter of how long the process will take." "What is an application of Towers of Hanoi? - CORRECT ANSWER By breaking the problem down by reducing the number of discs to the most simple case (1 disc). It demonstrates how the time complexity is approximately O(2^n) where n is the number of discs." "Contrast "tail recursion" with "backtracking" recursion - CORRECT ANSWER Tail recursion is the last thing that happens in the method before it returns while backtracking recursion returns to a prior decision to find a solution. Tail recursion is unable to undo changes while backtracking recursion requires the undoing of prior decisions to reach a solution." "What are the downsides to recursion? - CORRECT ANSWER Recursion costs more time and space than iteration." "What are the benefits to recursion? - CORRECT ANSWER when done right, recursion can use solutions of small-scale problems to solve large-scale problems." "Define the swap algorithm - CORRECT ANSWER Swaps two values using a temporary variable" "Summarize the strategy for selection sort - CORRECT ANSWER compares each candidate to find the best selection and move it to the next available position" "Define pseudocode for selection sort - CORRECT ANSWER for(i=0 until h) -assigns a smallest value at A[i] -assigns a variable that refers to position of i -for(j=i+1 until h) -if(value of j < smallest) -update smallest to be value of j -update position to be j swap values;" "Analyze the efficiency for selection sort - CORRECT ANSWER O(n^2) where n is the size of the input since it utilizes a nester for-loop" "Summarize the strategy for bubble sort - CORRECT ANSWER focuses on the relationship between neighbors starting from the end of the array" "Define pseudocode for bubble sort - CORRECT ANSWER for(i=0 until length-1) for(int j=length-1 until i) -if(A[j] < A[j-1] -swap" "Analyze the efficiency for bubble sort - CORRECT ANSWER O(n^2) where n is the size of the input since it utilizes a nested for loop" "Summarize the strategy for insertion sort - CORRECT ANSWER orders an element at the time of insertion" "Analyze the efficiency for insertion sort - CORRECT ANSWER O(n^2) where n is the size of the input since it utilizes a nested for loop" "Define pseudocode for insertion sort - CORRECT ANSWER for(i=0 until h) for(j=i;j>0 && (A[j] < A[j-1]); j--) -swap values at j and j-1" "Summarize the strategy for quicksort - CORRECT ANSWER separating larger arrays into smaller arrays depending on their relationship with the partition element (done recursively since same steps are done when the array becomes smaller)" "Analyze the efficiency of quicksort with randomized input - CORRECT ANSWER O(nlogn) where n is the size of the input because log n determines the maximum number of times a set can be split in half until it is a sorted array of 1 element" "Analyze the efficiency of quicksort assuming the input is ordered - CORRECT ANSWER O(n^2) where n is the size of the input because the pivot (typically leftmost or rightmost element) will create two extremely unbalanced arrays as one array will have 1 element and the other will have (n-1) elements." "Why do we sort? - CORRECT ANSWER It allows us to access multiple pieces of data in a preferred order" "What are the characteristics of a list? - CORRECT ANSWER A list is an ordered collection of elements where each element can be of any data type. Characteristics: -ordered: each element has a specific position in the list -mutable: they can be modified by adding, removing or changing elements -dynamic: lists can grow or shrink as elements are added or removed -heterogeneous: can contain elements of different data types -indexable: each element can be accessed using an index" "What do we mean by absolute position? - CORRECT ANSWER Defines the position of an object in it's list" "What do we mean by relative position? - CORRECT ANSWER Describes where objects are relative to each other" "What do we mean by "the list is an abstraction"? - CORRECT ANSWER a list is a conceptual representation of a collection of elements rather than a physical or tangible object such as a shopping list" "What is an interface? - CORRECT ANSWER An interface defines how we interact with something and how that thing will behave when we interact with it. Interactions are the inputs of an algorithm and behaviors are the outputs of the algorithm." "What does encapsulation mean? - CORRECT ANSWER a principle of object-oriented programming that involves building data and methods together into a single unit, called a class, and restricting access to the internal workings of that class from outside code. This ensures the data is only modified in appropriate ways" "What does information hiding mean? - CORRECT ANSWER keeping the internal details of a class hidden from outside code. This can prevent changes to the internal workings of the class." "Why do we create abstraction layers? - CORRECT ANSWER They simplify context systems by breaking them down into smaller, more manageable components. Each layer provides a simplified interface to the layer below it, while hiding the internal workings of that layer." "What does Abstract Data Type mean? - CORRECT ANSWER A mathematical model for data types, defined by its behavior (semantics) from the pov of a user of the data, specifically in terms of possible values, possible operations on data of this type and the behavior of these operations." "How is an abstract type typically expressed in Java? - CORRECT ANSWER abstract data types are typically expressed using interfaces. an interface defines a set of method signatures that must be implemented by any class that implements that interface. This allows for a high degree of abstraction and flexibility, as different implementations of the same interface can be used interchangeably" "What is the list interface? - CORRECT ANSWER -add(node) appends an element to the end of the list -remove(int k) removes an object from the list -size() retrieves the size -get(int d) retrieves the i-th element" "What data structures implement a list? - CORRECT ANSWER Linked List, ArrayList, array" "Analyze the efficiency of append for an array based list - CORRECT ANSWER O(n) where n is the number of elements in the list because it must copy the entire array into a new array in order to add one element (arrays have a fixed size and usually must be resized)" "Analyze the efficiency of remove for an array based list - CORRECT ANSWER O(n) where n is the number of elements in the array because all elements after the removed element need to be shifted one position to the left to fill in the gap." "Analyze the efficiency of append for a linked list based list - CORRECT ANSWER -O(1) if provided a tail pointer as the pointer can be modified to the new value -O(n) if there is only a head pointer as the list must be traversed to the end to insert" "Analyze the efficiency of remove for a linked list based list - CORRECT ANSWER O(1) because it uses the head to remove the element at the beginning of the list" "What is the role of the head pointer in a linked list? - CORRECT ANSWER The head pointer points to the first node in the list and serves as the starting point for traversing the list and accessing its elements." "Define the structure of a singly-linked-list node - CORRECT ANSWER Each node has only one link that points to the next node in a linked list" "How is the end of a linked list represented - CORRECT ANSWER the node points to null" "Is it necessary to maintain a head pointer for a linked list? - CORRECT ANSWER yes, it is necessary to identify the beginning of the list and support operations." "Is it necessary to maintain a tail pointer for a linked list? - CORRECT ANSWER no, a tail pointer is a design choice and may optimize efficiency for appending many elements." "Analyze the efficiency of adding to the head of a linked list - CORRECT ANSWER O(1) because the pointers of two variables are reassigned, meaning the efficiency is constant element = new Node() = head head = element" "Analyze the efficiency of removing from the head of a linked list - CORRECT ANSWER O(1) because the head pointer can simply be updated to point to the second node in the list, effectively removing the first node from the list." "Analyze the feasibility of removing from the tail of a linked list - CORRECT ANSWER It is not feasible without maintaining a tail pointer because the entire list must be traversed to find the second-to-last node in the list, in order to update its next pointer to null and effectively remove the last node from the list. With a tail pointer, however, removing from the tail is O(1) as the tail pointer can be updated to point to the second-to-last node and its next pointer set to null." "Define the structure of a doubly-linked list node - CORRECT ANSWER consists of a data field which stores the value of the element, a next field that points to the next node in the list, and a prev field that points to the previous node in the list." "What improvements does a doubly-linked list node bring to a list implementation. - CORRECT ANSWER it allows for efficient removal from the tail of the list, as the prev pointer can be used to quickly access the second-to-last node in the list and update its next pointer to null. It also allows for efficient backwards traversal of the list, as the prev pointer can be used to move backwards from any node in the list. This makes operations such as iterating over the list backwards or accessing elements by index from the end of the list more efficient." "What additional costs does a doubly-linked list bring to a list implementation? - CORRECT ANSWER It costs more in terms of space complexity because it stores two pointers (one for the previous node and one for the next node) instead of just one like in a singly-linked list node. This increases the memory overhead of each node which can become significant when dealing with large lists." "Contrast the time complexity of list operations in a linked list against list operations in an array based list. - CORRECT ANSWER In a linked list, adding or removing nodes from either end of the list (head or tail) is constant time complexity O(1), while adding or removing nodes from an arbitrary position in the list is linear time complexity O(n/2) on average, where n is the size of the list. Iteration over the list is also linear time complexity O(n).In an array based list, adding or removing elements from the end of the list is constant time complexity O(1) on average (assuming no resizing is required), while adding or removing elements from an arbitrary position in the list is linear time complexity O(n), where n is the size of the list. Iteration over the list is also linear time complexity O(n)." "Contrast the space complexity of list operations in a linked list against list operations in an array based list. - CORRECT ANSWER In a linked list, the space complexity is linear to the number of nodes in the list. Each node requires additional memory to store the value and the pointers to the previous and next nodes.In an array based list, the space complexity is also linear to the number of elements in the list. However, in addition to the elements, an array-based list also requires additional memory to store the underlying array structure." "Analyze the efficiency of queue operations when implemented using a linked list - CORRECT ANSWER With the use of a tail, the efficiency of both queue operations is constant time as the tail pointer is altered to point to a new element and the head pointer is altered to point to the second element; therefore, no traversal of the list is required. However, without a tail pointer, the efficiency of enqueue is linear time as the array must be traversed in order to find the last element and alter that pointer." "Give a software example for an application of the stack - CORRECT ANSWER Back and forward buttons in a web browser as more recent windows appear before older windows." "Give a software example for an application of the queue - CORRECT ANSWER Print tasks as a printer processes print requests in the order they were received." "Describe the morphology of a tree - CORRECT ANSWER Root: a node that has no nodes linking to it Branch: the link created between two nodes when one node references another Leaf: a node that has no outgoing branches Outer node: node that has no outgoing branches Inner node: node that has outgoing branches" "What is the meaning of distance in a tree? - CORRECT ANSWER The number of branches between two nodes" "Define the height of a tree - CORRECT ANSWER the number of branches to its most distant leaf node" "Describe the implementation of a binary tree for a map - CORRECT ANSWER Keys are stored in a way that allows for efficient searching, insertion, and deletion. Balances search trees maintain a balanced structure, ensuring that search operations have a logarithmic time complexity." "What is the efficiency of each map operation for a treemap? - CORRECT ANSWER Insertion: O(logn) on average, as balanced search trees maintain logarithmic height. O(n) in the worst case if the tree is unbalanced. Retrieval: O(logn) on average, as the search in a balanced tree has logarithmic time complexity Deletion: O(logn) on average, as the tree remains balanced. O(n) in the worst case if the tree is unbalanced" "What is the relationship between the number of levels and the number of elements in a balanced binary tree? - CORRECT ANSWER If a binary tree has n elements, the tree has log(n) levels as each node has two children stemming from the root. Therefore, a balanced binary tree has a search efficiency of O(logn) where n is the number of nodes because the data is repeatedly split in half after each comparison until the proper node is found." "What is the degenerate case for a tree map? - CORRECT ANSWER For a tree map, the degenerate case occurs when the tree becomes unbalanced, specifically when the tree takes on a linear structure and essentially becomes a linked list. The degenerate case arises when keys are inserted in a sorted or nearly sorted order since each new node is added to one side of the existing nodes, resulting in a linear structure. The efficiency of all operations in a degenerate case is O(n) where n is the number of nodes in a tree because the tree essentially becomes a linked list and lacks the previous O(log n) time complexity." "Define the structure of a hash table - CORRECT ANSWER A hash table is a data structure consisting of an array (or bucket array) and a hash function. The hash function maps keys to indices in the array, facilitating efficient storage and retrieval of key-value pairs." "What does the hashing function do in a hash table? - CORRECT ANSWER A hashing function maps keys to indices in the array, facilitating efficient storage and retrieval of key-value pairs. It returns a value of a specific type guaranteed to be within a specific range." "What does bias mean in terms of the hashing function? - CORRECT ANSWER Bias refers to a situation where the hash codes generated are not evenly distributed across the available indices in the hash table. If a hashing function is biased, the hash table may exhibit clustering, where keys are concentrated in specific regions rather than being uniformly distributed. A biased hashing function can compromise the key advantage of hash tables - constant time average case complexity for basic operations - and degrade their performance, making lookups, insertions, and deletions less efficient." "Define the depth of a tree - CORRECT ANSWER the number of edges back up to the root" "Define the term degree with respect to a node - CORRECT ANSWER the number of branches one node has to other nodes" "Define the term degree with respect to a tree - CORRECT ANSWER the maximum degree of any of its nodes" "What is the difference between an outgoing and an incoming branch? - CORRECT ANSWER Outgoing branches represent possible outcomes while incoming branches represent a previous decision. All nodes in a tree besides the root has one incoming branch and the maximum number of outgoing branches a node can have in a binary tree is two." "Define the relationships of nodes in a tree - CORRECT ANSWER Child: a node linked to by another node as an outgoing link Parent: the node that originates the link to that child Ancestor: any node that has children Descendant: any node that has a parent" "What can generally be said about the ancestral relationship between the root and all nodes in the tree? - CORRECT ANSWER The root is the ancestor of all nodes in the tree and all nodes are descendants of the root as it is the node that originates the link or links to all of its descendants." "What does balanced mean? - CORRECT ANSWER A tree in which the height of the left subtree and the right subtree of any node does not differ by more than one." "How many nodes are in a complete binary tree with depth d? - CORRECT ANSWER 2^d because each node has two children until the depth" "What is a degenerate tree? - CORRECT ANSWER Each parent node only has one child node; therefore, it is essentially a linked list as each node points to one element." "How does a tree become a degenerate tree? - CORRECT ANSWER It becomes degenerate if rebalancing is not performed when necessary to maintain it as a balanced tree. If the tree becomes extremely unbalances due to lack of consistent balancing, it will degenerate into performing no better than a linked list." "Justify why a balanced tree performs search in logarithmic time complexity - CORRECT ANSWER To find an element in a balanced binary tree, comparisons begin at the root and at each comparison, the remaining nodes to search is effectively eliminated by half." "Justify why a balanced tree performs insert in logarithmic time complexity - CORRECT ANSWER To find the proper location to insert a new element, the search operation is used which has a time complexity of O(logn). Apart from that, it is simply about altering pointers and rebalancing the tree if necessary." "Why do we ensure that a binary tree remains balanced throughout its usage? - CORRECT ANSWER If a binary tree is balanced, it makes search and insertion operations more efficient as it is O(logn) as opposed to O(n) where n is the size of the input in an unbalanced tree as it essentially operates like a linked list." "Define preorder traversal - CORRECT ANSWER Preorder visits the root first, then the left, then the right" "Define postorder traversal - CORRECT ANSWER Postorder visits the left first, then the right, then the root" "Define inorder traversal - CORRECT ANSWER Inorder visits the left first, then the root, then the right" "Which form of search is preorder traversal (depth first or breadth first) - CORRECT ANSWER Depth first because it visits all roots of each subtree until the bottom of the tree until it has reached a leaf node" "Which form of search is inorder traversal (depth first or breadth first) - CORRECT ANSWER Depth first because it visits the leftmost node which explores the bottom node before moving up the tree" "Which form of search is postorder traversal (depth first or breadth first) - CORRECT ANSWER Depth first because it visits the leftmost node first which explores the bottommost node before visiting the right node and the root of each subtree" "Which form of search is level order traversal (depth first or breadth first) - CORRECT ANSWER Breadth first because it explores an entire level of the tree before moving to the next level" "What is meant by depth first search (DFS) as opposed to breadth first search (BFS)? - CORRECT ANSWER DFS emphasizes moving down the tree first or exploring the depth of the tree while BFS emphasizes exploring an entire level before exploring any of the descendants of that level." "What is a map? - CORRECT ANSWER mapping elements from one domain to another" "What is a key-value pair? - CORRECT ANSWER the link between two domains (x domain = key, y domain = value)" "What are the requirements for each domain? - CORRECT ANSWER Each x domain (key) must be unique; however, the y domain can have multiple instances of the same value." "What is the uniqueness constraint of a map? - CORRECT ANSWER A key can never be repeated or duplicated in a map" "What is the vertical line test? - CORRECT ANSWER The vertical line test involves moving a straight, vertical line along a graph of a function and seeing if the line is intersected by the graph more than once at a point. This demonstrates how each value in the x domain or the x axis is linked with only one value in the y domain or the y axis." "What is the interface for a map? - CORRECT ANSWER put(key, value) - if the key exists in the map, put updates that key with the associated value; otherwise, put inserts the key-value pair into the map get(key) - if the exists in the map, get retrieves the associated value; otherwise, get returns a signifier that the key does not exist delete(key) - if the key exists in the map, delete removes the key and returns the associated value; otherwise, returns a signifies that the key does not exist" "Why must keys be unique? - CORRECT ANSWER It allows us to identify certain terms without having any duplicate values" "Why does the uniqueness of keys imply all map operations are search? - CORRECT ANSWER Each operation involves searching the map to validate that the key exists or does not exist to perform certain operations." "Describe the implementation of an associative array for a map - CORRECT ANSWER an associative array stores key-value pairs and retrieves given key-value pairs by iterating through the array and returning the value when the key is found" "What is the efficiency of each map operation in an array implementation? - CORRECT ANSWER Insertion: O(1) on average, but can be O(n) in the worst case if resizing is required Retrieval: O(n) in the worst case as it requires a linear search for the key through the array Deletion: O(n) in the worst case as it requires finding the key and removing the associated pair" "What would be the efficiency of inserting into an ordered array versus the efficiency of sorting? - CORRECT ANSWER Inserting into an ordered array can be more efficient than sorting the array after each insertion. The time complexity of inserting an element into a sorted array is O(n) where n is the size of the input in the worst case (as it may require shifting elements to make room for the new one), but in practice, it can be faster than sorting the entire array. The efficiency of periodically sorting an array would cause the efficiency of insertion to be O(nlogn)" "Why is the number of buckets an independent variable with respect to the number of elements? - CORRECT ANSWER The number of buckets is typically determined by the developer when creating the hash table based on the expected performance, however, the number of buckets can be adjusted during resizing. The number of elements is determined by the actual data being processed, and the hash table is designed to accommodate varying sizes of input data." "What is the relationship between the number of buckets and the number of elements? - CORRECT ANSWER The relationship between the number of buckets and the number of elements in a hash table is represented by the ratio of the number of elements in the hash table (n) to the number of buckets (m). n/m" "Why do we express the relationship between the number of buckets m and the number of elements n as n/m in our analysis? - CORRECT ANSWER Using a ratio helps us understand the proportion of elements to the number of buckets. It gives us an indication of how "loaded" the hash table is with elements. We put m in the denominator because it is never 0 (there is at least 1 bucket and if we eliminate it through our analysis, any function involving the numerator n looks like any other big O notation)." "Why do we condition our arguments with multiple cases in the hash table? - CORRECT ANSWER We condition our arguments with multiple cases because it guides us to make informed decisions about the design, resizing strategies, and overall performance considerations based on the characteristics of the data being handled such as n being significantly larger than m or vice versa." "Analyze an unbiased hash function, when n is significantly larger than m - CORRECT ANSWER The hash table resembles a linked list because, with a large n and a relatively small m, the elements are likely to hash to the same index, leading to a long chain of linked nodes. This causes the efficiency of all map operations to become O(n) where n is the size of the input because you may need to traverse the entire linked list to find a specific element. (n >>> m, lim n/m -> n = O(n))" "Analyze an unbiased hash function, when n is less than or approximately equal to m - CORRECT ANSWER The average time complexity is approximately O(1) or constant time. This is because elements are distributed more evenly which leads to a lower likelihood of collisions and results in efficient performance of map operations. (n = m, n/m -> 1 = O(1))" "What is the degenerate case for a hash table? - CORRECT ANSWER The degenerate case occurs when many keys hash to the same index, creating long chains of elements in the buckets. This can occur when the hash-function is not well-designed, resulting in biased or clustered hash codes. This causes the time complexity for map operations to become O(n) where n is the number of elements. The hash table practically degenerates into a linked list because all or most keys hash to the same index causing it to become congested" "Describe the implementation of a hash table for a map - CORRECT ANSWER A hashmap is typically implemented using an array of buckets, where each bucket contains a linked list. Keys are hashed using a hash function to determine the index in the array, and values are stored in the corresponding buckets, allowing for efficient retrieval and storage of key-value pairs." "What is the efficiency of each map operation for the hashmap? - CORRECT ANSWER Insertion: O(1) average case, assuming a well-distributed set of keys and a good hash function. O(n) worst case , degenerate case Retrieval: O(1) average case, assuming a well-designed hashmap. O(n) worst case, degenerate case Deletion: O(1) average case, assuming a well-distributed set of keys. O(n) worst case, degenerate case" "What are the optimal conditions of a hashmap? - CORRECT ANSWER If the hash table is deterministic (given a particular input, the same output will always be produced) and unbiased (all available values have the same probability of being chosen) to perform uniform distribution." "Under what circumstances would the binary tree be the better solution for a map implementation? - CORRECT ANSWER A binary tree may be a better solution for a map implementation when maintaining ordered data is a priority, as binary trees inherently organize elements in a sorted order. They are most suitable for scenarios where predictable and efficient performance across various operations is crucial. It may also be optimal for an arbitrarily large number of elements as the programmer cannot predetermine an arbitrarily large number of buckets." "Why is the associative array the worst choice among the three potential map implementations discussed? - CORRECT ANSWER The associative array has the worst case performance because it relies on linear structure for key retrieval and the efficiency for all map operations in O(n). In contrast, both the TreeMap and HashMap typically offer more favorable average-case and worst-case time complexities, making them generally superior choices for efficient map implementations." ""What is a recursive case? - CORRECT ANSWER The general solution to a subproblem." "How do we structure recursive implementations with regard to recursive cases? - CORRECT ANSWER We put the base case before the recursive case so the method does not create an endless recursion." "How do we control recursion? - CORRECT ANSWER Modifying the parameters, typically by reducing them." "Why do we try to model base cases at or around zero or null cases? - CORRECT ANSWER Because counting up requires an extra parameter which takes up more space when called and it is more likely that you will miss the base case which can lead to uncontrolled recursion." "Why is the stack so important in recursive algorithms? - CORRECT ANSWER A stack retains history in reverse order which handles backtracking." "What happens if recursion is uncontrolled? - CORRECT ANSWER it can lead to a stack overflow because every function call requires allocation of space and memory is taken up by every function call which can be detrimental as there is a finite amount of memory in a computer." "Why is there a finite number of recursive calls that can be made and why? - CORRECT ANSWER Because there is a finite amount of memory in a computer, meaning that no more recursive calls can be made after all the memory has been used up." "What is the relationship between the number of variables (and parameters) in a recursive function and the upper limit on the number of recursive calls? - CORRECT ANSWER The more variables and parameters used in a recursive function, the more memory is taken up, and, therefore, the greater the risk of overflowing the stack." "Define permutations - CORRECT ANSWER A permutation is a mathematical technique that determines the number of possible arrangements in a set when the order of the arrangements matters." "Give an example of a permutation - CORRECT ANSWER A string "ABC" -> [ABC, ACB, BAC, BCA, CAB, CBA] = 6 permutations" "What is the "Manhattan Distance"? - CORRECT ANSWER A measure of how far it is to travel from one location to another when confined to a grid." "Define the Manhattan problem - CORRECT ANSWER The goal is to determine how many shortest paths there are from the start location to the end location." "What are the constraints of the Manhattan Problem? - CORRECT ANSWER -cannot go backwards -cannot move back up or left -can only move down or right" "Illustrate the base cases for the Manhattan Problem - CORRECT ANSWER -one movement right to the end point -one movement down to the end point" "Illustrate the recursive case for the Manhattan Problem - CORRECT ANSWER choice to either move right or down" "Write the pseudocode for the Manhattan Problem - CORRECT ANSWER manhattan(row, col) if(row==0) return 1; if(col==0) return 1; count = manhattan(row-1, col) count = manhattan(row, col-1) return count;" "Estimate the growth of the problem with respect to the number of operations for the Manhattan Problem from the pseudocode - CORRECT ANSWER The growth of the problem is approximately O(2^n) where n is the size of the input because there are two recursive calls for each call to manhattan." "What does it mean to backtrack? - CORRECT ANSWER to return to a prior decision" "Why is recursion a natural approach for backtracking problems? - CORRECT ANSWER because the stack stores prior information in reverse order so you can refer back to the stack to fulfill a problem from the previous decision" "Why might an iterative approach be difficult to implement for a backtracking problem? - CORRECT ANSWER Because iterative approaches do not store past information." "What is an exploration problem? - CORRECT ANSWER the algorithm searches for new solutions in new regions" "Why are exploration problems good candidates for backtracking problems? - CORRECT ANSWER because new solutions are explored after a path fails to reach a solution" "Describe the Maze problem - CORRECT ANSWER attempting to find a solution to escape a maze"