Worded explanations on algorithms

Question 1

BFS

explain

Answer 1

• The BFS algorithm uses a queue ADT such that it stores the unvisited nodes in the queue ADT
• After each node has been visited, it marked the node as visited and enqueues all adjacent unvisited nodes in the queue

Question 2

Dijkstra’s

explain

Answer 2

• Dijkstra’s algorithm starts by initializing the distance of all nodes as infinity and the starting node as 0
• it iteratively picks the unvisited node with the lowest distance whilst updating the distances
• After visiting a node, it marks that node as visited then repeats until all nodes are visited or the target node is found

Question 3

Bellman-Ford

explain

Answer 3

• The bellman ford algorithm loops through all edges |V|-1 times in any order whilst updating the distances of each node in each iteration such that it is trying to minimize the distance
• Then it loops through all edges one more time, if a change has been made there exists a negative cycle, which then updates all effected edges as -infinity

Question 4

Floyd-Warshall’s transitive closure algorithm

explain

Answer 4

• Floyd-Warshall’s algorithm** initializing an adjacency matrix**
• Then through a triple nested for loop, it updates i through j whilst considering k, an intermediate node
• It repeats until it tries all the combinations of i,j and k

Question 5

Prim’s

explain

Answer 5

• Prim’s algorithm starts by considering all edges from a node while marking the starting node as visited
• Prim’s will then pick the edge with the lowest edge that leads to an unvisited node
• After it goes to an unvisited node, it marks it as visited then repeats until all nodes are visited

Question 6

Merge Sort

explain

Answer 6

• Mergesort divides the array into each sub array where len(sub array) is 1
• It then merges each subarray together whilst sorting each subarray
• It recursively does this until the array is back together

Question 7

Quick Sort

explain

Answer 7

• Quick sort has a pivot that splits the array into two parts, one for elements smaller than or equal to the pivot and one for the other.
• It then splits those sub array in a similar manor until reaching single size sub array then merges those back together.

Question 8

Binary search

explain

Answer 8

• The binary search algorithm divides the array in half and keeps the half that includes the target number
• It repeats until the target value is found

Question 9

Greedy graph coloring

explain

Answer 9

• The algorithm starts by colouring a node the lowest colour
• For each uncoloured neighbouring node, it colours the node the lowest colour such that the node adjacent to it is not the same colour
• It repeats this until all nodes are coloured and returns how many colours are used

Question 10

Change making brute force

explain

Answer 10

• The algorithm could first generate all the combinations as an array of the list of coins as an array
• Then by looping through sub arrays in the array, it gets the sub array with the smallest amount of coins in the array
• It then will return the lengh of that particular sub array

Question 11

Change making greedy

explain

Answer 11

• The algorithm could first sort the array in ascending order
• continusly adds the highest value until it exceeds the max number of coins
• Then it goes to the element below, repeating until it can does not exceed the max number of coins
• If it reaches the last element, the algorithm stops and returns how many coins were used

Question 12

Knapsack brute force

Answer 12

• The algorithm could first generate all the combinations of each item
• Then, it can remove all the solutions that are exceeding the weight
• Through this, it can pick the items with the highest value

Question 13

Knapsack heuristic

Answer 13

• The knapsack can generate a ratio between the value and the weight
• Then, it will continually add the highest ratio until it does not exceed the weight

Question 14

TSP Brute force

Answer 14

• The TSP brute force can get every combination all the possible solutions
• It then picks the solution with the lowest distance

Question 15

TSP heuristic (nearest neighbor)

Answer 15

• An algorithm can always pick the smallest unvisited node starting from the starting node
• Repeats until all nodes are visited, then connect the final node to the target node

Question 16

TSP randomized heuristic

Answer 16

• A random solution can first be generated
• then k-opt or some similar method can be used to swap edges
• Simulated annealing can then be used to determine if a candidate can be accepted or not through a probability based on the temperature.

Question 17

TSP backtracking

Answer 17

• By considering each decision as a decision node in a decision tree, backtracking can be used to solve the TSP
• An algorithm can c**ontinue down a path using a stack ADT **until it reaches a leaf node
• If the Leaf node is not a valid solution or the solution is worse than the pervious solution, it backtracks to the previous node
  Repeats until all nodes are visited or until a set number of iterations are achieved.

Question 18

quick sort worse case recurence relation

Answer 18

T(n)=T(n−1)+O(n)

Question 19

merge sort recurence relation

Answer 19

T(n)=2T(n/2)+O(n)

Question 20

quick sort recurence relation average case

Answer 20

T(n)=2T(n/2)+O(n)

Question 21

A*

explain

Answer 21

• A* algorithm works like Dijkstra’s such that the distance is the heuristic distance + actual distance
• By starting to initializing the distance of all nodes as infinity and the starting node as 0, the A* algorithm picks continously picks the edge with the shortest edge that leads to a node that has not been visited whilst considering the updated distance
• After visiting a node, it marks that node as visited and update the distance then repeats until all nodes are visited or the starting node is found