comp 215 test #3

Define callee

The function (method) being called.

Define caller

The function (method) that calls the callee.

Define a frame (stack frame)

an entry on the call stack representing a single method call that is in progress; holds call's parameters, local variables, and where to resume in the caller when it returns

Define the call stack

A data structure that stores the state of all the function calls that are in progress at a given moment in time. It is composed of frames.

In what order are frames added to and removed from the call stack?

LIFO

What is a call tree, and how is it different from the call stack?

A call tree shows the complete history of all function calls. call stack only shows the calls in progress at one moment, (a single path)

What are the steps (7) that happen behind the scenes when a function is called?

1) The caller's context (its variables and the call site) is saved. 2) The callee's parameter values are initialized. 3) Control flow transfers to the callee. 4) The callee's body executes. 5) The caller's context is restored. 6) The callee's return value is assigned in the caller. 7) Control flow transfers back to the caller.

main calls a(), a calls b(), and b is currently running. What is on the call stack, from top to bottom?

b, a, main. main is at the bottom because it was called first, and b is on top because it is currently running.

What happens to a method's local variables when the method returns?

Its frame is popped off the call stack, so those local variables no longer exist. A later call to the same method gets a brand new frame with fresh variables.

In Java, where do local variables live, and where do objects live?

Local variables and parameters (including object references) live in the method's stack frame. Objects created with new live on the heap. When a frame is popped, its references disappear, but an object survives if something else still refers to it.

True or false: when a method calls itself, all of the calls share the same local variables.

False. Each recursive call gets its own frame with its own copies of the parameters and local variables.

True or false: any iterative function can be written recursively.

True

what is the syntax used for Comparable comparisons vs Comparator comparisons?

this.compareTo(o); comparator.compare(o1, o2)

When is memoization not helpful?

When the subproblems don't overlap

What is the difference between the size and the capacity of an array-backed list?

Size is the number of elements actually in the list. Capacity is the length of the underlying array, meaning how many elements fit before the list has to resize.

What happens when an array-backed list runs out of space?

It allocates a brand new, larger array (1.5x size) and copies all of the elements from the old array into it, which takes O(n) time.

Why would expanding an array-backed list by a very large amount be a bad design?

waste of space

What is the complexity of appending to an array-backed list, and why?

O(1) amortized. There is usually a preallocated empty slot at the end, but occasionally the list must resize and copy the whole array in O(n).

What is the complexity of prepending to an array-backed list, and why?

O(n). Every existing element must shift one position to the right to free up index 0.

What is the complexity of inserting at an arbitrary position in an array-backed list, and why?

O(n). bc shifting

What is the complexity of removing by reference ("remove this object") from an array-backed list, and why?

O(n). The list first has to linearly search for the object, and then shift the elements after it to the left to close the gap.

What is the complexity of removing by idx from an array-backed list, and why?

O(n). The lookup is O(1), but shifting the elements to the left is O(n), since on average about n/2 elements after index i must be shifted

What is the complexity of removing the last element of an array-backed list, and why?

O(1) bc no shift

If list is an ArrayList containing [3, 2, 1], what does list.remove(1) do?

list.remove(1) defaults to removing by position, so the result is [3, 1]. To remove the value 1, use list.remove(Integer.valueOf(1)), leaving [3, 2].

T/F: An ArrayList can store primitive and reference types

False, ArrayList can only store objects (no primitive types)

What’s the default capacity of an ArrayList

10 (unless you explicitly pass a capacity to the constructor)

What is the time complexity of appending to a singly-linked list with/without a tail pointer, and why?

with: O(1) bc the tail pointer gives direct access to the last node

without: O(n) bc you have to start at the head and travers every node to find the last one

What is the time complexity of prepending to a linked list, and why?

O(1). The head pointer gives direct access to the first node, so the new node just points to the old head and becomes the new head

What is the time complexity of inserting at an arbitrary position in a linked list, and why?

O(n). You have to scan from the head to find the node that comes right before the insertion point. The linking itself is O(1), but the scan is O(n).

What is the time complexity of removing by position ("remove the object at index i") from a linked list (doubly-linked vs singly-linked), and why?

O(n) for both. You have to scan the list to find the node at position i (and the node before it) before you can unlink it.

What is the time complexity of removing by reference to a node ("remove this node") from a singly-linked list? doubly linked list?

O(n), unless the node is the head. Each node in a singly-linked list only stores a reference to the next node, so you have to scan from the head to find the node before it in order to unlink it.

O(1). Each node stores a reference to its previous node, so you can unlink it directly without scanning the list.

What is the space tradeoff between singly-linked and doubly-linked lists?

A doubly-linked list uses more memory, since every node stores an extra prev reference. but, it allows for O(1) removal by node reference

How can a linked list be optimized for looking up elements in order (index 0, then 1, then 2...), and what complexity does that give?

Add a field that remembers the most recently looked-up node and its index, and start the next scan from there instead of the head. If elements are accessed in order, each next lookup is O(1).

