Master list

Question 1

Describe the travelling salesman problem.

Answer 1

You’re givn a graph of n cities with weighted, undirected edges. What is the shortest Hamiltonian cycle in the graph?

A Hamiltonian cycle is a graph cycle which starts in one city, travels through each other city exactly once, then finishes at the starting city.

Question 2

What is the random construction method?

Answer 2

The random construction method is one where we generate a random permutation of all cities.

Question 3

What is the iterative random construction method? How many times do we run it?

Answer 3

The iterative random method is one where we run the random method several times, then choose the best result.

It’s usually run 5 times, according to Nourddine.

Question 4

What is the greedy construction method?

Answer 4

The greedy construction method is one where we start in a random city. At each step, we move to the next node with has the cheapest transition cost.

Question 5

What is the random insertion method?

Answer 5

During each step in the random insertion method, we select a random city. We then try putting this in-between each other city in our current tour, to find out where it would cause the lowest increase in tour length.

Question 6

What is the cheapest insertion method?

Answer 6

During each iteration:

1) Look at each unvisited city.
2) Try to insert it at any point in our current tour.
3) Select to keep the tour with the shortest length after doing this for all cities.

Question 7

Describe the greedy improvement heuristic.

Answer 7

The greedy improvement heuristic takes some tour and tries to improve it by swapping cities pairwise. If the swap lowers the overall tour length, it’s accepted, otherwise it’s rejected.

The heuristic is run until some stopping criteria are met, and is usually bounded by:

• Time
• Number of iterations
• Rate of improvement over some window

Question 8

Describe the transportation problem

Answer 8

It’s concerned with moving some commodity from a source to some destination.

We can model the problem as a list of factories (sources) with production rates, warehouses (destinations) with capacities and a weighted adjacency matrix between the two (transition costs).

Question 9

Describe the northwest corner method.

Answer 9

With the northwest corner method, we start in the northwest corner.

We try to maximize how much is transported from the current factory to the current warehouse.

Afterwards, we continue to do this for each square on a zig-zag pattern towards the southeast corner.

Question 10

Describe the least cost method. (Transportation)

Answer 10

In the least cost method, we look through the adjacency matrix to find the cheapest transition cost. We then want to transport as much as the factory/warehouse combination allows us.

Then we look through the adjacency matrix for the next cheapest factory/warehouse combination, and move as much as that allows.

We continue to do this while the factories and warehouses can deliver more.

Question 11

Describe the stepping stone algorithm.

Answer 11

We ask ourselves: if we assign one more unit to some empty factory/warehouse combination, will this decrease the total cost?

We try doing this by adding 1 unit to some f/w combination. This will unbalance the adjacent row and column. To balance these, we remove one unit from the row/column (Typically from the most expensive f/w combination). This will make both of those unbalanced, so we need to balance both of those until an equilibrium has been reached.

Question 12

Describe the knapsack problem.

Answer 12

Given an empty set with capacity W (the knapsack) and a set of items with value v and weight w. What items can we choose to maximize sum(v_i) subject to sum(w_i)

Question 13

Describe the four construction methods centered around sorting the elements. (Knapsack)

Answer 13

We can sort by weight ascending and descending, and by value ascending and descending.

We then select items while the weight limit of the knapsack hasn’t been reached yet.

Question 14

Describe how the greedy improvement heuristic can be used to improve this solution. (Knapsack)

Answer 14

We can iteratively choose to swap two item from outside/inside the knapsack and calculate the resulting cost. If it’s better, keep the swap. If it’s worse, reject the swap. Repeat until some stopping criteria has been reached.

Question 15

Describe the kick method.

Answer 15

S1: Some initial solution.
S2: Optimize S1.
S3: Some randomization of S2 (Eg. k random swaps).
S4: Optimize S3.
Compare S2 and S4, keep the best.

Question 16

Beskriv GreedyRandom.

Answer 16

GreedyRandom er en grådig optimeringsalgoritme som ligner på greedy heuristic.

