Unit 2

copy of a variable which is passed to a subroutine. Value of parameter only changes within the subroutine, doesn’t affect variable outside

• linked list is a dynamic data structure, array is static

• In an array any element can be accessed directly -linked list needs to be traversed until element is found

  
  

Constant

Algorithm will take same amount of time no matter its size.

Tell via no loop

Linear

Algorithm performance grows in linear time.

Tell via iteration e.g. for or while loop

Polynomial

Algorithm performance related to square of data size.

tell via two nested loops.

Exponential

Algorithm were time taken to execute doubles for each item added.

e.g. recursion

Logarithmic

Time taken grows very slow as data set size increases.

e.g. Binary search.

Usually tell through data halving

• a dynamic data structure

• each node consists of data and a pointer

• pointer provides location of next node

• Easier to debug

• Each area can be tested before integrating

• Code can be reused

• People can work in their expertise

• Save time

Depth first:

Depth first goes to left child node. If no left child node goes to right child node.

When no child nodes left algorithm backtracks to parent node.

Uses stack structure

Breadth first:

Visits all nodes connected to start node

Then all nodes connected to each of those nodes and so on

Uses queue structure

When a node doesn’t have any nodes to visit

Algorithm goes back to previous visited node to check for further nodes

when a subroutine calls itself from within itself

• needs a finite stopping condition

storing instructions/data after theyve been used as may be used again. Saves time as don’t have to go back to secondary storage to retrieve.

Common in web pages

• global variables usually defined at beginning of program

• global can be run by many functions

• local variables usually used in a subroutine and don’t exist after subroutine is run

• local variables may overwrite global variables

• but 2 local variables in different subroutines won’t overwrite each over

By Ref changes the value in variable

By ref passes the address

Byval only a copy of data is passed

ByVal change is lost when procedure ends

quick sort

merge sort

faster for larger data sets

1. find location of item

2. replace content of nude as ‘null’

3. make node pointing to item, point to the item which the null item was pointing to.

4. add item to the empty node list

1. find the location of the item you want to connect the new item to

2. create a new node

3. add a pointer from the current item to the new item

4. change the pointer of the new item to null

• both consist of nodes

• both connected by edges

• both dynamic data structures

using heuristics (an approximated cost from node x to the final node)

• makes finding shortest path more efficient as less nodes have to be covered

• Array size must be defined

• a stack pointer is used to point at top of array

• When an item pushed - pointer incremented

• When an item popped - pointer decremented

• identifying there is a problem to be solved

• identifying what the problem is and how it is solvable by a computer e.g. finite solutions

test the behaviour of a system before it is used

• stress testing

• testing with large number of inputs

• a tree has a hierarchy (parent/child)

• a tree has a root node

• a graph can be directed/undirected

• a graph can be weighted

recursion creates new variables each time whereas iteration uses the same variables

• record is a data structure

• class is a template for making data structures

• both can store multiple data types

• both can have instances

• both can have methods

concurrent processing is when two or more processes independant of each other can be executed at the same time, each task given a slice of processor time to look like tasks are being completed simultaneously.

a priority queue is used, shortest lengths at front of queue.

Uses weights

A* has two cost functions, actual cost and approximate cost.

A* doesn’t need to find all of the solutions

speed of algorithm is constrained by accuracy of heuristic

• larger number of requests -> server needs to respond within reasonable time

• users could override each others changes -> so use record locking to stop.

  • ☹️ could lead to deadlock where both don’t move as waiting on each other

• splits problem into smaller subproblems

  • smaller probs are more managable

  • smaller probs easier to solve

  • split tasks