DSA 3. Algorithms & Strategies
Brute-force - answer Algorithm strategy consisting of systematically enumerating and
testing every possible candidate solution.
Greedy - answer Algorithm strategy that finds the locally optimal solution at each step in
an attempt to find the globally optimal solution.
Divide-and-conquer - answer Algorithm strategy that divides the main problem into
smaller/similar subproblems, recursively solves them, and combines them into a main
solution.
Dynamic programming - answer Algorithm strategy that divides the main problem into
smaller/similar subproblems but also memoizes the solutions to overlapping
subproblems and applies stored solutions to subsequent repeat subproblems.
Linear search - answerFinds an element in a list by sequentially checking each item
until a match is found.
Binary search - answerFinds an element in a sorted list by dividing it in half and
comparing the target value with the middle value. If not equal, repeat recursively on the
left/right half, until a match or null is found.
Hash search - answerFinds an element in a collection by producing a unique index
based on the element key and retrieving the element at the produced index of the
collection.
Breadth-first search - answerFinds an element in a tree or graph by starting at a root
and exploring elements at the same level before moving to another depth level.
Depth-first search - answerFinds an element in a tree or graph by starting at a root and
exploring elements as far as possible along each branch before backtracking.
Kruskal's MST algorithm - answerA greedy algorithm for producing a minimum-spanning
tree from an undirected weighted graph by repeatedly picking the smallest weight edge
without creating a cycle until all vertices are connected.
Prim's MST algorithm - answerA greedy algorithm for producing a minimum-spanning
tree from an undirected weighted graph by picking an arbitrary vertex, then repeatedly
picking the subsequent smallest weight edge to the next unvisited vertex until all
vertices are connected.
Brute-force - answer Algorithm strategy consisting of systematically enumerating and
testing every possible candidate solution.
Greedy - answer Algorithm strategy that finds the locally optimal solution at each step in
an attempt to find the globally optimal solution.
Divide-and-conquer - answer Algorithm strategy that divides the main problem into
smaller/similar subproblems, recursively solves them, and combines them into a main
solution.
Dynamic programming - answer Algorithm strategy that divides the main problem into
smaller/similar subproblems but also memoizes the solutions to overlapping
subproblems and applies stored solutions to subsequent repeat subproblems.
Linear search - answerFinds an element in a list by sequentially checking each item
until a match is found.
Binary search - answerFinds an element in a sorted list by dividing it in half and
comparing the target value with the middle value. If not equal, repeat recursively on the
left/right half, until a match or null is found.
Hash search - answerFinds an element in a collection by producing a unique index
based on the element key and retrieving the element at the produced index of the
collection.
Breadth-first search - answerFinds an element in a tree or graph by starting at a root
and exploring elements at the same level before moving to another depth level.
Depth-first search - answerFinds an element in a tree or graph by starting at a root and
exploring elements as far as possible along each branch before backtracking.
Kruskal's MST algorithm - answerA greedy algorithm for producing a minimum-spanning
tree from an undirected weighted graph by repeatedly picking the smallest weight edge
without creating a cycle until all vertices are connected.
Prim's MST algorithm - answerA greedy algorithm for producing a minimum-spanning
tree from an undirected weighted graph by picking an arbitrary vertex, then repeatedly
picking the subsequent smallest weight edge to the next unvisited vertex until all
vertices are connected.
