computer paper 2

what is time complexity

how much time it requires to solve a particular problem

how is decomposition used in a game

breaks the problem down into its component parts. game can be divided into subprograms. subprograms can then be programmed as subroutines

how would pipelining be used in a game

the results from one subroutine will feet into the next subroutine

bubble sort pros

it is intuitive - easier to write

cons of global variables in a procedure

past values of the variable will remain

purpose of big o notaiton

to evaluate the tie complexity of an algorithm, and how the time taken increases with anincrease in the data set

What is tim complexty measured using

big-O notation

pros of data mining

• can look for links between a customer’s purchases

• can provide recommendations for future pruchases

• boost profits

• ensure demand is met

• improve quantity of stock needed

What is big-O notation

Shows the effectivness of the algorithm by showing the upper limit for the amount of time taken relative to the number of data elements given as an input

Why do we find the time complexity of algorithms

Allos you to predict the amount of time it takes an algorithm to finish given the bumber of data elements

How to reduce time complexity

Reduce the number of embedded loops or reduce the number of items you have to complete operations on

What is 0(1)

constant time complexity - the amount of time taken to complete the algorithm is independent from the number of elements inputted

quikc way of recognising Ono (1)

loops

0(1) graph

horizontal line

what is 0(n)

linear time complexity - the amount of time taken to complete the algorithm is directly proportional to the number of elements inputted

quick way of recognising linear time complexity

one loop repeating n times

example of 0(n)

linear search

linear search algorithm

def linearsearch(list, item):

index = -1

i = 0

found = False

while i < len(list) and found == False:

if list[i] == item:

index = i

found = True

i = i + 1

return index

0(n) graph

straight line through origin

what is 0(nⁿ)

Polynomial time complexity - the amount of time taken to complete the algorithm is directly proportional to the elements inputted to the power of n

Example of an algorithm with a polynomial time complexity

Nested for loops - the power in the polynimial is the same as the number of nested for loops. eg bubble sort is O(n²)

bubble sort algorithm

def bubblesort (array):

for i in range (0,len (array)):
for j in range (0, len(array)-1):
if array[j] > array[j+1]:
temp = array[j]
array[j] = array [j+1]
array[j+1] = temp
return array

What is 0(2ⁿ)

Exponential time complexity - the amount of time taken to complete an algorithm will double with every additional item e

example of an algorithm with an exponential time complexity

recursion

What is 0 (log n)

logarithmic time complexity - the time taken to complete the algorithm will increase at a smaller rate as the number of elements inputted

Example of algorithms with a logarithmic time complexity

divide and conquer algorithms - eg binary search as the number of items to search through gets halved each time

why is big-O notation important

it is a way of comparing algorithms so that the most efficient one can be chosen. A bad time complexity can make a problem involving vast amounts of data infeasible to solve

how does a linear search work

Starts with first item. This is compared to the item to be found. If equal then report found. If not equal then move to next item.
Repeat for all items, until found or end of list reached, which returns false.

when to use linear search

small losts or unordered lists

worst case time complexty of a linear search

O(n)

average time complexity of linear search

O(n)

best case time complexiy of linear search

O(1)

space complexity of linear seacrh

O(1)

how does binary search work

midpoint is calculated by adding upper and lower bound and dividing by two and rounding. If the item at the middle of the array is equal to the item to be found, set found to true. If the item to be found is less than the middle item, change the upper bound to be the midpoint - 1. if the item to be found is greater than the middle item, set the lower bound as the midpoint + 1. Repeat this porocess until the lower bound is greater than the upper bound. Rturn the found flag.

worst case time complexty for binary search array

O(log n )

average time complexity of binary search

O(log n )

best case time complexity of binary seacrh array

O(1)

space complexity of binary search

O(1)

worst case time complexity for binary search on a binary tree

O(n)

What is the worst to best time complexity

exponential , polynomial, linear, logarithmic, constant

What is spacce time complexity

The amount of storage an algorithm takes

How to reduce space complexity

Ensure you perform all changes on the original pieces of data because extra data is stored whenever a copy is made, which uses more storage so is more expensive

What is an algorithm

A series of steps that completes a task

What are the objectives of designing an algorithm

To get the best time and space complexity. There is no priority, it depends on the situation

When would you prioritise time complexity

If you have a lot of data that needs to be processed quickly

When would you prioritise space complexity

If you have a lot of processing power, time complexity isnt that important so you would prioritise space to make sure lots of data isnt wasted often

when to not use binary search

unordered list

how does a bubble sort work

Starting at the beginning of the list. Items are swapped with their
neighbour if they are out of order. Each pair of neighbours is checked in order. When a swap is made a flag is set. If at the end of the list the flag has been set, the flag is unset and the
algorithm starts from the beginning of the list again. When the algorithm gets to the end
of the list and the flag is unset, the list is sorted and the algorithm finishes

how to improve bubble sort

Checking one less item per iteration or alternating sorting directions

worst case time complexit of a bubble sort

O(n²)

average case time complexoty of bubble sort

O(n²)

best case time complexity of bubble sort

O(n)

space complexity of bubble sort

O(1)

how does insertion sort work

Breaks list into a sorted list (initially empty) and an unsorted list. One item taken from the unsorted list at a time and inseted into the sorted list in the correct place

worst case time complecity for insertion sort

O(n²)

Average case time complexity for insertion sort

O(n²)

best case time complexity for insertion sort

O(n)

space complexity of insertion

O(1)

Why is bubble sort inefficient

requires significantly more swaps than other algorithms, meaning it takes up more CPU cycles to solve the same problem

how does a merge sort work