Forskjellen er at man har en tilfeldig sjanse for å beholde nye løsninger man finner. Denne sjansen starter stor, og synker sakte gjennom hver deliterasjon av algoritmen.

Question 17

Vis GreedyRandom i pseudokode.

Answer 17

http://imgur.com/a/6HE0P

Question 18

Describe the graph partitioning problem

Answer 18

The graph partitioning problem is a problem in which we have a graph G(V,E), and two sets A and B.

We want to pot the nodes v in V into either A or B such that the edges crossing from A to B is minimized.

Question 19

With v in V, what is E(v) = external(v) and I(v) = interal(v)? (Graph partitioning)

Answer 19

With some node v, E(v) are the edges crossing from v’s set to the other set.

I(v) are v’s edges connected to other nodes in v’s set.

Question 20

With some v in V, what is diff(v)? (Graph partitioning)

Answer 20

diff(v) = external(v) - internal(v).

Question 21

How do you interpret diff(v)? (Graph partitioning)

Answer 21

diff(v) is the difference between internal and external edges for some node. It tells us something about how much of an improvement we can expect when moving v to the other set.

Moving v to the other set might improve diff(v). Does it decrease diff(w) for w in V, v =/= w?

Question 22

How do you improve this problem? (Graph partitioning)

Answer 22

You can exchange pairwise nodes a and b.

Question 23

How do you calculate the gain of swapping two nodes?

Answer 23

gain(a,b) = diff(a) + diff(b) - 2.

Question 24

Describe the first of the genetic algorithm.

Answer 24

With the genetic algorithm, we encode some solutions as “individuals”. They have some fitness - how well they do (eg. cycle length in TSP).

The algorithm loop looks like this:

• Increase population by mating individuals (crossover, mutate).
• Let individuals compete (eg. sort list by fitness).
• Repeat until stopping conditions are met.

Question 25

Describe crossover roughly. (Genetic algorithm)

Answer 25

In the mating process, two parents are combined to make two new children.

Crossover is the method in which the material is exchanged. We set some point in the material from which to start (two point: and end) and exchange everything in this interval.

Question 26

How do single-point and two-point crossover differ? (Genetic algorithm)

Answer 26

In single points crossover, you set a point. The children swap everything from this point to the end.

In two points crossover, you define two points to make an interval. The children swap only these intervals.

Question 27

How does mutation work? (Genetic algorithm)

Answer 27

With some random chance, the genetic material of an individual/child is changed by some small amount.

Question 28

Describe the constraint satisfaction problem.

Answer 28

In the constraint satisfaction problem, we have some nodes 1 .. .n with domain D_1 .. .D_n.

The domain can be both discrete and continuous.

The problem has constraints, often written as the edges between nodes, eg.
C(1,3) = x_1+x_3> 10
C(2,3) = x_2 - x_3 = 10

Question 29

What are some applications of the constraint satisfaction problem?

Answer 29

• Timetabling
• Graph coloring problem
• N-queen problem

Question 30

Describe min-conflicts method in pseudo code. (CSP)

Answer 30

Number_of_tries = 0;
while ( Number_of_constrained_violated > 0 AND Number_of_tries < MAX_Tries ) DO
__Select at a random a variable X that violates a constraint;
__For each value of X DO
____Determine the value of the selected variable that results in the
____highest gain ;
__End for
__Update the solution if it is beter than the previous one;
__Number_of_tries += 1;
End While

Question 31

Describe the GCSP (greedy CSP) in pseudo code.

Answer 31

Number_of_tries = 0;

while ( Number_of_constrained_violated > 0 AND Number_of_tries < MAX_Tries ) DO
__For each variable in the set of variables DO
____/* Selects the variable which will produce the higehst gain */
____Select at random a value ;
____Determine the gain;
____Keep the best gain sofar;
__End for
__Select the variable having the higest gain
__Update the solution ;
__Number_of_tries += 1;
End While

Question 32

Describe the multilevel CSP algorithm in pseudo code.

Answer 32

