Programming ‘theory’

Question 1

Define algorithm

Answer 1

• An algorithm is a sequence of steps that can be followed to complete a task

Question 2

Define Decomposition

Answer 2

• Decomposition means breaking a problem into a number of sub-problems, so that each sub- problem accomplishes an identifiable task, which might itself be further subdivided.

Question 3

Define Abstraction

Answer 3

• Abstraction is the process of removing unimportant detail from a problem
• so that attention can be given to the important parts of a problem
• to make the problem easier to solve


(so that the important details can be focused on. This can make solving the problem easier.)

Question 4

Efficiency is what

Answer 4

• Efficiency looks at how much time it takes to run a particular algorithm and how much space is needed

Question 5

Do you say more efficient when they ask for advantages ?

Answer 5

• say ‘faster’ not more efficient when they ask for advantages (e.g. of using a linear search vs a binary - faster for shorter lists)

Question 6

When linear search used

Vs binary

Answer 6

• Although linear and binary searching produces the same overall results, linear search is best used when the data is not in order, or for smaller lists. However, when the list is much longer and the data is in order, it is far more efficient to calculate the indexes needed to perform a binary search.

Question 7

• Linear search advantages (4)

Answer 7

• Performs well with small and medium-sized lists
  
  • Fairly simple to code
  • The data set does not need to be in any particular order (some algorithms need an ordered list)
  • It doesn’t break if new items are inserted into the list.

Question 8

• Linear search disadvantages (2)

Answer 8

• May be too slow to process large lists or data sets
  
  • If the search criteria only matches the last item in the list, the search has to go through the entire list to find it.

Question 9

• binary search advantages (2)

Answer 9

• Very good performance over large ordered lists.
  
  • A binary search takes a maximum of 8 loops to find an item in a list of 1000 items, whilst a linear search worst case would have to search all 1000 items in the list.

Question 10

• Binary search disadvantages (3)

Answer 10

• Binary search can only work on an ordered list. If the list is random, then a linear search is the only way
  
  • It is a bit more complicated than a linear search to code and so for small lists a linear search is just as good.
  • If it is a constantly updated list with items added or removed, the list will need re-ordering every time which may slow down the overall performance compared to a linear search.

Question 11

When does bubble sort stop

Answer 11

• bubble sort stops when: Once the algorithm has completed a pass without swapping anything and it knows that the list is now ordered and can stop.

Question 12

When does merges sort stop

Answer 12

• Merge sort stops when: This process of merging and sorting lists continues until all of the individual lists are merged together and just one list remains. Within this list, all of the data items will be sorted into the correct order

Question 13

• Bubble sort pros (3)

Answer 13

• Simple to write the code for.
  
  • Simple to understand.
  • The data is sorted in the same memory location that it is held, so you don’t need much extra memory to run the algorithm.

Question 14

• Bubble sort con (1)

Answer 14

• One of the slowest ways to sort a list. For example, if the list becomes ten times larger than before, it takes almost a hundred times longer to sort. So this method of sorting is very sensitive to the length of the list.

Question 15

• Merge sort pros (2)

Answer 15

• It is the fastest of three types of sort (bubble, insert, merge)
  
  • It is the best option to use for long lists of data (more than 1000 long)

Question 16

• Merge sort cons (2)

Answer 16

• More complicated to code compared to bubble and insert
  
  • It may use twice the memory size of the list - depending on the way it is coded. This becomes important if the list is millions of items long.

Question 17

Define sequence

Answer 17

• Sequence is the order in which programming statements are executed

Question 18

Define selection

Answer 18

• Selection is a programming construct where a section of code is run only if a condition is met.

Question 19

Define iteration

Answer 19

• Iteration is the repetition of a block of statements within a computer program.

Question 20

Iteration advantages

Answer 20

• Iteration allows programmers to simplify a program and make it more efficient . Instead of writing out the same lines of code again and again, a programmer can write a section of code once, and ask the program to execute the same line repeatedly until no longer needed.

Question 21

Nested selection is good because?

Answer 21

• Why nested selection is good: Nested selection can be built up over and over to include many possibilities and paths for a program to follow. It allows for complex decisions to be made.

Question 22

Variable - meaning?

Answer 22

• A variable is a named piece of memory that holds a value. The value held in a variable can - and usually does - change as the program is running.

Question 23

Why use meaningful identifier

W/ 2 adv

Answer 23

• MEANINGFUL IDENTIFIER: It is good practice in programming to give variables a sensible name that will help explain its purpose. - makes the algorithm easier to follow
• another programmer can better understand the code
• code easier to understand and debug/maintain

Question 24

Constant meaning

Answer 24

• A constant is a named piece of memory where the value cannot be changed while a program runs.

