D1, C1 - Algorithms Flashcards
What is an algorithm
A process or a set of instructions that need to be followed PRECISELY
How can you use a table to implement algorithms (what goes in the top row (headers))
Step number
Variables (such as A, B, et…)
Print (if things are printed)
What numbers does an algorithm generate if it generates (1, 1, 2, 3, 5, 8, …)
Fibonacci sequence
What is a flow chart
A way of listing instructions or a process
What shape is a start / end in a flow chart
Oval
What shape is an instruction in a flow chart
Rectangle
What shape is a decision (question) in a flow chart
Diamond
What is a trace table
A table that record actions / results
What goes in the header of a trace table
Actions
Variables
Print
Decisions
Perform a bubble sort on 4, 1, 3, 2 to get them into ascending order
1) 4, 1, 3, 2
2) 1, 3, 2, 4
3) 1, 2, 3, 4
4) 1, 2, 3, 4
What are the steps for a bubble sort
1) Start at the beginning and move from left to right comparing adjacent items, if in order leave, if out of order swap
2) When you get to the end of the working list, last item will be in its final position, this item is no longer in the working list
3) If you have made some swaps in the last pass repeat step 1
4) When a pass is completed with no swaps, every item is in final position and the list is in order
What is ascending
Smallest to biggest
What is descending
Biggest to smallest
Bubble sort into ascending order:
24, 18, 37, 11, 15, 30
1) 24, 18, 37, 11, 15, 30
2) 18, 24, 11, 15, 30, 37
3) 18, 11, 15, 24, 30, 37
4) 11, 15, 18, 24, 30, 37
5) 11, 15, 18, 24, 30, 37
What working should you show with bubble sorts
Circle letters / numbers being swapped
Write swap / leave
Perform a FINAL pass to show nothing changes