Unit 4 - Theory of Computation Flashcards
What is an algorithm?
A sequence of steps that can be followed to complete a task and that always terminates.
What is simulation?
Designing models of real life systems to understand behaviour and stratergies.
What is enumeration?
Looking at all the different possibilities
What is theoretical approach?
Finding the best way to solve a problem
What is trial and error?
Finding solutions until you find the right one
Strategies for algorithm design
- Decrease and conquer
- Finding solution to a sequence of smaller problems
until you get to the smallest problem and build up from
there - Binary search algorithm
- Finding solution to a sequence of smaller problems
What is insertion sort?
- Used for a small number of elements
- One by one going through elements and moving it to correct place
- Repeats until elements in order
What is bubble sort?
- Used for small number of elements
- Swapping elements from highest to lowest until in correct order
What is linear search?
Starts at the beginning and searches every element of the list
What is binary search?
“Divide and conquer”
- Halving search area repeatedly until you find item
Properties of a good algorithm
- Should execute efficiently with fewest steps possible
- Must terminate at some point
- Should allow invalid inputs
What is the top-down design model?
Modules being broken down into sub-units
- Hierarchy charts
Benefits of structured programming
- Easier to manage and program
- Multiple people can work on different modules at the same time
- Easier to find errors
What is modular programming?
Used for large complex programs, minimilses need for duplication
What is the purpose of testing?
Helps reveal errors in the program