Question 25

Constant good why - explain

Answer 25

• Constants are useful because they are declared and assigned once, but can be referred to over and over again throughout the program. This means that if the programmer needs to change the value throughout the program code, they only need to make one change. This can help make a program easier to maintain.

Question 26

• Limitations of different data types (2)

Answer 26

• integers and real numbers cannot be concatenated, ie joined together.
  
  • numbers held in strings cannot be subject to mathematical operations.

Question 27

Array adv (2)

Answer 27

• An advantage of array is that a number of sorting, searching and updating functions can be applied to it. - also obviously its purpose is to store related data values under one identifier

Question 28

How records different to arrays? - mainly

Answer 28

• Records allow data values of different types that relate to each other to be stored together instead of in different arrays.

Question 29

4 facts- records vs arrays

Answer 29

• An array tends to have the same data type for every element, records often have mixed data type fields
  
  • The number of fields within a record is fixed once it is declared, they cannot be added to or deleted as the program runs.
  • A record declaration does not contain actual data - it is a template with which to create variables of that type.
  • Arrays can be used to store records with each element in the array of the same record type.

Question 30

• What do you need to remember when concatenating (2)

Answer 30

• same data type (string)

- you must manually add a space if you want it

Question 31

• Purpose of ‘import random’

Answer 31

• It imports the random library(/module) so that… (random integers can be generated)

Question 32

• Advantages of subroutines explained (3)

Answer 32

• Subroutines are usually small in size, which means they are much easier to write, test and debug. They are also easy for someone else to understand.
  
  • As they are written outside of the main program, subroutines can be saved separately as modules and used again in other programs. This saves time because the programmer can use code that has already been written, tested and debugged.
  • A subroutine may be used repeatedly at various points in the main program and changed by passing in data known as parameters. However, the code only has to be written once, resulting in shorter programs.

Question 33

Difference of 2 types of subroutines - in purpose

Answer 33

• Procedures perform a specific task but do not return a value.
  
  • Functions manipulate data and return a value to the main program.

Question 34

• Why use local variables (5) - explained

Answer 34

• 1. global variables waste memory
     - 2. variable names can be unique
     - 3. global variables can cause bugs
     - 4. local variables start as null each time
     - 5. global variables are hard to trace
     - declaring variables in a subroutine means that memory allocation is only needed while the subroutine is executing – if the variables were all declared globally, then unnecessary memory would be used whereas local variables are removed from memory once the subroutine has completed
     - local variables only need to be unique within the subroutine rather than throughout the whole program – this means that a programmer does not need to know the names of variables used within other subroutines
     - local variables cannot be changed by another subroutine which could interfere with the way a program work
     - when a subroutine is executed, all local variables are added to memory with no data so any previous data from a previous execution of a subroutine will not affect the result
     - ..because they can be manipulated by multiple subroutines

Question 35

• 3 types of test data - name and meaning

Answer 35

• normal data - typical, sensible data that the program should accept and be able to process
  
  • boundary data - valid data that falls at the boundary of any possible ranges, sometimes known as extreme data
  • erroneous data - data that the program cannot process and should not accept

Question 36

How to answer why an algorithm is more efficient

Answer 36

• why a algorithm is more efficient: The algorithm in [] uses fewer steps/instructions;

Question 37

9 adv of subroutines and the structured approach

• all explained

Answer 37

• Decomposition
  
  • Abstraction
  • Generalisation 

    Re-usable 
Easier to read code 
Debugging 
Maintenance 
Development teams 
Local variables
  • Using subroutines means that a top-down design can be naturally achieved because the main program forms the top of the tree with each subroutine being a branch of the tree. This means that each task within the top-down design can be tackled separately rather than trying to tackle the whole problem at once.
  • Abstraction hides unnecessary data. With subroutines, the detail of how each subroutine is removed from the main program meaning that only the identifier name of the subroutine needs to be used, plus any parameters.
  • Subroutines can be used for a variety of different situations. This generalises the subroutine so it is not just used once. For example, a subroutine that finds the average of all values in an array can be used for any array and not just a specific array within a program.
  • Subroutines can be used over and over again within a program and if they are within a module they can even be used in other programs. This saves having to repeat sections of code as the subroutine just needs to be called each time instead. 
It is easier to read the name of a subroutine than all the detail involved in how the subroutine works. This makes the code easier to follow.
  • Each subroutine can be tested on its own without being executed as part of the main program. This means that any bugs within the subroutine can be corrected before it is tested within the main program.
  • If code needs to be changed in the future, then it is easier to change the code within a subroutine rather than having to work through all the code.
  • It is possible for different people to write the code for each subroutine because each subroutine can exist separately.
  • All the advantages of local variables discussed on other flashcard