1.3 Flashcards

1
Q

Algorithm

A

A set of instructions designed to solve a problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Identifier

A

A name given to an element of a program so it can be referred to throughout

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Good Programming Practice

A
  • Meaningful names, clear what variable is holding
  • Annotation, easier for programmers to follow
  • Program Layout, see each function and aids readability
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Variable

A

An attribute within a program whose value can be reassigned (during execution)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Constant

A

An attribute within a program which never changes its value (during execution)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Global Variable

A
  • Declared at the top of the program
  • Available to the whole program
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Local Variable

A
  • Declared inside a subroutine
  • Available only to that subroutine
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Sequence

A

Steps processed once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Selection

A
  • Uses a logical condition to determine which line of code to process next
  • Purpose: to execute code if a certain condition is met
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Nesting

A

When another selection statement is contained within an existing selection statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Repetition

A

Purpose: to repeatedly execute code until a certain condition is met

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Count

A

A value in a loop that will increase/decrease each time the loop is executed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Rogue Value

A

a value which tells the computer that input has finished

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

DIV

A

//

How many times one number goes into another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

MOD

A

%

Remainder after DIV

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Lossy Compression

A
  • Cannot be decompressed to yield back the original data
  • Not Good method for critical data such as text
  • Good for digitally sampled analogue data e.g. Sound/Video/Graphics
  • Algorithms vary but many use threshold truncation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Lossless Compression

A
  • Original message can be decompressed back to it’s original form
  • Good for text
  • Good for high quality media e.g. .FLAC .PNG
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Character Combinations (Compression)

A

Finding frequently occurring character combinations and replace them with tokens

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Run Length Encoding

A

Replace long strings with a number

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Photo Compression

A

Approximate all shades of blue in a photograph to one shade and only store this colour instead of every pixel

21
Q

Sub Sections

A
  • Algorithms and programs can be broken down into smaller parts.
  • These are named, reusable pieces of code that can be called any number of times within an algorithm to perform a specific task.
22
Q

Sub Sections Advantages

A
  • Can be developed by teams, easier to write.
  • Code is more readable
  • Avoids duplication of code.
  • Sections can be tested individually.
23
Q

Standard Module and Function

A

STANDARD FUNCTION
Carries out a common task for a standard situation in a program and is provided by the compiler/interpreter

STANDARD MODULE
Contains a group of related standard functions

EG: Module = math
Function = math.cos(x)

24
Q

Standard Module Advantages

A
  • Pre-written / No need to write again (Saves Development Time)
  • High Quality as written by experts
  • Already Tested/Used – Less Errors
25
User defined sub functions
a section of code (method) which is written for a specific purpose by the programmer
26
Parameter
a value which can be passed to a procedure or function
27
Reference Parameter
the memory address of the original data is passed to the procedure - The (original) data can be altered - A list, object or any non-primitive data type
28
Value Parameters
a copy of the data is passed into the procedure - Useful in calculations (not change original data) - Avoids unwanted side – Prevents the original value being changed by mistake
29
Linear Search
- Used on an unordered (or ordered) array METHOD - Cycle through each element in turn - Compare current element with SearchValue until a match is found or we get to the end of the list
30
Dry Run
A dry run can be used to determine what a section of unknown code does.
31
Binary Search
- Used for searching an ordered array METHOD - Calculate mid element in the array - Compare SV with the middle element - If SV is not found, search lower/upper half - Repeat until found (or not present in array)
32
Bubble Sort
- A pass through the data comparing each value with the following one and swapping values if necessary - A number of passes is made until the data is in order
33
Insertion Sort
- Whilst being processed, the array is effectively split into sorted/unsorted - Items are copied one by one (from unsorted part of the array) - Each new item is inserted in the correct place in the output (sorted part of the array)
34
Why Psuedocode
- Language independent - Easy to read/understand Translatable into any programming language
35
Logical Error
A bug in a program that causes it to operate incorrectly, but not to terminate abnormally - produces unintended or undesired output or other behaviour, although it may not immediately be recognised as such
36
Recursive Algorithm
- Calls itself (with different input values) until the terminating condition is met. - Values are placed onto the stack - Complicated to program and debug - Uses more memory, if not terminated could use all stack space causing the program to crash - Can be a more elegant solution to a problem e.g. factorial - Usually less lines of code.
37
Recursion Potential Problems
- Difficult to program (effectively) - Memory overheads of stack use with many recursive calls - Infinite Loop (Run out of memory) - Stack Overflow Exception risk - Difficult to debug if there is a fault
38
Quick Sort
- Quicksort is a recursive sorting algorithm METHOD - Select a pivot value - Re-order the data, producing 2 sub-lists: one which contains items smaller than the pivot, one which contains items greater than the pivot - Perform the same action on the sub-lists (recursively) until each sub-list has only one element - Rebuild the List
39
Big O
An approximation to compare algorithm efficiency - Constants are dropped - As n tends towards infinity, the constant will become insignificant - The biggest value of O will always override all other values
40
Big O, 1 loop through all items
O(n)
41
Big O, 2 nested for loop
O(n^2)
42
Big O Linear Search
O(n) The time to complete grows linearly in comparison to the size of the data.
43
Big O Binary Search
O(log n) The time to complete initially grows in a linear way when compared to the size of the data. As the data size grows larger the time taken starts to flatten off.
44
Big O Quick Sort
O(n log n)
45
Big O Bubble Sort/ Insertion Sort
O(n^2)
46
Big O Fibonnacci
O(2^n)
47
Big O Factorial
O(n!)
48
is cato cool
yes