For ( level = Number_of_Levels ; level > 0 ; level–) /* Number of levels )
Start:
__Number_of_tries = 0;
__while ( Number_of_constrained_violated > 0 AND Number_of_tries < MAX_Tries )
__Start:
____Select at random a specified number of variables ;
__/* Number of variables = Number of Levels */
____Choose at random a value for each choosen variable;
____Calculate the gain;
____Update the solution if the current solution is better than the
____previous one;
____Number_of_tries += 1;
__End
END

Question 33

Describe the satisfiability problem.

Answer 33

SAT is a class in which you have some conditions to be satisfied (eg. a list of boolean expressions). The problem comes when you want to satisfy as many of them as possible.

Question 34

Describe the gist of tabu search.

Answer 34

The idea is to create a list of solutions or changes which are taboo for some time. You’re not allowed to go back to a solution on the tabu list, nor are you allowed to change a variable on the list.

This can either be implemented as a list with some capacity (Eg. sorted by age), or a sa list describing how many iterations you can’t change each variable for.

Question 35

Describe how Noureddine has run tabu search on boolean expressions. (Satisfiability problem)

Answer 35

1) During each iteration, he has created a list where he’s bitflipped all variables that are not taboo.
2) He’s then ranked them and selected the flip which caused the biggest gain, and sett this as the new solution.
3) Afterwards, he’s updated the tabu list to say this variable is not to be changed for some iterations.

Question 36

Describe the max-flow problem.

Answer 36

Given a weighted, directed graph with a source (Node with no edges in, only out) and a sink (Node with no edges out, only in), what is the maximum number of units we can send from the source to the sink?

Question 37

How do you solve the max-flow problem?

Answer 37

Use BFS to find a path between source and sink. Prioritize moving to nodes with lower index numbers with positive excess capacity.

Once found, identify the edge with the lowest excess capacity. Subtract this much from the excess each edge in the path.

Repeat this until there are no existing paths from the source to the sink.

Question 38

Describe skip lists.

Answer 38

Skip lists have some variable MAX_LEVELS. We create a dummy node with this many levels.

For each element we insert, we select a random height between [1,MAX_LEVELS], and connect all the adjacent pointers on the same levels to it.

Question 39

How do search a skip list?

Answer 39

Start at the dummy node’s highest level. Look at the size of the element pointed to.

• If lower, continue to that node and look at its highest level, then repeat this step.
• If it’s higher, stay at the current node, go down one level and repeat the this step.

At some point, you’ll either:

• reach the lowest level and it’s NULL (Eg. this is the highest element)
• find the element’s position.
• Find the position where the element would go, but realize the element is not there.

Question 40

Describe deletion from a skip list.

Answer 40

1) Find the element.
2) Connect pointers to it to whatever it’s pointing to at that level.
3) Delete the element object.

Question 41

Describe inserting an element into a skip list.

Answer 41

1) Search for where the element would go.
2) Connect the parent elements to it.
3) Connect it to its children elements.

Question 42

Describe the four properties for an m-way b-tree (a b-tree of order m).

Answer 42

1) All leaves are on the same level.

2) All internal nodes except the root have at most m non empty children and at least
ceil (m / 2 ) nom empty children.

3) The number of keys in each internal node is equal to 1 less the number of its
nonempty children.

4) The root has at most m children.

Question 43

Describe inserting an element into the b-tree.

Answer 43

1) Search for a position in the b-tree where the new element would fit.
2) Try inserting it.
3) Observe which of the properties the insertion violates.
4) Fix the problems.

The problems can usually be fixed by splitting the current node into three nodes (Left, right and middle), and propagating the middle element upwards. This might mean the children of this node need be split and moved either to the resulting left/right subtrees independent of each other.

Question 44

Describe deleting an element from a b-tree.

Answer 44

1) Try deleting the element.
2) Observe which properties the deletion violates.
3) Observe what we can change to make up for the problem.
4) Implement those changes.

A deletion can usually be

Question 45

Describe multi-linked lists.

Answer 45

Multi-linked lists are like linked lists, except the nodes are larger.

Each node contains several pieces of information. For a person, it might be name, age, height and shoe size.

