Ch. 9 random Flashcards
Unit Testing
piece of code that passes arguments to function to be tested. Calculates value expected value and compares it to the actual value. Checks whether they are equal and records result
Unit
Smallest component of a program that can be tested
Benefits of unit testing
-fast
-identifies bugs easily
-makes it easy for members to check each others code
-provides documentation
-provides confidence that code works as intended
Recursion
breaking problem down into subsets of problem.
Recursive function
function that calls itself. Passes a subset of the function as an argument. Breaks down into smaller subsets of itself until a stopping point is reached: a base case. e.g. factorial
parts of recursive function
- define recursive function
- define base case
- specify value to be returned when base case is reached
- specifying operation to be done with each returned value
Searching algorithms
-Linear Search
-Binary Search
Linear search
Iterates through each item in a list and compares each one to a key until this key is found
what is the final print of this code:
for i in range(6):
print(i)
5
Binary Search
requires list to be sorted. Selects middle value and if the key isn’t the value it checks if it’s higher or lower. It then searches the corresponding half of the list in the same manner by selecting the middle card. This repeats until the key is found or determined to not be present.
Selection Sort
finds smallest item in a list and places it in first position. The next smallest item is then found and placed in second position. This repeats for all items in the list
Insertion Sort
Start by ordering two items. Then add subsequent items into the correct position within the sorted items
Bubble Sort
Compare two items at a time and swap their positions if required. Continue through list for each pair. List may not be sorted after one pass so more passes are done on the list until it is fully sorted.
Quick Sort
Assigns an item in the list to be the pivot value. All other items in the list are sorted into sublists as either above or below this value. These two sublists get their own pivot values and the cycle repeats until there is only one item in every sublist. The list is now sorted. Can be implemented recursively.
Benefits of recursion
- clearer code since it usually uses less lines. Coding quicksort iteratively would require manually making recursion 2. Alignment with problem structure. Algorithms like quicksort involve dividing a problem into smaller parts so recursion is a natural fit.
