Section 2 - Problem solving and theory of computation Flashcards
What is software?
The name given to any program written for a computer
What are the stages in writing software?
Analysis > Design > Implementation > Testing > Evaluation
One phase doesn’t have to be finished before another begins
What happens during analysis?
The requirements and goals of the project must be established with a data model created. The needs of the end user are considered, and alternative solutions may be suggested
What happens during design?
Data structures will be specified, algorithms, user interfaces, screen designs and reports will all be designed
What happens during implementation?
The program code is written
What happens during testing?
The whole system must be tested for the presence of errors, using selected test data covering normal, boundary and erroneous data
What happens during evaluation?
The system is evaluated according to given criteria
What is a puzzle’s input?
Something that defines an instance of the puzzle. The instance is either specific or general
What is an exhaustive search?
Trying every possible combination of numbers
How does a binary search work?
- Look at the middle item of a sorted list and compare it to the term you are looking for. If it is the correct term then stop searching. If it is greater than the item being sought, discard the second half of the list. Else, discard the left half. Repeat until the item is found
What is the goal of structured programming?
To improve the clarity and maintainability of programs
What programming structures are used in structured programming?
Sequence, selection, iteration
What are block-structured languages?
Languages like Python, C# and Pascal. The programs are made up of a series of blocks
What is a block?
A section of code consisting of 1 or more statements. Each block should have 1 entry and 1 exit point.
What is top-down design?
The technique of breaking down a problem into the major tasks to be performed, before breaking each part down even further into its own self-contained module or subroutine
What are the advantages of structured (modular) programming?
- Individual modules can be separately tested
- Modules can be kept in a module library to be reused in other programs
- Large programs can be split into modules that are easier to read, debug and maintain
- Several programmers can work on separate modules, shortening development times
What is a hierarchy chart?
A tool used to represent the structure of a program, showing how the modules relate to one another. The chart is depicted as an upside down tree shape
What is the downside of a hierarchy chart?
It does not show the detailed program structures required in each module
What is an algorithm?
A set of clear and precise steps that produce the correct output for any set of valid inputs. It must always terminate at some point.
What are the properties of a good algorithm?
- It should allow for invalid inputs
- It should execute efficiently, in as few steps as possible
- It should be designed in a way that others can understand it
What are the most common types of algorithms?
- Internet-related algorithms
- Route-finding algorithms
- Compression algorithms
- Encryption algorithms
What is the purpose of internet-related algorithms?
They are used to manage and manipulate huge amounts of data stored on the internet
What is the purpose of route-finding algorithms?
They work out the most efficient route to get from A to B. This could be cars on a road or data packets across a network
What is the purpose of compression algorithms?
They are used to compress data files so they can be transmitted faster or held in smaller amounts of storage
