everything on the mock add plain English for algs tho

linear search big o

O(n)

binary search

O(log(n))

bubble sort

O(n²)

stacks

last in first out data structure

implemented as an array and use a single pointer to keep track of the top of the stack - points to the element currently at the top of the stack

top is initialised at -1

stack functions

size() - check size

isEmpty() - check if empty

peek() - return top element but dont remove it

push(data) - add data to the top of the stack

pop() - remove top element of the stack and return removed element

size()

return top+1

isEmpty()

if top < 0:

return true

else:

return false

peek()

if isEmpty():

return error

else:

return list[top]

push(data)

top+=1

list[top] = data

pop()

if isEmpty()

error

else:

top-=1

return list[top+1]

queues

first in first out

implemented as arrays

front and back pointers

front holds position of the first element

back stores the last element

either or ^^

queue functions

size

isEmpty

peek

enqueue(data)

dequeue()

size() queues

back+1

isEmpty() queues

if front>back

return true

else

return false

peek() queues

return items[front]

enqueue(data) queues

back+=1

list[back] = data

dequeue()

if is empty

return error

else:

front+=1

return list[front-1]

what is sequencing

code is executed line by line top to bottom

what is branching

a certain block of code is run if a specific condition is met using IF statements

this is also known as selection

what is iteration

a block of code is executed a certain number of times or while a condition is met.

FOR / WHILE / REPEAT UNTIL

count controlled

iteration is repeated a given number of times (hard coded)

condition controlled

iteration continues until a given condition is met ( used when it is unknown how many times code needs to be repeated )

what is recursion

recursion is when a subroutine calls itself during its execution

this continues until a certain condition is met called the stopping condition.

must move towards the base case

advantages of recursion

code can be written using fewer lines of code - less prone to errors

what happens when a recursive function is called?

many stack frames are created within the call stack where parameters, local variables, and return addresses are stored. this info allows the subroutine to return to that particular point during its execution.

a finite number of stack frames are created until the stopping condition or base case is reached at which point the subroutine unwinds. - information from the call stack being popped off the stack.

disadvantages of recursion

inefficient use of memory

danger of stack overflow - call stack runs out of memory

recursion is difficult to trace

what is scope

scope is the section of code in which a variable is available

variables can be defined with either global or local scope

local varaibles

can only be accessed within the block of code in which they were defined

why is using local variables good practice?

it ensures that subroutines are self contained with no danger of variables being affected by code outside the subroutine

what are global variables

they can be accessed across the whole program

this is useful for values that need to be used by multiple parts of the program.

why are global variables not recommended

they can be unintentionally overwritten and edited.

they require more memory than local variables as they are not deleted until the program terminates.

what happens if a local and global variables have the same name

the local variable takes precedence within the subroutine.

what is modular programming

a techniques used to split large, complex programs into smaller, self contained modules.

this is essential to making a problem easier to understand and approach

benefits of a modular design

makes it easier to divide tasks between a team and manage

testing is simplified as each component can be dealt with individually.

this allows for re usability of components

what is the top down approach / stepwise refinement

a problem is continually broken down into sub problems until each can be represented as an individual self contained blackbox which performs a certain task

this is also known as stepwise refinement

what can subroutines be classified as

functions or procedures

functions

must always return a value - can only return one value

procedures

do not have to return a value

can return multiple values

typically given data as parameters for manipulation

passing by value

a copy of the value is passed to the subroutine and discarded at the end. the values outside of the subroutine is not affected

in exam questions, assume passed by value

passing by reference

the address of the parameter is given to the subroutine so the value of the parameter will be updated at the given address

what is an IDE

an integrated development environment is a program which provides a set of tools to make it easier for programmers to write, develop and debug code.

what is stepping

allows you to monitor the effect of each individual line of code by executed a single line at a time

what is variable watch

used to pinpoint errors by observing how the contents of a variable change in real time through the execution of a program

what is breakpoint

users can set a point in the program at which the program will stop.

