Paper 1

• Decomposition = breaking a complex problem down into smaller sub-problems and solving each one individually
• Abstraction = picking out the important bits of information from the problem, ignoring the specific details that do not matter
• Algorithmic thinking = a logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solve similar problems in the future
• Algorithm = an unambiguous sequence of steps that can be followed to have a specific outcome
• Algorithms can be written in PSEUDOCODE

  1. Pseudo code is not an actual programming language but it should follow a similar structure and read like one. The idea is that pseudo code clearly shows an algorithms steps
  2. It is quick to write and can be easily converted into any programming language
  3. There are different ways to write pseudo code - they are all equally correct as long as the person reading the code can follow it and understands what it means
• BINARY SEARCH ALGORITHM

  1. Find the middle item in the ordered list
  2. If this is the item you’re looking for, then stop the search
  3. If not, compare the item you’re looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item, get rid of the first half of the list
  4. You'll be left with a list that is half the size of the original list. Repeat these steps on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for
• LINEAR SEARCH ALGORITHM

  1. Look at the first item in the unordered list
  2. If this is the item you’re looking for, then stop the search - you’ve found it
  3. If not, then look at the next item in the list
  4. Repeat these steps until you fin the item that you’re looking for or you’ve checked every item
• LINEAR SEARCH VS BINARY SEARCH

  1. A linear search is much simpler than a binary search but not as efficient. The biggest advantage of a linear search is that it can be used on any type of list, it doesn’t have to be ordered
  2. For small ordered lists the difference in efficiency doesn’t really matter so the run time of both algorithms will be similar
  3. For large ordered lists, the run time of binary search will generally be much quicker than linear search
• BUBBLE SORT ALGORITHM

  1. Look at the first two items in the list
  2. If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them
  3. Move into the next pair of items and repeat
  4. Repeat this until you get to the end of the list - this is called one pass. The last item will now be in the correct place, so you don’t include it in the next pass
  5. Repeat until there are no swaps in a pass
• BUBBLE SORT - ADVANTAGES

  • Its a simple algorithm that can be easily implemented on a computer
  • Its an efficient way to check if a list is already in order
  • Doesn't use very much memory as all the sorting is done using the original list
• BUBBLE SORT - DISADVANTAGES

  • Its an inefficient way to sort a list
  • Due to being inefficient, the bubble sort algorithm is pretty slow for very large lists of items
• Operators are special characters that perform certain functions
• Many programming languages use “=“ for the assignment operator and “==“ for the comparison operator
• Data values can be CONSTANTS or VARIABLES:

  • the name of the constant or variable is linked to a memory location that stored the data value.
  • A constant is assigned a value at design time that cannot be changed. If you attempt to change the value of a constant in a program then the interpreter or complier will return an error
  • Variables on the other hand can change value which makes them for more useful than constants
  • To make code easier to follow, programmers usually give variables and constants descriptive names. They will also follow standard naming conventions when naming variables
• Strings can be joined together to form new strings - this is called concatenation
• LEN(string)

  —> returns the number of characters in the string
• string[x:y]

  —> extracts a substring from the original string, starting at position x, up to but not including position y
• REPEAT-UNTIL LOOPS

  • controlled by a condition at the end of the loop
  • keep going until the condition is true
  • always run the code inside them at least once
  • you get an infinite loop if the condition is never true
• WHILE LOOPS

  • controlled by a condition at the start of the loop
  • keep going while the condition is true
  • never run the code inside them if the condition is initially false
  • You get an infinite loop if the condition is always true
• DO-WHILE LOOPS

  • controlled by a condition at the end of the loop
  • keep going while the condition is true
  • always run the code inside them at least once
  • you get an infinite loop if the condition is always true
• ARRAYS

  • an array is a data structure that can store a group of data values, of the same type, under one name
  • each piece of data in an array is called an element - each element can be accessed using its position (or index) in the array
  • arrays are most helpful when you have lots of related data that you want to store and it doesn’t make sense to use seperate variables
  • just like variables, some languages require you to declare arrays before you use them
• RECORDS CAN CONTAIN DIFFERENT DATA TYPES

  • a record is a type of data structure which means that it is used to store a collection of data values
  • one of the things that makes records so useful is that, unlike arrays, they can store values with different data types
  • each item in a record is called a field, and each field is given a data type and a field name when the record is created
  • records are fixed in length, which means that you can’t add extra fields to them once they’ve been created
• SUBROUTINES HELP TO AVOID REPEATING CODE

  • Subroutines are sets of instructions stored under one name
  • Subroutines can be either functions of procedures - the main difference is that functions always return a value and procedures do not
  • Subroutines are very useful when you have sets of instructions that you need to repeat in different places within a program. They give your program more structure and readability whilst cutting down on the amount of code
  • In most subroutines you’ll encounter parameters
• VARIABLES CAN BE LOCAL OR GLOBAL

  • all variables have a scope
  • local variables = can only be used within the structure they’re declared in
  • global variables = can be used any time after their declaration
  • variables declared inside a subroutine are local variables. They are invisible to the rest of the program
  • the advantage of local variables is that their scope only extends to the subroutine
  • variables in the main body of a program can be made into global variables - these can be used anywhere in the code, it can be difficult to keep track of the value of global variables in larger programs
• STRUCTURED PROGRAMMING MAKES CODING MUCH EASIER

  • Structured programming involves decomposing the program that you want to write into manageable modules. Each of those modules is then decomposes even further into smaller modules and eventually into modules that perform individual tasks
  • Simple subroutines can be written to carry out each individual task. Then the bigger modules and main program can be written using these subroutines
  • It’s important to clearly document the interface of each module. This means listing the modules name, any inputs, processes and the output/return value
• AUTHENTICATION CAN HELP PROTECT YOUR PROGRAMS

  • Authentication can confirm the identity of a user before they’re allowed to access certain pieces of data or features of the program
  • Here are some common ways to increase the security of a password-based authentication system:

  - force users to use strong passwords and change password regularly

  - limit the number of of failed authentication attempts before access to an account is lost

  - ask for a random selection of characters from the password on each authentication

  • it’s important to get the level of authentication correct
• input validation = checking if data meets certain criteria before passing it into the program
• Logic errors = when the complier or interpreter is able to run the program, but the program does not work as intended
• A TEST PLAN SHOULD BE MADE BEFORE IMPLEMENTATION

  • a test plan will outline exactly what you’re going to test and how you’re going to test it. It should cover all the possible paths through a program
  • a food test plan will anticipate potential issues with the program and select appropriate test data to test for these issues
• TYPES OF TEST DATA

  • Normal data - valid data that a user is likely to input into the program
  • Boundary data - valid or invalid data on either side of the boundary of what the program should accept
  • Erroneous data - invalid data that the program should not accept
• • Trace tables give a simple way of testing that a piece of code is working correctly. They keep track of the values that certain variables take as you go through the code
  • Their main use is to ‘dry run’ a subroutine or algorithm to make sure there are no logic errors - they can also be used to help you figure out what a piece of code is actually doing