Fichas
Week 3: Sorting, time complexity & exceptions/assertions
Fichas del conjunto (19)
- 1Bubble sort
- 2Bubble sort optimisation- Invariant: at every traversal, the largest yet unsorted element gets to its final place
- Everything right of the mark is sorted, in its final position and grows by 1 each pass
- 3Bubble sort II- Initialise swapped to False
- Set true every time there is a swap
- If no swaps occur on an iteration, then break - 4Incremental algorithm- Given a sorted list and one new element
- Use one (or a few) iterations of the algorithm to return a sorted list that has the new element
- Do not need to re-compute everything after a small change (can reuse work) - 5Stable algorithmMaintains the relative order among elements
- 6Bubble sort: stability and incrementality- Incremental if new element is appended at beginning, not the end
- Stable because we only swap under > condition (not >=) - 7Selection sortInvariant: everything left of the mark is sorted, in its final position and grows by 1 each pass
- 8Selection sort: stability and incrementality- Not incremental
- Not stable - we are swapping non-consecutive elements - 9Insertion sort- Invariant: elements in S are sorted and grow by 1 in each iteration
- Each pass, store the first unsorted value X in a temporary place, shift all sorted elements bigger than X one position to the right and move X into newly freed space
- 10Insertion sort: stability and incrementality- Incremental if new element is appended at end, not the beginning
- Stable because we only swap under > condition (not >=) - 11Computational (time) complexityNumber of elementary steps T(n) needed to compute output for an input of size n
- 12Big O complexityCompute an upper bound f(n) to T(n) that ignores parts of T(n) that do not add significantly to runtime
- 13Sorting complexities
- 14Precondition- Properties of the data that must be true before a piece of code is executed
- If violated, the result of the execution is undefined (unknown)
- "Design by Contract" => precondition must be met by caller - 15Postcondition- Properties of the data or I/O that results from the code being executed
- If violated, there is a bug in the code
- "Design by Contract" => postcondition must be met by callee - 16Exception- Run-time event that breaks the normal flow of execution
- Use exception handling to transfer control to a handler (block of code which can recover from event)
- Deals with errors from code users (when reading from input, or precondition for an exported function/method is not met) - 17Built-in exception types
- 18AssertionDeals with bugs (checks the internal state of a program is as expected)
- 19Assertions vs exceptions- Exceptions ensure program robustness i.e.any data is within expected values (preconditions)
- Assertions ensure program correctness
i.e. internal state is as expected (debugging), checking invariants and postconditions hold
- Code cannot recover from assertions, but can from user errors exceptions
- Use exceptions for exported functions, otherwise assertions (you are your own user, so it is a bug)
Información
- Descripción
- (FIT1008: Intro to Computer Science) Computer Science Fichas sobre Week 3: Sorting, time complexity & exceptions/assertions, creado por Melina Mackey el 27/04/2020.
- Creado por
- Melina Mackey
- Visitas
- 0
- Historial
-
- Creado por Melina Mackey · 25 abr 2020
- Copiado por Melina Mackey · 26 abr 2020
- Copiado por Melina Mackey · 27 abr 2020
- Valoración