ZNOTES.ORGUPDATED TO 2017-19 SYLLABUSCAIE A2 LEVELCOMPUTERSCIENCE(9618)SUMMARIZED NOTES ON THE PRACTICAL SYLLABUSCAIE A2 LEVEL COMPUTER SCIENCE (9618)1.Computational Thinkingand Problem Solving1.1.AbstractionAbstraction is the process of modeling a complex systemin an easy to understand way by only including essentialdetails,using:Iterative Binary Search:Functions and procedures with suitable parameters-Imperative Programming·Classes→Object Orientated Programming·Facts and rules→Declarative programmingADTs(Abstract Data Types)1.2.AlgorithmsSerial/Sequential/Linear SearchAll the values are considered in sequence·Insertion SortEven if an item is not found,all the values will haveItems from the input array are copied one at a time tobeen consideredthe output arrayBest-case scenario:item to be found is at the start ofEach new item is inserted into the right place so thatthe list→O(1)the output array is always in order.Worst-case scenario-max number of comparisons,Considerably faster than the bubble sort for a smallerwhen item to be found is at the end of the list-O(N)number of data itemswhere N is the number of elements in the listIterative process·Average number of comparisons→N/2·Binary SearchUsed to search an orderedarrayMuch faster than a linear search for arrays of morethan a few itemswhile position >0 and array[position-1]>currentValue:array[position]-array(poaition-1]1.Ordered array divided into 3 parts:middle,lower andupperreturn array）2.Middle item is examined to see if it is equal to thearray=[6,2,9,7,15]sought item3.If not,and the middle value is greater than the soughtprint (array)item,the upper part of the array is disregarded·Bubble Sort4.The process is repeated for the bottom partThe list is divided into two sublists:sorted andunsorted.When compared to linear search,whose worst-The largest element is bubbled from the unsorted listcase behaviour is N iterations,we see that binaryand moved to the sorted sublist.search is substantially faster as N grows large.Forexample,to search a list of one million items takesAfter that,the wall moves one element back,increasing the number of sorted elements andas many as one million iterations with lineardecreasing the number of unsorted ones.search,but never more than twenty iterationsEach time an element moves from the unsorted partwith binary searchto the sorted part one sort pass is completed.Recursive Binary Search:Given a list of n elements,bubble sort requires up ton-1 passes(maximum passes)to sort the data.WWW.ZNOTES.ORGCAIE A2 LEVEL COMPUTER SCIENCE(9618)Algorithm for insertion in linked listarray=[4,2,5,1,6,7,8,3]for i in range(len(array)):for j in range(len(array)-1):if array[j]array[j+1]:temp=array[j】array[j+1】=tempprint (array)The performance of either sort routine is the best whenthe data is already in order and there are a small numberElseof data items.uEnd IFCan be represented as two 1-D arrays-string array forElsedata values and integer array for pointer valuesCreating a Linked list-Setting values of pointers infree list and empty data linked listFOR Index 1 TO 49NameList(Index].Pointer Index 1EN DFORNameList [50].Pointer -0Searching a Linked ListHeadPointer -0Algorithm for searching in a linked listProcedure Searchltem(Newltem)FreePointer -1While CurrentPointer>0 and found falseA user-defined record type should first be created torepresent a node's data and pointer:Print "item found at address"CurrentPointerSet found to trueProgram code for creating free list and empty data linked listEnd WhileDefine the array with the user-defined record type as its data type and alsoDeleting an Item from a Linked List1.Use a Boolean value to know when an item has beenfound and deleted (initially false)2.Use a pointer(CurrentPointer)to go through eachInserting into a Linked Listnode's address3.If new item is found at the header:1.Set head pointer to pointer of node atCurrentPointer2.Set pointer od node at CurrentPointer to freepointer3.Free pointer points to CurrentPointer4.Set Boolean value to True4.Otherwise:1.Search for Item while end of linked list notreached and Boolean value is false1.Use a Previous Pointer to keep track ofthe node located just before the onedeletedWWW.ZNOTES.ORG