2.3

• What makes a good algorithm? ◦ Has clear and precisely stated steps that producethe correct output for any set of valid inputs◦ Should allow for invalid inputs◦ Must always terminate at some point◦ Should execute efficiently in as few steps as possible◦ Should be designed in such a way that other people will be able to understand it and modify it if necessary◦ We need to be able to identify the most suitable algorithm for a given task and dataset in terms of execution time and space.
• What is the suitability of different algorithms for a given task given task and data set in terms of execution and space? There may be many different algorithms that solve an issue and they can be compared on how much time it takes for them to solve it. This is called the time complexity of the algorithm.We can determine which algorithm is best to use by comparing the time and space complexity then deciding the best to use based on the scenario.
• What is complexity? "Complexity is a measure of how much the time memory space or resources needed for an algorithm increase as the data size it works on increases.This is represented using big O NotationA notation that shows the effectiveness of an algorithmIt shows the upper limit for the amount of time and memory taken relative to the number of data elements given as an inputIt considers what we call the ""worst case scenario"" assuming that every possible element is touched on as the algorithm executesThere are two types of complexityTime complexitySpace complexity"
• What is time complexity? Time efficiency is a measure of how much time it takes to complete an algorithm as its input (N) increases.For example on the previous page we had a loop summing up all numbers to N :- For x = 1 to N x = x + 1 Next x The time taken to complete this algorithm is directly related to the size of N. For N as a million it would take a million loops to complete. Therefore in this case time increases linearly with N.Is there are better algorithm to do this? i.e. one that is constant and not dependent on the size of NIn fact there is. There is a formula to sum up any number to the value of N Sum of numbers = n(n+1)/2Try it - it does work for any n. For example what is the sum of all numbers up to 1000? In your calculator type in 1001 (the n+1 bit) then multiply by 1000 (the n bit) then divide by 2 : answer 500500. Which shows one line of code (your calculator) can work out this problem.Therefore in terms of time efficiency this is a better summing algorithm than the iteration version.
• What is Big O Notation? This is the measure of the time complexity of an algorithm. It is a useful approximation of the time taken to execute an algorithm for a given number of items in a data set.When finding the Big O of an algorithm only the dominant term counts so even if the algorithm is working at O(n+1) the big O has to be O(n).In order to calculate the time complexity of an algorithm we need to count the number of basic operations it performs. This includes each iteration of loops.
• What are the 7 classifications of Big O notation? ""
• What is O(1)? "O(1) - Constant ComplexityNo matter the size of the input the execution time will always remain the same. "
• What is O(log n)? "The execution time of the algorithm is directly proportional to the logarithmic size of the input dataA binary search is a good example of this as with each pass the data set halves itself "
• What is O(n)?  "Algorithm's execution time is directly proportional to the input size It directly correlates with each other "
• What is O(n^2)? "Execution time is directly proportional to the square of the input size "
• What is O(2^n)? "The time taken to execute the algorithm will double with each additional input given "
• Important pieces of info for Big O "Working out big O "
• Linked list implementation "ImplementationRecordsClasses"
• Linked List Traversal RecordsSUBROUTINE traverse(head) current = head WHILE current != Null // Continue to end of list PRINT(current.data) current = current.next // Get pointer to the next record ENDWHILE ENDSUBROUTINEClassesCLASS Node .... PUBLIC FUNCTION get_data() return data ENDFUNCTION PUBLIC FUNCTION get_next() return next ENDFUNCTION PUBLIC PROCEDURE set_next(new_next) next = new_next ENDPROCEDURE ENDCLASS CLASS LinkedList .... PUBLIC PROCEDURE traverse() current = head WHILE current != Null // Continue to end of list PRINT(current.get_data()) current = current.get_next() // Get pointer to next record ENDWHILE ENDPROCEDURE ENDCLASSCLASS Node PRIVATE data: String PRIVATE next: Node // Constructor method PUBLIC PROCEDURE Node(given_data) data = given_data next = Null ENDPROCEDURE ENDCLASS CLASS LinkedList PRIVATE head: Node // Constructor method PUBLIC PROCEDURE LinkedList() head = Null ENDPROCEDURE ENDCLASS // Instantiate an empty linked list object my_list = NEW LinkedList()
• Adding to a linked list RecordsPROCEDURE insert_at_front(head data) // Create the new node new_node = NodeRecord new_node.data = data new_node.next = Null // Insert at front of list IF head == Null THEN head = new_node ELSE new_node.next = head head = new_node ENDIF ENDPROCEDUREClassesCLASS LinkedList .... PROCEDURE insert_at_front(data) new_node = new Node(data) // Create new node // Insert at front of list IF head = None THEN head = new_node ELSE new_node.set_next(head) head = new_node ENDIF ENDPROCEDURE ENDCLASS
• Adding in an ordered linked list RecordsPROCEDURE insert_in_order(head data) // Create the new node new_node = NodeRecord() new_node.data = data new_node.next = None // Insert into position current = head IF current == None THEN // No nodes in list head = new_node ELSEIF current.data >= new_node.data THEN // New node is head of list // Change pointers new_node.next = my_list.head head = new_node ELSE // Find the point of insertion WHILE (current.next != Null and current.next.data < new_node.data) current = current.next ENDWHILE // Change pointers new_node.next = current.next current.next = new_node ENDIF ENDPROCEDUREClassesCLASS LinkedList .... PROCEDURE insert_in_order(data) // Create the new node new_node = new Node(data) // Insert into position current = head IF current == None THEN // No nodes in list head = new_node ELSEIF current.get_data() >= new_node.get_data() THEN // New node is head of list // Change pointers new_node.set_next(head) head = new_node ELSE // Find the point of insertion WHILE (current.get_next() != None and current.get_next().get_data() < new_node.get_data()) current = current.get_next() ENDWHILE // Change pointers new_node.set_next(current.get_next()) current.set_next(new_node) ENDIF ENDPROCEDURE ENDCLASS
• Deleting nodes in a linked list recordsPROCEDURE delete(head data): current = head IF current.data == data THEN // Deleting item at head of list head = current.next ELSE WHILE current.next.data != data current = current.next ENDWHILE current.next = current.next.next // Swap pointers ENDIF ENDPROCEDUREClassesCLASS LinkedList .... PROCEDURE delete(data) current = head IF current.get_data() = data THEN // Deleting item at head of list head = current.get_next() ELSE WHILE current.get_next().get_data() != data current = current.get_next() ENDWHILE current.set_next(current.get_next().get_next()) // Swap pointers ENDIF ENDPROCEDURE ENDCLASS
• Adding to a tree ""
• Deleting from a tree " "
• Binary Search Tree Algorithm FUNCTION binary_tree_search(node search_item) IF search_item == node.data THEN RETURN True ELSEIF search_item > node.data AND node.right != Null THEN RETURN binary_tree_search(node.right search_item) ELSEIF search_item < node.data AND node.left != Null THEN RETURN binary_tree_search(node.left search_item) ENDIF RETURN False ENDFUNCTION
• Hash Table: Adding an item ""
• Hash table: deleting an item ""
• Hash table: traversal ""
• Queue: Initialisation Linear queue initialisationMAX_SIZE = 100 ARRAY queue[max_size] front = 0 rear = -1
• Enqueue (linear) "Enqueue (linear)FUNCTION is_full(rear) IF (rear + 1) == MAX_SIZE THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION enqueue(queue rear data) IF is_full(rear) == True THEN PRINT (""Queue is full"") ELSE rear = rear + 1 queue[rear] = data ENDIF RETURN rear ENDFUNCTION"
• Dequeue (linear) "Dequeue (linear)FUNCTION is_empty(front rear) IF front > rear THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION dequeue(queue front rear) IF is_empty(front rear) == True THEN PRINT(""Queue is empty"") dequeued_item = Null ELSE dequeued_item = queue[front] front = front + 1 ENDIF RETURN (dequeued_item front) ENDFUNCTION"
• Circular Queue implementation MAX_SIZE = 100 // Uses a constant ARRAY circular_queue[MAX_SIZE] front = -1 rear = -1
• Enqueue (circular) "Enqueuing on a circularFUNCTION is_full(front rear) IF (rear + 1) MOD MAX_SIZE == front THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION enqueue(queue front rear data) IF is_full(front rear) == True THEN OUTPUT 'Queue is full' ELSE rear = (rear + 1) MOD MAX_SIZE queue[rear] = data IF front = -1 THEN // First item to be queued front = 0 ENDIF ENDIF RETURN (front rear) ENDFUNCTION"
• Dequeue (Circular) "Dequeuing on a circularFUNCTION is_empty(rear) IF front == -1 THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION dequeue(queue front rear) IF is_empty(rear) == True THEN PRINT(""Queue is empty"") dequeued_item = Null ELSE dequeued_item = queue[front] IF front == rear THEN // Nothing left in queue front = -1 rear = -1 ELSE front = (front + 1) MOD maxsize ENDIF ENDIF RETURN (dequeued_item front rear) ENDFUNCTION"
• Priority Queue priority queueCLASS Node PRIVATE data: String PRIVATE priority: Integer PRIVATE next: Pointer PUBLIC PROCEDURE new(item_data item_priority) data = item_data priority = item_priority next = Null ENDPROCEDURE PUBLIC PROCEDURE set_next(new_next) next = new_next ENDPROCEDURE PUBLIC FUNCTION get_next() RETURN next ENDFUNCTION PUBLIC FUNCTION get_data() RETURN data ENDFUNCTION PUBLIC FUNCTION get_priority() RETURN priority ENDFUNCTION ENDCLASS CLASS PriorityQueue PRIVATE front: Pointer PRIVATE rear: Pointer PUBLIC PROCEDURE new() front = Null rear = Null ENDPROCEDURE PUBLIC PROCEDURE set_front(new_front) front = new_front ENDPROCEDURE PUBLIC FUNCTION get_front() RETURN front ENDFUNCTION PUBLIC PROCEDURE set_rear(new_rear) rear = new_rear ENDPROCEDURE PUBLIC FUNCTION get_rear() RETURN rear ENDFUNCTION ENDCLASS
• Enqueue (Priority) Enqueue prioritiesPUBLIC PROCEDURE enqueue(data priority): new_node = Node(data priority) IF front == Null THEN // Queue is empty front = new_node rear = new_node ELSE IF new_node.get_priority() > front.get_priority() THEN new_node.set_next(front) front = new_node ELSEIF new_node.get_priority() <= rear.get_priority() THEN rear.set_next(new_node) rear = new_node ELSE current = front WHILE (current.get_priority() >= new_node.get_priority()) previous = current current = current.get_next() ENDWHILE new_node.set_next(current) previous.set_next(new_node) ENDIF ENDIF ENDPROCEDURE
• Dequeue (Priority) "Dequeue prioritiesPUBLIC FUNCTION dequeue() IF front == Null THEN dequeued_item = Null PRINT(""Nothing dequeued - queue is empty"") ELSE dequeued_item = front.get_data() front = front.get_next() ENDIF RETURN dequeued_item ENDFUNCTION"
• Class Intitialisation (Priority Queue) "Class initialisationPROCEDURE test_my_queue() my_queue = new PriorityQueue() my_queue.enqueue('peas' 3) my_queue.enqueue('turnips' 4) my_queue.enqueue('cabbage' 4) my_queue.enqueue('carrots' 3) dequeued_element = my_queue.dequeue() PRINT(dequeued_element) ENDPROCEDURE"
• Stack Implementation MAX_SIZE = 100 // Uses a constant ARRAY stack[MAX_SIZE] top = -1
• Push (stack) "FUNCTION is_full(top) IF top == MAX_SIZE - 1 THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION push(stack top data) IF is_full(top) == True THEN PRINT(""Stack is full"") ELSE top = top + 1 stack[top] = data ENDIF RETURN top ENDFUNCTION"
• Pop (stack) "FUNCTION is_empty(top) IF top == -1 THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION pop(stack top) IF is_empty(top) == True THEN PRINT (""Stack is empty"") popped_item = Null ELSE popped_item = stack[top] top = top - 1 ENDIF RETURN (popped_item top) ENDFUNCTION"
• Peek (stack) "To return the item at the top of the stack without removing it simply return the item at the position indicated by the top pointer. For these examples we’ll assume our stack is an array called A.Don’t forget to check that the stack has data in it before attempting to return data though as an empty stack could cause errors. It’s useful to use the isEmpty function here.FUNCTION peek(stack top) IF is_empty(top) == True THEN PRINT(""Stack is empty"") peeked_item = Null ELSE peeked_item = stack[top] ENDIF RETURN peeked_item ENDFUNCTION"
• What is a bubble sort? "Bubble SortIs intuitive (easy to understand and program) but inefficient.Uses a temp element.Moves through the data in the list repeatedly in a linear wayStart at the beginning and compare the first item with the second.If they are out of order swap them and set a variable swapMade true.Do the same with the second and third item third and fourth and so on until the end of the list.When at the end of the list if unsorted variables still remain parse through the algorithm again; otherwise If all variables are sorted the list is sorted and the algorithm stops.Trace Table: "
• What is an insertion sort? "Works by dividing a list into two parts: sorted and unsortedElements are inserted one by one into their correct position in the sorted section by shuffling them left until they are larger than the item to the left of them until all items in the list are checked.Simplest sort algorithmInefficient & takes longer for large sets of data "
• What is a merge sort? "Works by splitting n data items into n sublists one item big.These lists are then merged into sorted lists two items big which are merged into lists four items big and so on until there is one sorted list.Is a recursive algorithm = require more memory spaceIs fast & more efficient with larger volumes of data to sort."