divides the unsorted list into 2 until eachsublists contains one element. Repeatedly merge sublists by comparing the first item of both lists and selecting the smaller item and writing it into a new list. Repeat until all sorted sublists are recombined into a single list

worst case time complexity of merge sort

O(nlog n)

average case time complexity for merge sort

O(nlog n)

best case time complexity for merge sort

O(n log n )

space complexity for merge sort

O(n)

How does quick sort work

Use divide and conquer. One item in the list is made the pivot. All other items are compared to the pivot and are moved to the left of the pivot if it is smaller than it or to the right of the pivot if it is larger than it. This algorithm recursively repeats for the sublists to the left and right of the pivot (by choosing a pivot in each sublist) until there is only one element either side of the pivot.

worst case time complexity for quick sort

O(n²)

average case time complexity for quick sort

O(n log n)

best case time complexity for quick sort

O( n log n)

space complexity for quick sort

O(log n)

Why might a bubble or insertion sort be better than a quick or merge sort

easier to implement the algorithm and quicker on nearly sorted lists

what is meant by logarithmic growth

as the size of the array increases, the rate at which the number of checks needed increases more slowly

when is quick and merge sort better than insertion and bubble sort

larger data sets

which is faster insertion or bubble sort

insertion

why do bubble sort and insertion sort have space complexity of O(1)

They are inplace (all sorting takes place within the data itself)

why do bubble sort and insertion sort have time complexity of O(n²)

Nested loop

When is a depth first traversal used

job scheduling, where some jobs have to be completed before others can begin

what is breadth first traversal used for

finding the shortest path between two points ; eg facebook uses this to find all friends of a given person

why are trees traversed

to get the information stored in them

what is an intractable problem

one that cannot be solved efficiently - eg in polynomial time

what is an insoluble problem

one that has no solution at all other than heuristics

describe breadth firsth traversal

visits the first node and all conncting nodes. Then visits connecting nodes to these

describe depth first traversal

goes to the left node, this becomes a nw tree. Continues going left until it reaches a leaf. It then returns this value and then goes right and repeats from start.

Evaluate the use of breadth first vs depth first traversals

Breadth is more efficient when the data to be searched is closer to the root, whereas depth first is more effiient when data is further down. Breadth also generally has a better time complexity. Depth can be written recusively to aid understanding but in large trees, it may never return a value. Also depth memory requirement is linear.

why are values stored in an arrya instead of separate variables when sorted

so all values can be indexed in one array

compare bubble sort, insertion sort and merge sort

The best case time complexity for bubble sort and insertion sort is O(n), which is shorter than the best case for merge sort O(n log n). however, merge sort best worst and av time complexity is the same, wherease bubble and insertion average and worse cases are O(n²). Bubble and insertion have constant memory but merge uses more memory as new lists are needed.

describe how a leaf node is deleted from a binary search tree

traverse tree until required node is found. Set parent node to the leaf node to null

Describe how a ninary tree is searched for a value

1. If root is equal , return found

2. If value < root, tke left subtree. if value> root, take right subtree

3. repeat process for subtree

4. until value is found or no more branches can be travelled

Explain how backtracking is used in depth first traversal

When a leaf node is reached, the traversal backtracks to the leaf’s parent node

Describe how to add a new item to the end of a linked list

insert new item at the index of the next free pointer. Traverse the list to find the last item and update this pointer to be the index of the next free pointer. Update the next free pointer to the index the new item is pointing to Set the pointer of the new item to null.

Explain exponential

The rate of increase is at a rate of k^n as n increases . This makes it unmanageable for large data sets

explain constant

does not change

what is a jeuristic

a rule of thumb that estimates the distance from each node to the destination node

what loop could be used instead of while for a binary search algorthm

do until

Explain why quicksort is regarded as a divide and conquer lgorithm

decomposes the data set into smaller subsets which are then sorted before the subsets are recombined to provide a solution

describe how a binary search tree can be searched

if root node is equal to the item to be found, report found. If the item is smaller, take the left subtree. If the item is larger, take the right subtree. Repeat process for the subtree until item is found or no more branches to be travelled

evaluate the use of heuristics for a computer game

• Heuristics are rules of thumb used to find a ‘good enough solution’ to a problem.

• They are used to reduce the time taken to solve a problem.

• They work by adding a weight to a node. For example, it is used in the A star algorithm to estimate the shortest route between two nodes.

• They reduce the time complexity as every possibility within the game does not need to be examined.

• They are used in AI when the exact steps cannot be pre-programmed and decisions need to be made.

• Heuristics are more appropriate with complex time-critical tasks and some aspects of the game may require faster searching.

• Heuristics are more appropriate with large-scale tasks and the game could be large-scale, and AI algorithms may need to be shortened.

• Games are not life critical so a good answer is likelt enough and a perfect answer is not necessarily required.

• Avoids programs running indefinitely- in a computer game there could be too many

• In a gane, characters will have a certain number of paths they can follow which involve different routes so heuristics will be used to determine what path the character should take o get to one specific destination

Cons of heuristics

• However, they require skill to be implemented effectively - ie determining the hueristics of every node

• Due to time-saving, they are not always accurate and the solution eg the shortest path may not be the most efficient

• With a small number of paths, the time difference may not be noticeable

Why does thinking procedurally make writing a program easier

breaks down problem into smaller parts which are easier to understand and easier to design

First stage of thinking proceduraly

Problem decomposition - large, complex problem is continually broken down into smaller subproblems. Problem becomes more feasible to manage and can be divided between a group of people according to the skill stes of individuals,

How are problems decomposed

top-down design. Breaks down problems into levels. Higher levels provide an overview of a problem while lower levels specify in detail the components of this problem