Ch. 9 random Flashcards
Unit Testing
Individual component/module of system tested in isolation to verify correctness. Can be done with a 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
steps of making 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, the mid-interval 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 mid-interval. This repeats until the key is found or determined to not be present. [Like quicksort but for searching instead of sorting]
-floor divides the half interval so goes to lower value if the half interval is in between two values
Selection Sort
Passes across every item in list from left to right. First element being passed over is current element. The algorithm compares current with next element and if it is smaller, that element is now the current element. Continues comparing the rest of the list. By the end of the pass, the current element must be the smallest so it is placed in first position. The next smallest item is then found by passing through unsorted items in the list again and placed in second position. This repeats for all items in the list
Insertion Sort
First item is considered sorted all elements to right considered unsorted. Passes across each element in list starting from second element and inserts them into sorted list at the correct position.
Bubble Sort
Passes through list and compares each pair of adjacent items at a time and swaps their positions if item on right is smaller. Continues 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. At most the number of passes need will be equivalent to the input size.
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 more readable code since it usually uses less lines. Coding quicksort iteratively would require manually making recursion
- Alignment with problem structure. Algorithms like quicksort involve dividing a problem into smaller parts so recursion is a natural fit.
Binary Search worst case time complexity
O(log2(n))
Binary Search best case time complexity
O(1)
Linear Search best case time complexity
O(1)
Linear Search worst case time complexity
O(n)
O(1) meaning
the time taken to complete a task remains constant regardless of input size
purpose of return statement
to end function and to pass result of a function back to the calling code
Disadvantages of recursion
- Slower execution time due to memory overheads
- If recursion is too deep, there is danger of running out of space on the stack and the program crashing
XOR Gate
Exclusive Or Gate that only outputs 1 if only one of its two inputs is 1 but not both. Created by passing A and B to both an OR Gate and a NAND Gate which are then passed on to an AND Gate.
Hardware
physical components of a computer system.
Examples processor, memory, storage devices, any input or output device, peripherals, registers, logic gates
Software
general term used to describe programs/instructions that are executed by the processor.
e.g. Microsoft Word, Microsoft Teams, Spotify
