Computing: Unit 1-Fundamentals of Algorithms

What is efficiency?

We are considering time and storage space.
-The London tube map is an example like the distance between the stations or landmarks

What is a sequence?

In computer programming, this is a set of instructions that are executed one after another

What is a selection?

A decision within a computer program when the program decides to move on based on the results of an event.
-An IF statement is a selection statement. Selection works by testing a condition. The test gives a Boolean result - TRUE or FALSE

What is iteration?

The repetition of a block of statements within a computer program. There are 3 types of iteration statements:
-REPEAT-UNTIL LOOPS
-WHILE LOOPS
-WHILE...ENDWHILE

What are the pros and cons of a merge sort?

Pros and cons of merge sort:
Pros: A very efficient algorithm.
Cons: Can be slower for small lists. Needs additional memory.

What is an algorithm?

A set/sequence of instructions for solving a problem or completing a task

What is algorithm thinking?

Algorithmic thinking is a way of solving problems by producing algorithms.

What are two ways to represent algorithms?

•pseudocode
•flow charts

What is pseudocode?

Pseudocode is a common way of representing an algorithm.
-It is a way to write out algorithms using code-like statements.
-It is intended to be very readable, and easy to understand.

What is the purpose of pseudocode?

•Pseudocode is not an actual programming language
•Pseudocode is used to plan algorithms, focusing on the logic and steps rather than language-specific syntax.

How can pseudocode be run on the computer?

It can not be run on the computer

What are identifiers?

•Identifiers are the names of variables, constants, and subroutines.
•These often give strong clues about the purpose of an algorithm.

What are some hints for identifying algorithms?

They include:
•Check comments
•Check identifiers
•Check inputs
•Check outputs

What happens if a line of code is forgotten?

Sometimes a line of code has been forgotten, which can lead to issues such as infinite loops, where the code will never end.

What is abstraction?

Removing unnecessary information in a problem so that you can focus on the essentials. ---> Examples include maps as they leave out many details in order to focus on the important information, such as roads and landmarks.

What is decomposition?

Splitting/breaking down a large problem into smaller sub-problems
-Then the sub-problems can be broken down further until they're manageable

What are some advantages of decomposition? What can you use to visualise it?

-Decomposition allows large teams to each take a part of a problem and work on it.
-Decomposition allows seemingly impossible problems to be solved by splitting them into simple tasks.

•Structure charts are used to visually represent breaking a large problem down into the smaller parts that make it up.
-Each box represents a smaller problem to be solved.
-Lines show which bigger problem the box is a part of.

+

Addition

-

Subtraction

*

Multiplication

/

Division

DIV

Integer division(quotient)
e.g. 20 DIV 3 = 6

MOD or %

Remainder (modulus)
e.g. 20 MOD 3 = 2

What is 2 + 8 * 2

18
Computers follow the rule of BODMAS
(brackets, other, division, multiplication, addition, subtraction)

What is a variable?

A location in memory in which you can temporarily store text or numbers

What are flow diagrams/ charts and why are they used?

•Flow diagrams are used to represent a given algorithm.
•Flow diagrams are used to visually represent the steps that make up an algorithm.
•A standard set of shapes are used to represent different types of step.
•Arrows represent the flow of control, or what to execute next.

Flowcharts: Start/ stop

The beginning and end of the algorithm are put in ovals

Fc: Inputs/ Outputs

An input is data received by a computer. An output is a signal or data sent from a computer and it goes in a parallelogram box

Fc: Processes

An instruction, command or calculation which goes in rectangular boxes

Fc: Decision

A decision, either a 'yes' or 'no' question, are put in diamond boxes
•A decision has two labelled arrows coming out of it.The 'Yes' arrow is followed if the condition in the diamond was true, otherwise the 'No' arrow is followed.

Fc: Subroutine

Subroutines are references to other flowcharts

Fc: Arrows

They connect the symbols and they show the direction of flow of instructions

INT

Integer- whole numbers only
Typical amount of memory taken up: 2 bytes or 4 bytes

REAL

Real(or float)- Numbers that have a decimal part
Typical amount of memory taken up: 4 bytes or 8 bytes

BOOL

Boolean- can only take one or two values, usually TRUE or FALSE
e.g. true/ false
1/0
yes/ no
Typical amount of memory taken up: 1 bit is needed but 1 byte is usually used

