2.3.1 Algorithms

Question 1

2.3.1 A)
What are the two things to check when developing an algorthim

Answer 1

Time complexity and space complexity

Question 2

2.3.1 A)
What is time complexity

Answer 2

How much time it takes to solve a problem.

Question 3

2.3.1 A)
How is time complexity measured. and what does it show

Answer 3

notation called big o notation. it shows the efficently of the algortihm. shows uper limit of time taken relative to number of elements inputted.

Question 4

2.3.1 A)
What are the big o notaions, their names and what they do

Answer 4

• o(1) - constant time - time take independant from # of inputs
• o(n) linear time - tt direction properitaoinal to number of elements inputted
• o(n^n or n*2) polynomail time - time takes to complete is proportional to element to the n^n or n^2
• o(2^n) - exponent time tt doubles w very item
• o (log n) logarhimic time - tt, inc at smalleer rate of elements ^

Question 5

2.3.1 A)
big o notations best to worse

Answer 5

O(1), O(LOG N), O(N), O(2^N)/O(N^N), O(N!)

Question 6

2.3.1 A)
Draw big o notation as a graph

Answer 6

check notes

Question 7

2.3.1 A)
space complexity, whats the significance of it, how is it measured

Answer 7

amount of storage the algorithm takes, ^storage = ^ expensive, bigO(o(n)) notation

Question 8

2.3.1 A)
What is an algorithm, what are the two main objectives

Answer 8

a series of steps that completesa task, main objectives is to complete the task and then to space asd time complexity.

Question 9

2.3.1 A)
How to reduce space complexity

Answer 9

• preform all changes on orginal peiece of data
• reduce embedded loops
• reduce # of items you need to do operations on

Question 10

2.3.1 B)
What are stacks and how do they work

Answer 10

stacks are first in last out (Filo) data structures often implemted as arrays

Question 11

2.3.1 B)
How do stacks keep track of elemeted

Answer 11

a sugular pointed called top pointer

Question 12

2.3.1 B)
Why is the top pointer initalised at -1

Answer 12

the top pointer is initalised at -1 bcos pointer at 0 would suggest somthing is in the list as arrays start at index values 0.

Question 13

2.3.1 B)
What are the operations and names for a stack

Answer 13

operations - name
checks size - size()
checks if empty - isEmpty()
return top element - peek()
add to stack - push(element)
returm top element and remove - pop()

Question 14

2.3.1 B)
What does size() do in a stack ?

Answer 14

returns # of elements returns value of top point +1 as first element is in 0.

Question 15

2.3.1 B)
What does isEmpty() do in a stack ?

Answer 15

checks if pointer is at 0> aka -1

Question 16

2.3.1 B)
What does peek() do in a stack ?

Answer 16

returns top w/o removing it check if it is empty first or will get an error

Question 17

2.3.1 B)
What does push(element) do in a stack ?

Answer 17

new item passed through parameter then at position of top pointer

Question 18

2.3.1 B)
What does pop() do in a stack ?

Answer 18

the element at the position of the top pointer is record before being removed. the top pointer is decremented by one before removed item is returned. Make sure stack isnt empty before attemping to pop or error.

Question 19

2.3.1 E)
Binary seach in steps

Answer 19

1) calc midpoint
2) (ub + lb) /2
3) compare arry midpoint with value
4) if same, flag set to true
5) if mp < value, mp = lb + 1
6) if mp > value, mp = ub + 1
7) repeat
8) until lb >= ub
9) return flag found

Question 20

2.3.1 E)
linear seach in steps

Answer 20

1) compare search item w/ first value
2) compare search item w/ next value
3) repeat until either
4) end of array
5) item is found
6) return the position

Question 21

2.3.1 E)
insertion sort in steps

Answer 21

1) start at second item
2) compare current with first item in sorted list
3)if current item large move infron of other item
4) repeat until current is less then or equal to sorted
5) move all up one
6) insert current
7) repeat until done