What is the space efficiency tradeoff between array-backed lists and linked lists?

Array-backed lists may waste space on empty, preallocated slots in the underlying array. Linked lists have no empty slots, but every element carries extra overhead for its node object and its next (and prev, for doubly-linked lists) references.

What is the time complexity for the lookup operations in an array-backed list vs a linked list? Why?

O(1) for an array-backed list and O(n) for a linked list

an array-backed list computes the position directly from the index (math); a linked list has to scan from the head.

When would a linked list be preferred over an array-backed list?

When you frequently add or remove at the front of the list (like a queue), when you remove nodes you already hold references to (doubly-linked), or when you want to avoid wasted capacity

When would an array-backed list be preferred over a linked list?

When you frequently look up elements by index, since that's O(1) instead of O(n), or when memory overhead per element matters, since there are no node objects or next/prev references.

Which abstract data types can a linked list be used to implement?

List, Queue, and Stack. With a head and tail pointer, adding at one end and removing from the other end are both O(1) (for removing from the tail, you need a doubly-linked list).

What property must hold for a graph to be considered a tree?

It must be acyclic (contain no cycles).

What is the time complexity of an in-order, pre-order, or post-order traversal of a binary tree, and why?

O(n). Every node is visited exactly once, no matter which order the traversal uses.

Why does the height of a binary tree matter for the complexity of its operations?

Operations like insert, remove, and contains in BSTs, heaps, and treaps all have O(height). A balanced tree has height O(log n); a completely unbalanced one has height O(n).

What is the best-case time complexity of insert, remove, and contains in a binary search tree, and why?

O(height) = O(log n). best case is when tree is balanced, so height = log n

What is the worst-case time complexity of insert, remove, and contains in a binary search tree, and why?

O(n). If the tree is skewed (elements inserted in ascending order, for example), it effectively becomes a linked list, so its O(height) = O(n)

Which abstract data types can a binary search tree be used to implement, and why?

Sets and Maps bc neither needs to preserve insetion order

How does a BST compare to an list for checking whether an element is in the collection?

A balanced BST does contains in O(log n), because each comparison eliminates about half the remaining tree. An unsorted list has to linearly check elements one by one, which is O(n).

What benefit does a BST have over a hash-based Set or Map?

BST keeps elements in strict order all the time

difference between BST with total preorder and with total order

Total order doesn’t allow duplicates

What two constraints does a binary heap add to a binary tree?

1) The shape constraint: every level is full except possibly the bottom level, and the bottom level's nodes are as far left as possible.

2) The partial ordering constraint (the heap property): for a max-heap, parent is always greater than children; for a min-heap, parent is always less than children

What is the difference between a min-heap and a max-heap?

min-heap: parent is less than or equal to its children

max-heap: parent is greater than or equal to its children

What is the time complexity of inserting and removing into a binary heap, and why?

O(log n). The swaps only happen along one branch from the bottom up toward the root (o reverse for remove), and because heaps are guaranteed to be balanced, its height is always O(log n).

What is the time complexity of contains or removing an arbitrary element from a binary heap, and why?

O(n). The heap is only partially ordered (children > or < than parent) so you can't eliminate half the tree at each step. You have to search linearly.

Which abstract data type is a binary heap a good implementation of, and why?

A priority queue, where the highest-priority element is removed next. Removing and insertion is O(log n)

What is a space advantage of storing a binary heap in an array?

Because the heap is always complete, it fits in an array with no gaps. also no need for node objects or child references. can find a node's children and parent by index arithmetic (parentIdx = childIdx / 2, where the first element in the array is null)

Which constraints does a treap enforce on its keys and its priorities?

Keys → BST constraint (left<node<right)

