1 - Fundamentals of Algorithms

What is an algorithm?

An algorithm is a sequence of steps that can be followed to complete a task - it follows a precise set of rules to solve a problem

How do computer programs use algorithms?

A computer program is an implementation of an algorithm - an algorithm is NOT a computer program

What is decomposition?

Breaking a problem down into a number of smaller manageable sub problems, so that each sub problem accomplishes and identifiable task, which might itself be further subdivided

What are some advantages of decomposition?

The problem is easier to solve, and each small problem (module) can be reused and tested independently in other programs, saving development times

What is abstraction?

Its the process of removing unnecessary detail from a problem to focus on important features

How do u use a systematic approach to solve problems?

A systematic approach means being able to take a logical approach and use algorithmic thinking to solve a problem

What are some ways to represent algorithms?

Through Pseudocode, Flowcharts and Program Code

What is pseudocode?

It is a structured, text based tool using English to describe an algorithm, allowing the designer to focus on the logic of an algorithm without being distracted by syntax

How do you output something in pseudocode

OUTPUT ("Please enter your age")

How do you get an input in pseudocode or assign values to variables ?

age <- USERINPUT or INPUT() or 1 + 2 etc

What are different programming constructs in pseudocode?

Sequence, selection and iteration

What is the sequence programming construct in pseudocode?

Statements are executed in the order they are written

Give an example of a sequence in pseudocode

mealCost <- 4.00 | drinkCost <- 2.00 | total <- mealCost + drinkCost

What is the selection programming construct in pseudocode?

An IF statement - the next statement to be executed depends on whether the condition being tested is true or false

Give an example of a selection in pseudocode

age <- USERINPUT | IF age < 10 THEN | OUTPUT "Good" | ELSE "Too old" | ENDIF

What is the iteration programming construct in pseudocode?

It means repetition - uses statements such as FOR…ENDFOR, WHILE…ENDWHILE, REPEAT…UNTIL

Give an example of a FOR loop

FOR i <- 1 to 10 | (process to be carried out) | ENDFOR

When do you use a WHILE…ENDWHILE command?

When you want to execute a loop while a certain condition is true - the condition is tested at the beginning of the loop

Give an example of a WHILE loop

WHILE age = 10 | … | ENDWHILE

When do you use a REPEAT…UNTIL loop?

When you want to execute a loop UNTIL a certain condition is true - the condition isn't tested until the end of the loop (so you need an IF statement as well)

What is a flowchart?

They are a visual tool that uses shapes to represent different functions to describe an algorithm - they show the input and output data, the processes that take place and any decisions or repetition, with lines to show the flow of control

What does an oval in flowcharts mean?

Terminator symbols - the start or end

What does a rectangle in flowcharts mean?

A process, such as a calculation or assignment - eg number = 5

What does a parallelogram in flowcharts mean?

An input or output

What does a rhombus in flowcharts mean?

A decision - eg is count = 10? (yes or no)

What can algorithms be broken into?

3 main sections - inputs, processes and outputs

What is an input in algorithms?

Data or information being entered and taken into a program before it is processed - can come from users (keyboards, mouse, mic) or sensors (temp, pressure) or js typed in

What is a process in algorithms?

A doing action performed in the algorithm that transforms inputs and processes them into the desired output - eg comparing 2 numbers, calculating an average

What is an output in algorithms?

The result of the processing in an algorithm - usually the way a user can see if an algorithm works as intended - they can come as numbers, texts, images or actions etc

Give an example of a pseudocode algorithm, identifying the inputs, processes and outputs

Input: OUTPUT ("Enter number") | number <- USERINPUT | Process: IF number MOD 2 = 0 | Output: OUTPUT ("Number is even") ELSE OUTPUT ("Number is odd") | ENDIF

How can you determine the purpose of a simple algorithm?

By using a trace table and visual inspection to see how they work

What are trace tables used for?

To trace through an algorithm to test it for logic errors, find the output or determine its purpose

How do trace tables work?

They trace through an algorithm and test them for logic error that appears when it's executed - each stage of the algorithm is executed step by step, and inputs + outputs + variables can be checked for values and to find the purpose + errors

How do you draw a trace table?

Make a column for each variable used in the order they appear

How can a many algorithms be used to solve the same problem

For example, a linear and binary search - 2 different algorithms but both have the same function to find a value in a list, but one might be faster depending on circumstances

How would you compare the efficiency of algorithms?

Compare the time efficiency - how long it takes to complete an algorithm

What is a searching algorithm?

A set of instructions for finding a specific item of data within a data set - there are 2 types, linear and binary

What is a Linear Search?

Used on unsorted lists - starts with the first value in the dataset and checks every value once until you find it

How do you perform a linear search?

Check the first value - if its the value your looking for, stop, otherwise move on and check again - repeat until you checked all the values and found the value youre looking for

What are the advantages of linear search?

It works on unsorted data, faster on small datasets and simple to understand + implement

What are the disadvantages of linear search?

Slow for large dataset and inefficient as it starts at the beginning each time

What is a Binary Search?

Works on an ordered set to quickly find a value - the list is halved each time and compares the target value with the middle value, going left if smaller, right if bigger, until the value is find

How do you perform a binary search?

Identify the middle value, compare it to the value your looking for - if it is stop, else if its bigger, go to the left and repeat, if its smaller, go to the right and repeat (comparing it with the middle value)

What is the maximum amount of numbers you need to look at in binary search, based on a list of 2^n items?

n+1 ‎ = eg if theres 16 items (2^4) there will be n (4) + 1 = 5 numbers to look at (round down if the number isn't square

What are the advantages of binary search?

Fast for large datasets and efficient for repeated searches

What are the disadvantages of binary search?

Dataset must be in order, and its more complex to implement

What is a sorting algorithm?

Precise step by step instructions that a computer can follow to efficiently sort data in big datasets - can be bubble or merge sort

What is merge sort?

A sorting algorithm that divides a dataset into smaller sub datasets and merging them back in the correct order

How does merge sort work?

Divide unsorted data set repeatedly in half into individual datasets - merge pairs of these subsets by comparing the first values and ordering them - reoeat until all subsets are merged into 1 sorted list

What is bubble sort?

Its a simple sorting algorithm, starting at the beginning of a dataset and checking values in pairs, swapping them to sort them

What is a pass?

1 full run of comparisons from beginning to end, looking through each unsorted item in the list, leaving the largest item at the end

How does bubble sort work?

Compare the first 2 - if theyre in the worng order, swap them - compare the next 2 and repeat till you reach the end - repeat from the start (multiple passes) till you cant make any more swaps - this is a sorted list

What are some advantages of merge sort?

Its quicker and more efficient and perfomrs well no matter how unorganised data is

What are some disadvantages of merge sort?

Require more memory to store sublkists, and is more complex to implement

What are some advantages of bubble sort?

Simple and efficient - easily implemented + doenst use much memory as sorting is done to the original list

What are some disadvantages of bubble sort?

Slow and inefficient for large datasets, as it iterates through the data multiple times