Go on. Explore!

lvl 0 • 0 xp

lvl 1

Home Market Decks Interests

Algorithms

memorize.ai (lvl 286)

Section 1

Preview this deck

Prim (Distance Matrix)

Front

1 / 11

Competitive Programming

0.0

0 reviews

5			0
4			0
3			0
2			0
1			0

Active users

All-time users

Favorites

Last updated

5 years ago

Date created

Mar 1, 2020

Cards (11)

Section 1

(11 cards)

Prim (Distance Matrix)

Front

1. Choose any vertex to start the tree 2. Delete the row in the matrix for the chosen vertex 3. Number the column in the matrix for the chosen vertex. 4. Put a ring around the lowest undeleted entry in the numbered columns (If there is an equal choice, choose randomly.) 5. The ringed entry becomes the next arc to be added to the tree. 6. Repeats steps 2,3,4 and 5 until all rows are deleted

Back

First-Fit Decreasing

Front

1. Reorder the items so that they are in descending order. 2. Apply the first-fit algorithm to the reordered list.

Back

Dijkstra

Front

(e.g. finding the shortest path from S to T through a network) 1. Label the start vertex, S, with the final label, 0 2. Record a working value at every vertex that is directly connected to the vertex, X, that has just received its final label. •Working value at Y = final value at X + weight of arc XY •If there is already a working value at Y, it is only replaced if the new value is smaller. •Once a vertex has a final label it is not revisited and its working values are no longer considered. 3. Look at the working values at all vertices without final labels. Select the smallest working value. This now becomes the final label at that vertex. (If two vertices have the same smallest working value either may be given its final label first.) 4. Repeat Steps 2 and 3 until the destination vertex, T, receives its final label. 5. To find the shortest path, trace back from T to S. Given that B already lies on the route, include arc AB whenever final label of B - final label of A = weight of arc AB.

Back

Bubble Sort

Front

1. Write out the the numbers/names given. 2. Record only each full pass and not each bubble. 3. One Pass consists of comparing the first and seconds numbers, then the second and third numbers and compare the first and second numbers and so on until we work down the list. 4. Now repeat the procedure down the whole list. This is the second pass. 5. The bubble sort algorithm terminates when a pass produces no changes to the ordered list i.e. the last two passes will be identical.

Back

Happy Numbers

Front

1. If the number is a single digit, square it (multiply it by itself). 1. If the result or the original number has multiple digits, take each digit by itself and square the digit (multiply it by itself). 2. Add the resulting square numbers together 3. Repeat Steps 1 and 2 until the answer is 1 unless a loop is clearly identified. 4. If the answer is 1 then the original number is happy.

Back

Quick Sort

Front

1. Write down the list 2. Select the pivot(mid point) 3. Now write all the numbers smaller than the pivot to the LEFT of it ( called SUBLIST L₁) and all the numbers larger than it to the right (called SUBLISt L₂). Deal with each number in order and do not reorder these sublists. 4. Apply steps 2 and 3 to each sublist 5. Stop only when each sublist contains only one number.

Back

First-Fit

Front

1. Take the items in the order given 2. Place each item in the first available bin that can take it. Start from bin 1 each time.

Back

Binary Search

Front

1. Use one of the sorting algorithms (quick sort or bubble sort) in ascending or alphabetical order. 2. If we are looking NAME in a list, then compare name with the middle term in the list. a) The middle item is name in which your search is complete b) NAME occurs before the middle term c) Name occurs after the middle term 3. If b) is true then repeat step 2 on the first half of the list. If c) is true then repeat step 2 on the second half of the list. 4. Keep repeating steps 2 and 3 until either NAME has been located OR You have shown that NAME does not appear in the list.

Back

Kruskal

Front

1. Sort the arcs into ascending order of weight. 2. Select the arc of least weight to start the tree 3. Consider the next arc of least weight from the remaining arcs. If it forms a cycle discard it. If it doesn't form a cycle add it to the tree.

Back

Prim

Front

1. Choose a starting vertex. 2. Choose the vertex nearest to the starting vertex, add this and the associated edge to start your tree. 3. Next scan all the unconnected vertices and choose the one that has the smallest distance to ANY vertex in the tree (i.e. the one which is the smallest distance away overall from the vertices in the tree. Choose this and connect it to the tree 4. Repeat the previous step until all the vertices are connected to the tree.

Back

Full-bin packing

Front

1. Use observations to find combinations of items that will fill a bin. Pack these items first. 2. Any remaining items are packed using the first-fit algorithm.

Back