Types of questions:

Write some questions in the form,

• "given this data, which data type to use"
• "if an algorithm produced this from this, which algorithm was used / how could you figure out which was used"

Questions with Proposed Answers

Q: Compare and contrast a heap and and array.

A: A heap can be implemented using an array. An array is a contiguous block of data, indexed from 0. An array can be ordered, unordered etc, depending on its use. Each element in the array must be of the same data type. Arrays can be used to store data with a range of purposes.

A heap on the other hand, whether implemented in an array (draw a picture here) or as a linked data type, must follow the "heap property" (that each element must be greater priority (for a max heap) than either of its children) and the "completeness property" (that when displayed as a tree, is filled row by row, left to right without skipping any spots). A heap is used to store data where we want to access/remove items with the highest (for max heap) priority first (or more often) than the items with lower priority.

Q: Can we implement a heap by linked list or bst?

A: Yes. In class, we looked at visual representations of implementing it as a tree. While you technically can implement it in a linked list or tree, unless you have another reason to do so, it is unadvised as implementing it as an array has the following advantages:

1. Quick movement up and down the tree (parent = n/2 and child = 2n and 2n+1). (Linked list would take too long)
2. Finding "the next empty spot to put a new element so that we maintain the completeness of the tree" is significantly harder in a tree than in an array. (Tree would take too long.)

Q: cycle checking in graphs - is Kruskal's practical?

A: In order to implement Kruskal's, you need to either, check for cycles after adding each edge (and remove it if there is a cycle) or check if there exists a path between two nodes before putting in an edge. So you need cycle checking (or similar) in order to implement Kruskal's.

Q: but isn't cycle checking slow/expensive compared to Prims

A: Options:

• Do the "does a path already exist" by maintaining the matrix produced by Warshall's algorithm for our MST graph as it's being built (and update it everytime we add an edge).
• Using this data structure and algorithm, we can more efficiently keep track of which verticies are currently connected to each other: https://cmps-people.ok.ubc.ca/ylucet/DS/Kruskal.html

Q: For situations such as if we're checking if a path exists a lot as justification for Warshall's, how do we know breakpoints? (or is it just by feel)

– Please elaborate. Warshall's is pretty amazing if we don't have many changes to the graph, and just want to see if you can get from A to B. (Eg roads in a city - new roads are rare, and for just one change, iirc isn't too costly to update). Or are you asking about situations where there are lots of changes, with rare questions about paths?
I'm asking like at a baseline Warshall's isn't good (if you never actually check whether there's a path), but the more times you check whether there's a path the better it becomes compared to alternatives. So should we have a feel of at what point an algorithm can become better than another.
A: Yes, you'd have some idea based on the data. In my limited experience it's usually quite clear whether you're doing mostly updating with very little asking about paths, or more asking about paths. (If asking about paths is a core, often repeated, part of the process.)

Q: Why doesn't Dijkstra's work with negative edge weights –- any way to fix this, or out of scope for 2521

A: Out of scope for 2521. For your own interest and learning, you can see the end of the slides about Dijkstra's algorithm for a list of similar algorithms, some of which handle negative weights.

Q: Not theory but how should we implement the bucket in radix sort?

A: Array of arrays, or array of linked lists.

Q: Is there a good way to turn a sorted list into a BST? like a reverse in-order traversal

A: Off the top of my head, if you know your list is sorted (or near sorted) reference elements in the same order they'd be checked in a binary search and insert them into your tree in that order. This would give you the most balanced tree possible without requiring re-balancing.

Q: Is there a decent way to check if two graphs are isomorphic 🧌 lmao yeah and even harder figuring out the isomorphism itself

Proving is trivial - provide the function between g1 edges to g2 edges (1081 jumpscare (literally a prerequisite))

Q: When is a double pointer used in coding? Like why do we use a double pointer for a predecessor array?

Q: what is the optimal wordle solving data structure (very hard)

I was thinking start with a trie, but you'd also want to sacrifice using some letters you know in exchange for more letters. yeah ai

Trie - lacks power because knowing "the third letter is r", means a lot of work within your trie.
Data analysis on which words contain the most common letters.
Maybe some data analysis on which letters are most commonly found in which elements (position) of the word.

Q: What is the final question of the exam (impossible)

A: 1 + 1 = ? (Solve in at most O(n^2) time)

Fib algorithm in O(1) time (hint precompute all the values) isn't there a formula and you just round
nah pow is O(log n)

int fib(int i) {
return [0, 1, 1, …][i]; // only 30 or so <= MAX_INT
// return infinity if out of range
}

i reckon we do this
(O(n^2))