fundamentals of algorithms Flashcards
explain the term algorithm
a set of instructions that can be followed to complete a task
explain the term decomposition
breaking down a problem into smaller, more manageable problems and solving each one individually
explain the term abstraction
the process of removing unnecessary details from a problem so the details can be focused on
explain algorithmic thinking
a logical way of getting from the problem to the solution
what are the 4 flowchart symbols?
rounded box - START or END
rectangle - calculation or process
parallelogram - input or output
diamond - decision
determine the purpose of simple algorithms
dry-run the algorithm (manually working through code with executing it on a computer):
- trace table
- visual inspection
more than one algorithm can be used to solve the same problem
some algorithms are more efficient that others in solving the same problem
answer with TIME EFFICIENCY
explain how the linear search works
- used for an UNORDERED list
checks each item in the list to find correct one
1. looks at first item in list
2. checks it with item you are looking for
3. if it is the one you are looking for, STOP
4. if not, repeat until you either find the item or get to the end of the list
explain how the binary search works
-used for an ORDERED list
divides the list in half, keeping the part that contains the required item and continuing until you have the correct one left
1. find the middle of the list (n+1) / 2
2. check it with the item you are looking for
3. if it is the one you are looking for, STOP
4. if not, if the item you are looking for comes before the middle item, get rid of the second half of the list OR if the item you are looking for comes after the middle item, get rid of the first half of the list
5. find the new middle item
6. repeat until you have found the item or there are no items left
compare linear and binary search
- for short lists the run time of both will be similar
- LINEAR is simpler
- BINARY is more efficient
- LINEAR can be used on any time of list
- for larger lists the run time of BINARY is much quicker
explain how merge sort works
- a divide-and-conquer algorithm
1. split list in half to make sub-lists
2. keep splitting the sub-lists until all lists contain one item
3. merge pairs of sub-lists and sort the items into the right order
4. keep merging the sublists until all items are in the correct order
explain how bubble sort works
-used for UNORDERED lists
1. look at first 2 items of list
2. if they are in the correct order don’t do anything, if they are in the wrong
3. move to next pair and compare
4. continue till you get to the end of the list
5. don’t compare last item as it has gotten to its place
6. swap until there are no swaps in a pass
compare merge and bubble sort
-BUBBLE is inefficient therefore very slow
-BUBBLE uses less memory; list is already in order
-MERGE has a consistent running time
-MERGE uses more memory: has to create additional lists
