1 - Fundamentals of Algorithms

Question 1

What is an algorithm

Answer 1

A series of instructions that describes how to solve a specific problem or perform a specific task

Question 2

What is decomposition

Answer 2

Breaking down a problem down into smaller ‘sub-problems’

Question 3

Advantages of decomposition

Answer 3

• Smaller problems are easier to solve than larger problems
• Each ‘sub-problem’ can be developed separately, making planning and working to a timescale easier
• ‘Sub-problems’ are easier to distribute among a team than one large problem

Question 4

Inputs, Initialisation, processing, outputs

Answer 4

Inputs - what data enters the system and how?
Initialisation - What variables are needed and what are their initial values?
Processing - What processes (calculations, sorts, etc.) are carried out on the inputs?
Outputs - What data leaves the system and in what format?

Question 5

Abstraction

Answer 5

Hiding the layers of complexity within a system, in order to focus on one specific layer of complexity

Question 6

Common methods of defining algorithms

Answer 6

• Pseudocode

- Flowcharts

Question 7

Pseudocode

Answer 7

A cross between English and a generic-looking programming language. While pseudocode would not compile, a competent programmer could convert it to code that would compile

Question 8

Flow Chart

Answer 8

A means of defining an algorithm using shapes and arrows. Within each shape, an action is taking place or a decision is being made. The direction of arrows indicates which action or decision comes next

Flow charts are easier understood than pseudocode to someone who is not a programmer

Question 9

Oval

Answer 9

This is the terminator. One is used to mark the start and another is used to mark the end. They are not used elsewhere

Question 10

Arrow

Answer 10

Shows which instruction should take place next

Question 11

Diamond

Answer 11

A decision. It asks a question and each arrow leaving must have a possible answer

Question 12

Square/ rectangle

Answer 12

This is a process. Each one contains a single instruction. so complex tasks usually incorporate several processes

Question 13

Parallelogram

Answer 13

This shape represents data that is entered into the system or output from it. Basically input or output

Question 14

Sequence

Answer 14

A sequence is when instructions in an algorithm each need to be executed only once, and in the order in which they are written

Question 15

Selection

Answer 15

Selection is when one sequence of instructions or another, but not both, is executed. The sequence that is executed will depend on what happened in earlier instructions.

Question 16

Iteration

Answer 16

Iteration takes place when one or more instructions are executed more than once. Iteration is also known as repetition. Iteration is taking place when a program code (or pseudocode) contains the words LOOP, FOR, WHILE, or REPEAT.

Question 17

Trace tables

Answer 17

Interpreting an algorithm works best when you do so one line at a time, as a computer would. A trace table can and should be used to keep track of variables that change throughout the algorithm.

Question 18

Efficiency

Answer 18

A measure to compare two different algorithms that solve the same problem. A more efficient algorithm is a better choice. Efficiency can be measured in a number of different ways, the main type is TIME efficiency. An algorithm that can be executed in 20 instructions is more efficient than one that takes 30 instructions

Question 19

Searching

Answer 19

Determining whether a specific piece of data exists within a data structure. If it does exist, a search algorithm will reveal its location

Question 20

Linear search

Answer 20

A search algorithm that begins at one end of a data structure, checking each data item in turn until the required item is found, or the end of the structure is reached

Question 21

Binary search

Answer 21

A search algorithm that begins in the middle of a data structure, eliminating half of the remaining data with each pass. Binary searches are only appropriate when performed upon a sorted data structure. (Meaning that data is already ordered)

Question 22

Comparing searches

Answer 22

A binary search is more efficient that a linear search since it will, on average, find a search term more quickly than a linear search. However, binary searches do not work on unsorted data, so efficiency is not the only consideration

Question 23

Sorting

Answer 23

Putting data into order, whether that be numerical order, alphabetical order or chronological order, ascending (A-Z) or descending (Z-A)

Question 24

Bubble sort

Answer 24

Passes through the data, and swaps data that are not ascending
Keeps passing through until one lass pass proves that the data is sorted

A bubble sort only ends when a complete pass has yielded no changes or when n-1 (n being the number of elements to be sorted) passes have taken place

Question 25

Merge sort

Answer 25

Unsorted data is split into individual units
Then paired with the smaller number first
Then merged into 4’s in ascending order
Keeps merging until the whole data set is merged in ascending order

Question 26

Bubble sort vs Merge sort

Answer 26

Bubble sort:
Adv
- Straightforward to program
- Does not use much extra memory space while the sort is in progress
Dis
- Can take a very long time with a large set of data to sort

Merge sort
Adv
- More efficient in terms of time
Dis
- More complex to program
- Requires lots of memory space as it runs