Vocabulary
Set of instructions designed to solve a problem
What is an algorithm?
Shrimpcat wants a simple container to be able to store more than one item
What is an array? (Vector, map, set, and similar are also acceptable)
Turtlecat has an unsorted set of numbers. He wants to check if it contains the number 34. (Don't over-complicate this)
What is complete search?
Term used for a negative or positive whole number. (Note: by definition, whole numbers cannot be positive. This is describing the negated version)
What is an integer? (long or similar also accepted)
Shrimpcat wants to store pairs of {string, integer}
What is a map?
Turtlecat has several contests he wants to participate in and wants to schedule them during his day. Each contest has a start end end time. Turtlecat wants to know how to arrange these contests to be able to participate in as many as possible
What is interval scheduling? (Sort by end)
A sequence derived of another from the deletion of 0 or more elements without rearrangement of order
What is a subsequence?
Shrimpcat wants to easily add undirected edges to a graph and determine which nodes are connected to which
Disjoint set data structure
Turtlecat wants to go to the store. His town is a directed graph with unweighted edges. Help him find the shortest path to the store
What is BFS?
Node of a tree with no children
What is a leaf?
Shrimpcat wants to find the minimal subset of edges with the minimal sum of weights in an undirected connected graph that allow it to remain connected even if these are the only edges in the graph.
What is Kruskal's (or Prim's) algorithm?
Turtlecat works in a turtle shell shop. He sells a turtle shell to Corncat and must give him his change. Turtlecat likes his coins so he wants to use as few as possible.
What is the coin change problem?
Two ways of performing DP. Include details
What are top-down/memoization and bottom up/tabulation DP techniques?
Shrimpcat wants to be able to be able to iterate through all subsets of a set
What is bitmask brute force?
Turtlecat wants to go to the store. His town is a directed graph with weighted edges. Help him find the shortest path to the store
Why wasn't it a Dijkstra?