Priorities —> heap constraint (max-heap: parent priority >= children

What is the purpose of assigning random priorities to treap nodes, from a complexity standpoint?

Random priorities make the tree's shape the same as if the keys had been inserted into a normal BST in random order. That makes the tree very likely to be balanced (P(worst case) = 2^(n-1)/n!), so all operations are expected O(log n), even if the keys are inserted in sorted order.

What is the space tradeoff of a treap compared to a plain BST?

Each node stores an extra priority value, so a treap uses a little more memory per node in exchange for being balanced with high probability.

Which abstract data types can a treap be used to implement?

Sets and Maps

What assumption is needed for trie operations to be considered O(1) with respect to the number of elements?

we assume that the length of the strings (m) is bounded by a constant, and the character set is fixed (26 lowercase letters), so moving from a node to the right child takes constant time, so O(m) must also be constant.

What is the time complexity of insert, contains, contains prefix, lookup, and remove on a trie, and why?

O(m), where m is the length of the input string, because each operation visits one node per character. It doesn't depend on the number of elements in the trie, so it's O(1) with respect to n (assuming string length is bounded and the alphabet is fixed).

Which abstract data types can a trie be used to implement?

Sets or Maps (with string keys/elements), since neither needs to preserve insertion order

What is the major disadvantage of using a trie?

Poor space efficiency. Every character gets its own node, so long chains of nodes with no branches use a lot of memory.

How do compressed tries address the space disadvantage of tries?

They combine chains of nodes with only one child into a single node with multiple characters, reducing the total number of nodes.

What does Comparable's compareTo() allow you to do?

It allows internal comparisons, where the class itself defines this ordering.

When is it a better design to use the Comparable interface?

When you want to define a single default order defined for your own class, or use the order that alrdy exists

When is it a better design to use the Comparator interface?

if you need to define multiple custom orders for the same objects or you don't like the default order for that class

What are the return values for when this/o1 is less than, equal to, or greater than o/o2

< 0
= 0
> 0

How many parameters does compareTo() take vs compare(), and why?

compareTo(T o) takes one parameter because it’s called on this
compare(T o1, T o2) takes two because the Comparator is a separate object comparing two others.

Say you want to sort a list of Student objects by GPA sometimes and by last name other times. Should you use Comparable or Comparator?

Comparator, because you need multiple custom orders

Example: you want to sort Strings by length instead of alphabetically. Should you use Comparable or Comparator, and why?

Comparator. String is a class you didn't define, and its default (Comparable) order is alphabetical, which isn't the order you want.

Example: what does "apple".compareTo("banana") return?

A negative number; String's natural ordering is alphabetical and "apple" comes before "banana"

What is a collision in a hash table?

When two distinct keys map to the same hash code (and therefore the same slot in the table).

What three properties should a good hash function have, and why does each matter for complexity?

1) Deterministic: the same input always maps to the same hash code, or you could never find a key again.

2) Uniform distribution: keys are spread evenly across slots, even when inputs are similar, which keeps collisions (and chains) short.

3) Efficient: computing the hash is O(1), so it doesn't slow down every operation.

What is the time complexity of insert, remove, and lookup in a hash table, and why?

O(1) expected. Each operation computes a hash code, which is O(1), then scans one chain or probe sequence, which is O(1) if it stays a constant length.

What assumptions must be made for hash table operations to be O(1)?

That there's a good hash function and a sufficiently large table, so each chain (or probe sequence) only holds a small, constant number of elements.

What is the worst-case time complexity of hash table operations, and when does it happen?

O(n). If the hash function is bad or the table is too small, many keys collide into the same slot, so an operation may have to scan through nearly all n elements.

What is the load factor of a hash table?

n / k, where n is the number of key-value pairs stored and k is the number of slots in the table.

Why is it important to dynamically resize a hash table, and how does the load factor decide when to resize?

O(1) operations require a sufficiently large table. If the table is too small, chains grow and operations stop being O(1); if it's too large, space is wasted. So the table resizes when an insert makes the load factor n/k exceed a threshold t (0.75 by default in Java).

What is the complexity of resizing a hash table, and why doesn't it ruin insert's O(1) complexity?

Resizing is O(n), because every existing key has to be rehashed into the new, larger table (its slot depends on the table size). Because the table grows by a multiple, resizes are rare, so insert is still O(1) amortized, like appending to an array-backed list.

How does open hashing (separate chaining) handle collisions?

Each slot in the array holds a linked list (chain) of key-value pairs, so colliding keys are stored in the same slot's chain.

How does closed hashing (open addressing) handle collisions?

Every pair is stored directly in the array. If a key's slot is taken, a probing scheme scans other slots until it finds the key or an open slot.

What is lazy deletion in closed hashing, and what problem does it solve?

Instead of emptying a removed pair's slot, the pair is marked invalid and left in the array. Emptying it could break the probing scheme: a later lookup would stop at the empty slot and miss keys that were stored further along the probe sequence.

What are the advantages of open hashing (separate chaining)?

It's a simpler scheme, especially for removal (no lazy deletion needed), and it's less susceptible to bad clustering, since separate chains can't merge.

What are the advantages of closed hashing (open addressing)?

It's more space efficient (no node objects or next references), and it has locality advantages because pairs are stored contiguously in the array.

What are the two steps of computing a hash code in Java, and why is splitting them helpful for the programmer?

1) The key's hashCode() method produces an int. 2) A private function in the data structure converts that int into an index smaller than the table size. The programmer only writes hashCode() for their class and never has to think about the table's size; the data structure handles that internally.

In Java, if two objects are equal according to equals(), what must be true of their hashCode() values, and why?

They must return the same hash code. Otherwise, two equal keys could land in different slots, and a HashMap or HashSet would fail to find a key that's actually there.

Which abstract data types can a hash table be used to implement?

Sets and Maps, since neither needs to preserve insertion order

When would you choose a BST-based Map over a hash-based Map?

When you need the keys kept in sorted order (to iterate in order, or find the smallest or largest key), or when you need guaranteed O(log n) instead of O(1) expected with an O(n) worst case.