1 - Algortihms Flashcards
Define algorithm.
Finite sequence of step-by-step instructions carried out to solve a problem.
How do you represent an algorithm?
Flow chart or trace table.
What does an oval represent?
Start/end.
What does a rectangle represent?
Instruction.
What does a diamond represent?
Decision.
How do you sort an unordered list?
Bubble sort or quick sort.
How do you do a bubble sort algorithm?
.Start at top and work left to right comparing 2 adjacent items - swap if not in order.
.When at the end of the working list the final number is in it’s final position - no longer in the working list.
.Repeat step 1 if any passes made.
.Finished if no swaps made in a pass.
How do you do quick sort?
.Choose midpoint (middle right) as pivot.
.Write all items less than in same order as a sub-list.
.Write pivot.
.Write remaining items in a sub-list.
.Repeat.
.Stop when all items have been a pivot.
What could happen to the pivots at each pass in a quick sort?
Could double.
What are the three bin packing algorithms?
First-fit, first-fit decreasing and full bin.
How do you find the lower bound?
Add all values and divide by max each bin holds - optimal solution.
How do you do first-fit? What are the advantages/disadvantages?
.Take in order given.
.Place in first available bin starting at bin 1.
.A - Quick.
.D - Not good solution.
How do you do first-fit decreasing? What are the advantages/disadvantages?
.Sort into descending order.
.Apply first-fit.
.A - Good solution, easy.
.D - Not optimal solution.
How do you do full bin? What are the advantages/disadvantages?
.Observe and find combinations which fill a bin - pack them first.
.Use first-fit for remaining.
.A - Good solution.
.D - Difficult.
Define order/complexity of an algorithm.
How changes in size affect run time/completion. If an algorithm has order f(n) the increasing size to m will increase run time by factor f(m)/f(n) approximately.
What order does bubble sort have?
Quadratic.
What happens if a program of linear order increases by factor k?
k times as long to complete.
What happens if a program of quadratic order increases by factor k?
k^2 times as long to complete.
What happens if a program of cubic order increases by factor k?
k^3 times as long to complete.