this can be based on a condition or set to occur at a specific line. this can help to pinpoint where an error is ocurring

what is a source code editor

the editor aims to make coding easier by providing features such as autocompletion, indentation, syntax highlighting and automatic bracket completion

what are debugging tools

some ides provide run time detection of errors with a guide as to where in the code they are likely to have occurred

Linear search

Binary search

Bubble sort

Insertion sort

what is abstraction

the process of separating ideas from reality - hiding unnecessary detail and showing details that are important in context

what is an example of abstraction? where is it used

icons. When designing software and interface, abstraction often uses symbols, legends, colour-coding and icons to accentuate real life feature

icons are a great example of abstraction they can be used to suggest a function or process in a simple, efficient way

what is the need for abstraction?

to remove some details and highlight others to improve clarity of what is trying to be conveyed

removal of less important things to highlight the more important things

think of an example of abstraction in file management

when saving a file, the details of where is it stored and how is the data represented is abstracted

the users only need to be able to create, open, move, save and delete files. they dont need to know how it all happens

how to abstraction

remove unimportant details, add in details, change details, highlight details

What do you need to determine when designing a new system

the inputs the system needs

the outputs the system should produce

first decide what your system needs to output - what is its goal

once you understand what your system does, backtrack and work out the inputs it will need to produce the desir

what are most systems designed to produce

an output

visual, audio, haptic feedback, data to be input into another process or system

what should you identify when writing a computer program

the inputs, processes and outputs of a problem

what is a precondition

conditions that already exist and could affect how a solution to a problem is created.

whenever trying to solve a problem, it is always good to ask if there are any preconditions that you must take into consideration.

What is caching

an example of thinking ahead in computer architecture

instruction/data retrieved from secondary storage and placed into main memory often remain there in case they are needed again. resulting in much faster retrieval times as they don’t need to be fetched from secondary storage which is much slower compared to primary storage

what is prefetching

prefetching involves data being requested from main memory by the processor before it is actually needed

for prefetching to work, algorithms need to be designed to predict that an instruction or piece of data will be required soon.

a good example of this is taking your wallet out before paying to reduce time spent at checkout

bubble sort in english

Bubble sort repeatedly steps through a list, comparing adjacent elements and swapping them if they are in the wrong order.
Each pass moves the largest unsorted value to its correct position at the end of the list.
The process continues until no swaps are needed, meaning the list is sorted.

insertion sort in english

Insertion sort builds a sorted list one item at a time.
Each new element is taken and inserted into its correct position within the already sorted part of the list.
Elements greater than the current value are shifted to the right to make space for the insertion.

binary search in english

Binary search works on a sorted list by repeatedly dividing the search interval in half.
The middle value is compared to the target value.
If the target is smaller, the search continues in the left half; if larger, in the right half.
This process repeats until the value is found or the search space is empty.

linear search in english

A linear search checks each item in a list one at a time, starting from the beginning, until the required value is found or the end of the list is reached.
It does not require the list to be sorted.
If the item is found, its position is returned; otherwise, the search reports that the item is not in the list.

thinking concurrently

working out which parts of a program can be developed to take place at the same time / which parts are dependant on each other therefore cannot do at the same time.

concurrency

advancing tasks at the same time

e.g. 5 push ups 10k run

1 push up, 5k run, 4 pushups, 5k run

parallelism

advancing tasks at the same exact moments.

e.g 5 push ups, 10k run

cant run and pushup at the same time therefore its concurrent

so youd need another core

one does 5 push ups, one does 10k run

concurrent processing benefits

user can interact with applications while tasks are running in the background

a long running task wont delay short running ones

allows for parallelism

NUMBER OF TASKS COMPLETED IN A GIVEN TIME IS INCREASED

LESS TIME WASTED ON WAITING FOR USER / PROCESS IS REDUCED.

concurrent processing disadvantages

possibility of corrupting the consistent state of a program

tasks can suspend and wait on each other indefinitely - deadlock

threads can consume resources - harming scheduling, context switching, synchronisation