Graphs
What is an ADT and what is a graph?
Abstract data type = a data structure that describes behavior (but NOT implementation) from the POV of the user
Graph = Vertices and edges as any number of connected components
What is a greedy algorithm?
Any algorithm that makes decisions based only on local optimums
What is the format for a lambda expression?
(parameters) -> { method body }
What is a stream?
Sequence of elements/information able to be manipulated
add(E value), contains (E value), size, connectUndirectedE a, E b), connectDirected(E a, E b), connected(E a, E b)
Is the nearest neighbor algorithm more similar to DFS or BFS? (And why?)
DFS (heads deeper into the graph each time a new vertex is chosen)
What are some differences between inner and anonymous classes?
State within the anonymous class is usually not accessible from outside
Anonymous classes aren't named
An instance of the inner class must be created using an instance of the outer class
Name three methods you can perform on streams
Stream.forEach, Stream.filter(predicate), Stream.sum(), Stream.collect(), etc
What is an adjacency list?
A map of vertices & their list of neighbors; used to represent an adjacency graph
What data structures does Dijkstra's algorithm use?
Map of vertices & their path tuples, and a priority queue for the path tuples
What changes for an inner class if it is declared as static?
It cannot directly access the outer class’ state and behavior, but it can be created without an instance of the outer class
What is Jennie's most frequent closer activity for these SI sessions?
NYT Connections
What is the difference between BFS and DFS?
BFS investigates all surrounding nodes before moving on, DFS utilizes recursion and continues deeper one node at a time
What happens when a backtracking algorithm finds an invalid configuration?
It automatically prunes its search tree of all its successors
How is a method reference structured?
class/variable name :: method name
What data structures do DFS and BFS use?
DFS: Stack (recursively implemented) and a set of already visited
BFS: Queue and a hashmap of already visited
List out all the steps to BFS
As long as queue is not empty and options are not in already-visited set:
dequeue next vertex and if its not the end then add each of its neighbors to the queue next
keep checking till path found or queue empty
If Jennie has 20 pieces of candy, ranging from size 1 to size 3, and there are 10 students who all want a certain amount of candy, write the steps to a greedy algorithm that tries to maximize even candy distribution
:>
Give any example of a situation where you might have to use a lambda and method reference in the same line
names.stream().map(name -> name.toUpperCase()).forEach(System.out::println);
What scope do lambdas have?
Same as anonymous classes: Have access to all variables in containing class, including variables local to method they were created in