Topic 4: Computational Thinking Flashcards
sub-procedure
define
A section of code in a program that does a specific job.
Can be called by name when needed without naming the details as these are wrapped in the procedure. It is therefore an example of abstraction.
pre-fetching / caching
define
Building libraries of pre-formed elements for future use (e.g. using Java libraries to increase efficiency, making sure you have your most commonly used spices ready at the front of your cupboard for cooking etc.)
pre-condition
define
Starting state before algorithm is executed, conditions that need to be fulfilled.
e.g. have to have the required ingredients, a place to cook, pre-conditions while making decisions in cooking (“Are the carrots still hard? Cook them a bit longer”).
post-condition
define
Final state after execution of algorithm, the state you are trying to achieve/ lead up to, the final result.
concurrent processing
define
execution of different instructions simultaneously by multiple processors
sequential/linear search
define
Usual search, go through every value and compare to the target value.
pros and cons of sequential/linear search
Pros:
- Simple to implement
- data doesn’t need to be in order.
Cons:
- Inefficient with large number of elements – may have to go through every single one of them
- time consuming
binary search
define
Values in order. Compare search value with middle value. If smaller, compare to middle value of sub-array to the left. If larger, compare to sub-array to the right, and so on.
pros and cons of binary search
Pros:
- Faster than sequential search
Cons:
- Too complicated for small number of elements
- Only works on sorted lists
- difficult if data is constantly being added.
bubble sort
define
Compare adjacent values. If not in order, swap around
pros and cons of bubble sort
Pros:
- Simple to write, less code
Cons:
- Takes more time to sort – average time increases almost exponentially as number of elements increase.
selection sort
define
Splits array into sub-arrays. First sub-array is sorted, second is unsorted. e.g. to sort in ascending order, find the smallest value, place it in the correct position in the first sub-array by swapping it with the element that was there, move position of beginning of sub-array forward one, loop through the rest (second sub-array) to find the smallest value again. Repeated for all elements.
pros and cons of selection sort
Pros:
- Good for small lists
Cons:
- Not efficient with big number of items – have to find the smallest value many times.
collection
define
Group of objects.
No assumptions are made about the order of the collection (if any) or whether it can contain duplicate elements.
We add and retrieve data from them.
efficiency of an algorithm
define
Amount of computer resources required to perform algorithm’s functions
correctness of an algorithm
define
Extent to which algorithm satisfies specification
reliability of an algorithm
define
Capability to maintain performance
flexibility of an algorithm
define
Effort required to modify algorithm for other purposes
Fundamental operations of a computer
- Adding (and subtracting) values
- Comparing values/data
- Retrieving data
- Storing data
Machine language
define
Low-level language directly understood by computer, made up of binary numbers
Assembly language
define
Low-level language using symbols for instructions and memory addresses
High-level programming language
Uses elements of natural language. Easy to use for humans and more understandable.
Abstracts some areas of computing systems, would otherwise take too long to write our systems in machine code.
What do programming languages need to have?
characteristics of programming languages
- Fixed vocabulary - Instructions for operations do not change. e.g. “print” will always print
- Unambiguous meaning - Clear instructions
- Consistent grammar and syntax - The way we declare and use language features must be the same.
- Provide a way to define basic data types and operations on those types - ability to write functions/procedures
- It has to run on/be able to be processed by a computer - it must have a compiler/interpreter
source code
define
Original code/program developed using high level language. Needs to be translated into machine code to be run/executed by the computer.
object/target program
define
Program translated into machine language.
methods of translating a source code into a target program
Compiler: Executes translation process only once, translates the whole program. Object program is saved so it doesn’t need to be compiled again. All errors are displayed when the whole program is checked, compilation ends only once errors are fixed. Example: C++
Interpreter: Reads, translates and executes program line by line. Errors are displayed after each line is interpreted. Goes through the process every time the program is run, much slower than a compiler. Example: BASIC
variable
define
Used to store a data element that can be changed during program execution. Has an identifier and type.
constant
define
Elements and quantities that don’t change.
e.g. final double PI = 3.14
object
define
Comprised of data and methods (operations that can be performed by the object)
Advantages of breaking down into sub-programs
- Breaking complex job into simpler tasks
- Distributing program amongst different programmers
- Code reuse across multiple programs
- Reducing code duplication in program
Advantages of collections
- Methods are predefined algorithms, can immediately use
- Software reuse