CHAR

Character- a single letter, number, symbol
Typical amount of memory taken up: 1 byte

STRING

String-used to represent text, it's a collection of characters
e.g. 'FsTmQ2'
'$money$'
Typical amount of memory taken up: 1 byte for every character in the string

Is equal to

=(or == in python)

Is not equal to

≠(or <> or != in python)

Is less than

<

Is greater than

>

Is less than or equal to

≤(or <= in python)

Is greater than or equal to

≥(or >= in python)

What is the difference between IF, ELIF and nested If statements?

-In an elif statement if the condition is met it ignores the rest
-In an if statement, it executes the whole programme. It checks if a condition is true or false, and carries out different actions depending on the outcome, so it is not efficient
-Nested IF statements allow you to check more conditions once you've established that the previous condition is true or false

What does a REPEAT-UNTIL loop do?

-Controlled by a condition at the end of the loop
-Keep going until the condition is true
-You get an infinite loop if the condition is never true
-The condition is not tested until the end of the loop(it's always executed at least once), so you need an IF statement as well as the Repeat loop

What does a WHILE LOOP do?

-Controlled by a condition at the start of the loop
-Keep going while the condition is true, until it is false
-It never runs the code inside them if the condition is initially false
-You get an infinite loop if the condition is always true
-It is a condition control loop

What does a DO-WHILE LOOP do?

-Python does not have this loop
-Controlled by a condition at the end of the loop
-Keep going while the condition is true, until it is false
-Always run the code inside them at least once
-You get an infinite loop if the condition is always true

What does a FOR LOOP do?

-For loop is a count control loop
-You use it when you want
-They repeat the code inside them a fixed number of times. The number of times that the code repeats will depend on an initial value, end value and sometimes a step count to execute the loop a specified number of times

What are search algorithms?

A search algorithm is a set of instructions for finding a specific item of data within a data set.
-Computer systems can store and process billions of pieces of data so it is vital that computers can find the information they need efficiently.

What is a linear search?

-This is a simple algorithm used to find a value in a list of d

The algorithm runs as follows:
•Identify a search term.
•Look at the first item in the list.
•Compare the item with the search term.
•Is the current item the same as the search term? If so, the item has been found. If not, move to the next item.
•Repeat from step two until the last item in the list has been reached.
•If the end of the list has been reached and the search term has not been found, then the search term is not in the list and the algorithm can stop.

What is a binary search?

-This is a more complex algorithm than linear search and requires all items to be in order.

The algorithm runs as follows:
•Start by setting the counter to the middle position in the list.
•If the value held there is a match, the search ends.
•If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.
•Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
•The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.

What's a disadvantage and advantage of a binary search?

•The main disadvantage of binary search is that the data set must be sorted before starting the algorithm

•An advantage is that it is efficient

What is an efficient sort algorithm?

An efficient sort algorithm is one which can sort a dataset in a short time.

What is a bubble sort?

-This is a simple algorithm used for taking a list of unordered numbers and putting them into the correct order.

The algorithm runs as follows:
•Look at the first number in the list.
•Compare the current number with the next number.
•Is the next number smaller than the current number? If so, swap the two numbers around. If not, do not swap.
•Move to the next number along in the list and make this the current number.
•Repeat from step 2 until the last number in the list has been reached.
•If any numbers were swapped, repeat again from step 1.
•If the end of the list is reached without any swaps being made, then the list is ordered and the algorithm can stop.

What are 2 advantages of bubble sort?

Advantages of bubble sort:
•Does not use much memory
•Easy to implement

What is a merge sort?

-This is a more complex algorithm than bubble sort, but can be more efficient.
The merge sort algorithm repeatedly divides a list into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined. The process is then repeated until the list is recompiled as a whole.
•This algorithm is used to sort an unsorted list

-The list is split into half:
-The process repeats
-Until all elements are individually separated:
-The algorithm looks at the individual elements and compares them as pairs.
-Each pair is sorted into order
-The pairs are then compared, starting with the first number in each pair. If the left hand number is smaller than the right hand number, it is placed in order. The comparison then moves up to the second number on the left hand side and the process repeats. If the right hand number is smaller, it is placed in order and the comparison moves to the next number on that side.

When is it a particularly bad idea to use merge sort?

• On a small list which is unlikely to grow