Unit 4 (teachers notes)

Question 1

Sequential/ linear search:

Answer 1

Sequential/ linear search: Usual search, go through every value and compare to the target value.
Simple to implement, data doesn’t need to be in order. Inefficient with large number of elements,may have to go through every single one of them.

Question 2

collections:

Answer 2

Collection: Group of objects. No assumptions are made about the order of the collection (if any) or whether it can contain duplicate elements. We add and retrieve data from them.

Question 3

Suitability of an algorithm

Answer 3

Suitability of an algorithm
Efficiency: Amount of computer resources required to perform algorithm’s functions
Correctness: Extent to which algorithm satisfies specification
Reliability: Capability to maintain performance
Flexibility: Effort required to modify algorithm for other purposes

Big O notation: Measure of efficiency of an algorithm.
O(1) – efficiency and speed are always the same, time proportional to 1. e.g. addFront, algorithm
that adds up fixed no. of values etc.
O(n) – time and efficiency proportional to n. e.g. linear search method (proportional to length of array, longer array = longer time searching, loop to non-constant value etc.)
O(n2) – proportional to n2. Time required increases rapidly if n increases e.g. nested loops in bubble sort and select sort

Question 4

Big O notation: Measure of efficiency of an algorithm.

Answer 4

Big O notation: Measure of efficiency of an algorithm.
O(1) – efficiency and speed are always the same, time proportional to 1. e.g. addFront, algorithm
that adds up fixed no. of values etc.
O(n) – time and efficiency proportional to n. e.g. linear search method (proportional to length of array, longer array = longer time searching, loop to non-constant value etc.)
O(n2) – proportional to n2. Time required increases rapidly if n increases e.g. nested loops in bubble sort and select sort

Question 5

Pseudo cide, mod and div

Answer 5

Pseudo code
mod (returns remainder e.g. 15 mod 7 = 1),
div (how many times number fits e.g. 15 div 7 = 2)

Question 6

Programming languages

Answer 6

Programming languages
Machine language: Low-level language directly understood by computer, made up of binary numbers.
Assembly language: Low-level language using symbols for instructions and memory addresses
High-level programming language: Uses elements of natural language. Easy to use for humans and more understandable. Abstracts some areas of computing systems, would otherwise take too long to write our systems in machine code.

Question 7

Programming languages need to have…

Answer 7

Programming languages need to have…
  Fixed vocabulary- Instructions for operations do not change. e.g. “print” will always print
  Unambiguous meaning- Clear instructions
  Consistent grammar and syntax- The way we declare and use language features must be the same.
  Provide a way to define basic data types and operations on those types- ability to write functions/procedures
  It has to run on/be able to be processed by a computer- it must have a compiler/interpreter

Question 8

Higher level programming languages can differ by…

Answer 8

Higher level programming languages can differ by…
  Method of translation- Whether by compiler or interpreter (or both)
  Different programming paradigms- e.g. procedural or object-oriented
  Purpose of the language- Specific for certain tasks (e.g. CSS for HTML websites or language for AI) or general purpose (can build any program with any logic e.g. Python)
  Compatibility with different environments- e.g. Java with virtual machine can run on all OS while some languages can’t
  Syntax differences- e.g. structure of statements

Question 9

Source code:

Answer 9

Source code: Original code/program developed using high level language. Needs to be translated

Question 10

Object/Target program:

Answer 10

Object/ target program: Program translated into machine language.

Question 11

translation methods:

Answer 11

Translation methods:
  Compiler: Executes translation process only once, translates the whole program. Object program is saved so it doesn’t need to be compiled again. All errors are displayed when the whole program is checked, compilation ends only once errors are fixed. Example: C++
  Interpreter: Reads, translates and executes program line by line. Errors are displayed after each line is interpreted. Goes through the process every time the program is run, much slower than a compiler. Example: BASIC

Question 12

Writing code
Variable
Constant
Object

Answer 12

Writing code
Variable: Used to store a data element that can be changed during program execution. Has an identifier and type.
Constant: Elements and quantities that don’t change. e.g. final double PI = 3.14
Object: Comprised of data and methods (operations that can be performed by the object)

Question 13

Thinking procedurally

Sub-procedure:

Answer 13

This includes identifying the steps and putting them in the correct order e.g. recipes
Sub-procedure: A section of code in a program that does a specific job. Can be called by name when needed without naming the details as these are wrapped in the procedure. It is therefore an example of abstraction.

Question 14

Thinking logically
Thinking ahead
Gantt Charts:

Answer 14

Thinking logically
Different actions are taken based on conditions, taking alternative procedures into account. Need to identify conditions associated with a given decision (like an IF statement

Thinking ahead
Need to identify inputs and outputs required in solution before carrying it out. e.g. cooking- need to identify the different ingredients.

Gantt Charts:
Outlining tasks, how long they will take to carry out, and when they are carried out. Can identify and show what tasks can be carried out concurrently.
Allows easy inspection and overlapping tasks, durations etc.

Question 15

Pre-planning
Prefetching/ caching:
Pre-condition:
Post-condition:

Answer 15

Pre-planning
Prefetching/ caching: Building libraries of pre-formed elements for future use, e.g. using Java libraries to increase efficiency, making sure you have your most commonly used spices ready at the front of your cupboard for cooking etc.
Pre-condition: Starting state before algorithm is executed, conditions that need to be fulfilled. E.g. have to have the required ingredients, a place to cook
Post-condition: Final state after execution of algorithm, the state you are trying to achieve/ lead up to, the final result.
Will need to also consider exceptions when building pre-conditions, e.g. identifying conditions for calculating end of year bonus when not all employees have worked for the company for the whole year.

Question 16

Thinking abstractly

Thinking concurrently:

Answer 16

Thinking concurrently
Concurrent processing: Implementing parts of a solution at the same time e.g. assembly line mass production- people carrying out a task on one product then moving on to the next one while the next person carries out another task at the same time.
In computers: Execution of different instructions simultaneously by multiple processors. Each processor processes different parts of a program’s procedures and sub-procedures. Needs better planning that accounts for different people working on the solution at the same time due to the changes they make, e.g. database should only be accessed once edit has been made
otherwise the person wouldn’t know someone else has erased their changes

Thinking abstractly
Selecting the pieces of information that are relevant to solving the problem and leaving out other information, to enable the ability to examine a solution at a human level of interaction. Considering something as its relevant characteristics and qualities, separated from concrete realities, actual
objects or instances.
E.g. Map of London only showing roads and names, not the buildings because purpose is navigation along roads for cars
Subway map showing simplified route as user is only interested in the order of stops
Virtual reality games having smaller time scale and providing icons of items in inventories
City simulation for pilots not having details like people or windows on buildings, just landmarks and the shape and height of buildings
An object in OOP is an example of abstraction because it hides the details of the code while preserving functionality