1.9 Algorithms and Programming Flashcards
What is an algorithm?
A series of steps (sequence) to solve a specific problem.
State 3 methods of defining algorithms.
- Flowcharts
- Pseudocode
- Structured english
What is pseudocode? (2)
- A method of writing code without using syntax of any particular language.
- Shows the structure of a solution.
What is structured English?
A cross between pseudocode and written English.
What is a variable?
A named space in the memory that contains a single piece of data.
What is a constant?
The same as a variable except the data
cannot be changed in the program.
Name 3 techniques to make code readable.
- Indenting the code
- Writing annotations to explain the code to programmers
- Using appropriate identifiers
State 2 types of a variable.
- Local
- Global
What is a local variable? (2)
- Only exists until the subroutine in which it was created ends.
- Only visible in that subroutine.
What is a global variable?
Exists throughout the program and can be read/ written from any subroutine.
What is a parameter?
It is an item of data that is passed from one subroutine to another
What are the two ways of passing a parameter?
- Passing by value.
- Passing by reference
What is passing by value? (2)
- A copy of a value passed from one subroutine to another.
- The original value cannot be changed by the subroutine that receives it
What is passing by reference? (2)
- An actual variable is passed from one subroutine to another
- The original value can be changed by the subroutine that receives the variable
What is difference between 5 DIV 3 and 5 MOD 3?
5 DIV 3 = 1 i.e. integer division
5 MOD 3=2 i.e. remainder after division
What is sorting?
Placing data into a specified order .e.g. alphabetical, numerical or other
State 2 sorts.
- Bubble sort
- Insertion sort
How does Bubble Sort work? (4)
- A pass is made through the data, comparing each value with the following one, and swapping if necessary.
- It compares the 1st with 2nd, 2nd with 3rd and so on.
- When it has worked to the end it has completed one pass.
- A number of passes is made until the data is in order/ no swaps
When is Bubble sort most appropriate to use?
Works best on smaller, nearly sorted data.
How does Insertion Sort work? (4)
- Takes an element out the data and compared with a sorted list
- Items in the sorted list are moved up/ down to enable new items to be added in the correct place.
- It initially assumes only the first number is in the correct order.
- With each pass the number of items assumed correct increases by one.
When does insertion sort works best?
Works best on small, jumbled up files.
What is searching?
Locating an item in a data structure
Name two types of searches.
- Linear search
- Binary search
How does a linear search work?
Starts at one end of a data structure and examines every element in order until the item is found.
When is a linear search faster? (2)
- Number of items to search is small.
- The item to search is one of the first data items in the list
How does a binary search work? (4)
- Start at middle & check if value to be found is larger or smaller than the current value.
- If larger, discard smaller values. If smaller,
discard larger values. - Search in the middle of the selected data and repeat step 1. This eliminates half the data with every pass.
- Continue until the number is found or there is no more data to search.
When is binary search faster?
Good on large sorted sets of data
What is Top-Down Design?
Breaking down a problem into smaller problems, and smaller problems into smaller problems until the problems are simple and can be solved easily.
What is a sequence?
Lines of code that are executed one after another in the order in which they are written.
What is a selection?
One path through the code will be selected if a condition is met. An example of selection code is IF.
What is repetition?
Code that is executed more than once. Example: For, While, loop.
What is count?
An integer that keeps track of how many times a code has been run.
What is a Rogue Value? (2)
- An invalid value to represent a special case.
- Often used as an exit condition from a loop
What is modular programming?
The splitting up of a large piece of code into smaller chunks (modules) of code that perform a specific task.
State 4 advantages of using modular programming.
- Different modules can be allocated to different programmers.
- Programmers with different skills are given tasks appropriately.
- Modules can be designed separately and tested separately.
- Modules can be reused reducing risk of bugs.
What is a subroutine?
It is a piece of code that performs a specific task.
What is a function?
Code that must return a value.
What is compression?
Making a file occupy less space on a disk.
State 4 advantages of using compression.
- Can transfer files faster
- Means that the disk has more space and can hold more files.
- Faster reading and writing of a file.
4 Helpful for streaming and downloading files
State 2 disadvantages of using compression.
- Can result in lower quality of files.
- You may lose information that can’t be recovered.
State 2 types of compression.
- Lossy
- Lossless
What is lossy compression?
Removing data to decrease the file size.
What is Lossless compression? (2)
- Shrinks the whole file while keeping all of the quality.
- Works by finding repeated patterns and compressing those patterns.
What is lossless compression based on?
The LZ compression method developed by Lempel and Ziv.
State 2 advantages of lossless compression,
- The file can be restored to its original quality.
- The file can be compressed up to 50% without losing quality.
State 2 disadvantages of lossless compression.
- A lossless compressed file is not as small as a lossy compressed file
- Does not work well with random data as it is dependent on patterns in data
What is run- length encoding? (2)
- Compressing clusters of number. E.g. pictures with lots of the same color.
- A form of lossless compression
Give an example of run- length encoding.
Original: 0000 0000 0000 1111 1000 0000
Compressed: 12(0); 5(1); 7(0)
Why is testing used?
To verify that a program is bug free.
List 5 standard tests on data entry (E.g. input an integer between 1-10).
- Normal data (5)
- Extreme data (1,10)
- Invalid data (0,11)
- Data type (hello)
- Missing data ()
Why is normal data used?
To see if the program processes normal data.
Why is extreme data used?
While valid it is as invalid as possible.
Why is invalid data used?
Should not work even if close to valid number.
Why is data type used?
Testing to see if an error message appears.
Why is missing data used?
To check the code doesn’t crash when data is missing.
