Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
60 Cards in this Set
 Front
 Back
For a persistent list, what is the time complexity of inserting something at the end of a list assuming we have a last pointer? 
O(n)  The last pointer does not matter, because we still have to copy the list. 

For a persistent list, what is the time complexity of inserting something at the end of a list? 
O(n) 

Suppose we have a list A and wish to create a new list B that is identical, except the first element will be changed. If use a persistent list, what will be the space complexity? 
O(1)  We need to create one cell to represent the changed element, but we can share the remaining elements with the original list. 

For a persistent list, what is the time complexity of deleting something from the beginning of a list? 
O(1) 

For a persistent list, what is the time complexity of deleting something from the end of a list, assuming we have a last pointer? 
O(n)  The last pointer does not help because we still need to copy the list. 

For a persistent list, what is the time complexity of deleting something from the end of a list? 
O(n) 






















Write a function in Clojure that will take a list and return the sum of all its elements. You may use the defrecord type we did in class, or Clojure's builtin lists. 


Suppose we have a list A and wish to create a new list B that is identical, except the first element will be changed. If we use a mutable list, what will be the space complexity? 
O(n)We need to create one cell to represent the changed element, but we also need to copy the original list. Otherwise, changes made to the original list will be visible in our copy. 

For a mutable list, what is the time complexity of inserting something at the beginning of a list? 
O(1) 

For a mutable list, what is the time complexity of inserting something at the end of a list, assuming we have a last pointer? 
O(1) 

For a mutable list, what is the time complexity of inserting something at the end of a list? 
O(n) 

For a mutable list, what is the time complexity of deleting something from the beginning of a list? 
O(n) 

For a mutable list, what is the time complexity of deleting something from the end of a list, assuming we have a last pointer? 
O(n)The last pointer does not help because we have to "back it up" one step, and going backwards in a singlylinked list is O(n). 

For a mutable list, what is the time complexity of deleting something from the end of a list? 
O(n) 




In a doublylinked list, what is the purpose of a sentinel? 
A sentinel takes the place of of null pointers, and allows the same code to handle both interior nodes and edge cases. This simplifies code. 

What is the advantage of doublylinked lists over singlylinked list? 
A doublylinked list allows the program to traverse the list backwards quickly. 

If you only have persistent data, but want to be able to traverse a list forwards and backwards quickly (like you can in a doublylinked list), what can you do about it? 
You can use a list zipper to handle this functionality. 































What advantage does tail recursion confer to the programmer? 
Tail recursion allows the compiler to reuse the stack frame of a function when it makes its recursive call. This transforms the recursive function internally into an efficient loop. 







What are the three stack operations? Give their time complexities. 
The three operations are push, pop, and top. They all take O(1) time. 

Explain briefly how to implement a stack using arrays (vectors). How are push and pop implemented? 
You need a vector for the stack, and an integer for the top of stack pointer. This pointer will point to the first available entry in the stack. 

Explain briefly how to implement a stack using lists. How are push and pop implemented? 
You can implement a stack with a list by inserting at the front to implement push and deleting from the front to implement pop. 
























































