4.2 Thinking in Program Design Flashcards
What are the four standard algorithms?
Sequential Search
Binary Search
Bubble Sort
Selection Sort
What is Sequential Search?
Start at the start of an unsorted list comparing items until you find what you want.
What is a Binary Search?
Start at centre of sorted array, comparing with values and going lower or higher.
What is Bubble Sort?
Comparing adjacent tiles and switching them if they are in the wrong order.
What is Selection Sort?
Divides list into two parts, sorted and un sorted. Finds the smallest and puts it at the beginning.
Evaluate Binary Search
Faster O(log n) but can only be a sorted list.
Evaluate Sequential Search
Slower O(n)
but can be performed on an unsorted list
Evaluate Bubble Sort
Can quit early if few swaps are needed but on bigger code will need lots of swaps.
Evaluation Selection Sort
Must always perform n swaps, it can’t finish early.
But is better on longer lists
What is this?
Terminator - start or end value.
What is this?
Input/Output
What is this?
Process - something is happening.
What is this?
Decision.
What is used to measure the efficiency of an algorithm?
Run Time,
What can affect the run time of an algorithm?
Computer/Hardware
Representation of ADTs
Efficiency of Compiler
Competence of Programmer
Complexity of Algorithm
Size of Input
What is complexity?
A measure of the amount of time/space required by an algorithm for a given size.
How is time represented?
t(n)
How do we measure complexity?
Predicting the number of times the principle activity is performed for the input.
In best case, average case, and worst case.
How long does a single loop take to run?
Repeats n times
Takes n time to run.
How long does a nested loop take to run?
Repeats n times
Takes n*n to run.
What is more efficient for or while?
While because it won’t always run if the condition isn’t met.
What are the advantages of linked lists?
Can expand and easily add and take things away.
What are the advantages of an array?
Easier to find things.
