Problem Solving and Theory of Computation Flashcards
Computational Thinking
The ability to think logically about a problem and apply techniques for solving it.
Methods of Problem Solving
Simulation
Enumeration – list all cases
Trial and error
Theoretical Approach
Creative solution
Simulation Problems
Simulation is the process of designing a model of a real system in order to understand the behaviour of the system, and to evaluate various strategies for its operation.
Simulation applications include:
Financial risk analysis
Amusement park rides
Population predictions
Managing inventory systems
Queueing problems
Strategies for Algorithm Design
Decrease and conquer.
This involves finding a solution to a sequence of smaller, related problems until the instance is small enough to be solved directly.
A good example of this is the binary search algorithm.
Structured Programming
Structured programming is a method of writing a computer program which uses:
Top-down analysis for problem-solving.
Modularization for program structure and organisation.
Structured code for the individual modules.
Sequence
A sequence consists of one or more statements following one after the other.
Selection
Selection is implemented using an IF…THEN…ELSE statement. Some languages also have a CASE statement.
Iteration
Iteration means repetition. Most high level languages have three iterative structures.
High Level Language Structures
Structured programming is only possible
because the structures are built in to programming languages like Python, Java, VB and C#. Early programming languages had no
iterative statements.
Top-Down Design Model
Structured programming uses a top-down design technique.
The program is divided into modules, which are called from the main program.
Any of the modules may be further broken down into smaller sub-tasks, with the smallest modules performing a single function.
A hierarchy chart may be used to show the overall program structure.
Hierachy Chart
Any module shown below another module is part of the module above.
Execution takes place from left to right, always at the lowest level component.
Selection and iteration are not shown in a hierarchy chart.
Benefits of Structured Programming
Programs are more easily and quickly written.
Large programs are broken down into subtasks that are easier to program and manage.
Each module can be individually tested.
Modules can be re-used several times in a program.
Frequently used modules can be saved in a library and used by other programs.
Several programmers can simultaneously work on different modules, shortening development time.
Programs are more reliable and have fewer errors.
It is easier to find errors in small self-contained modules.
Programs take less time to test and debug.
Programs are easier to maintain.
A well-organised, modular program is easier to follow.
It is easier to find which module needs to be changed.
Self-contained modules mean that the change should not affect the rest of the program.
New features can be added by adding new modules.
Good Programming Practice
Use meaningful names for variables and subroutines.
Add lots of comments to explain each module.
Each module should perform a single task.
Selection and iteration structures should have single entry and exit points.
Keep each module self-contained by passing parameters and using local variables in subroutines.
Modular Programming
Modular design and programming techniques are most useful for large, complex programs.
Properties of a Good Algorithm