We start with a dummy node struct with as many fields as the Person struct. It points to each field’s (Eg. name’s) lowest Person instance. This Person then has a pointer to the next Person in the sorted list, and so on.

We do this for each attribute.

Question 46

What does Floyd’s algorithm do?

Answer 46

FA calculates the length of the shortest path between all pairs of nodes in a graph.

Question 47

Describe Floyd’s algorithm in pseudocode. Be very careful to get the for loop constants to match up with the matrix accesses.

Answer 47

With adjM as the adjacency matrix:

for (int k = 1; k < n; k++) {
\_\_ for (int i = 1; i < n; i++) {
\_\_\_\_ for (int j = 1; j < n; j++) {
\_\_\_\_\_\_ int ik = adjM(i,k)
\_\_\_\_\_\_ int kj = adjM(k,j)
\_\_\_\_\_\_ int ij = adjM(i,j)
\_\_\_\_\_\_ if (ik + kj < ij) {
\_\_\_\_\_\_\_\_ adjM(i,j) = ik + kj;
\_\_\_\_\_\_ }
\_\_\_\_ }
\_\_ }
}

Question 48

Describe a mnemonic for getting the order of the variables right.

Answer 48

KIJ

Killing is joke.

Question 49

Describe a rule for getting the matrix accesses right.

Answer 49

A(i,k) + A(k,j)

Getting for i to j requires you to start at i and end up at j. k is the intermediate node we use for that.

k is our current neighborhood and we want to bridge its neighbors.

Question 50

Describe brute force string matching, with some string S and some pattern P.

Answer 50

Try matching each substring in S against P.

S = AAAB
P = AB

i = 0
AAAB
AB

i = 1
AAAB
_AB

i = 2
AAAB
__AB -> Match!

Code:
for (int i = 0; i < M.length - P.length; i++) {
\_\_ int j = -1;
\_\_ while (++j < P.length) {
\_\_\_\_ if (S[i+j] != P[j]) break;
\_\_}
\_\_ if (j == P.length) return true;
}

return false;

Question 51

Describe the Rabin-Karp string matching method, with some string S and pattern P.

Answer 51

Try creating a cheap hash of the pattern you want to match, then create that hash for each substring you want to check.

The trick comes in making the hash cheap, eg. the additive value of all the letters. When you advance the substring in S, subtract (evict) the leftmost character and add the rightmost.

P_h = hash(P, 0, P.length);
for (int i = 0; i < M.length - P.length; i++) {
\_\_ S_h = hash(P, 0, P.length);
\_\_ if (S_h == P_h) {
\_\_\_\_ int j = 0;
\_\_\_\_ while (++j < P.length) {
\_\_\_\_\_\_ if (S[i+j] != P[j]) break;
\_\_\_\_ }
\_\_\_\_ if (j == P.length) return true;
\_\_ }
}

return false;

Question 52

Describe the AVL tree structure.

Answer 52

The AVL tree is similar to a binary search tree.

We want to make sure the tree is balanced - the height should be as low as possible.

To achieve this, we keep track of the height of each subtree. By taking the difference in these values, we find what’s called the balance factor. If this is outside the interval [-1, 1], the tree is unbalanced and we need to perform appropriate rotations.

Question 53

The subtrees can be in four different states. Describe these. (AVL trees)

Answer 53

Follow this chart: http://imgur.com/a/6fd0P

The tree can be weighted to the left:

• LL (Left child, left child’s left child)
• LR (Left child, left child’s right child)

The tre can be weighted to the right, which are mirrored left-weighted problems.

• RR (Right child, right child’s right child)
• RL (Right child, right child’s left child)

Question 54

How do you do a left or right rotation? (LL or RR) (AVL trees)

Answer 54

http://imgur.com/a/od9Rm

Question 55

How do you perform a LR or RL rotation? (AVL trees)

Answer 55

http://imgur.com/a/BVWR8

Question 56

When do we need to perform rotations? (AVL trees)

Answer 56

When a node’s balance factor is something besides is outside the interval [-1, 1].