paper 4

• Linear search


  1. mylist = []

  2. n = len(mylist) - 1

  3. ItemFind = input("Enter item be be found: " )

  4. ItemFind = False

  5. for i in range(0,n): if ItemFind == mylist[i]: ItemFound = True else: ItemFound = False

  6. if ItemFound == True: print("Item found")

  7. else: print("Item found")
• Binary search


  1. myList = []

  2. upperBound = len(myList) - 1

  3. lowerBound = 0

  4. item = int(input("Enter item to be found: "))

  5. found = False

  6. while (not found) and (lowerBound <= upperBound): index = ((upperBound+lowerBound)//2)

  7. if (myList[index]): found = True

  8. if item > myList[index]: lowerBound = index + 1

  9. if item < myList[index]: upperBound = index - 1

  10. if(found): print("Item found")

  11. else: print("Item not found")
• Insertion sort


  1. mylist = [53,21,60,8,94,18,42,19]

  2. print(mylist)

  3. n = len(mylist)

  4. print(n)

  5. for pointer in range(1,n): ItemToBeInserted = mylist[pointer]

  6. CurrentItem = pointer - 1

  7. while (mylist[CurrentItem] > ItemToBeInserted) and (CurrentItem > -1): mylist[CurrentItem + 1] = mylist[CurrentItem]

  8. CurrentItem = CurrentItem - 1

  9. mylist[CurrentItem + 1] = ItemToBeInserted

  10. print(mylist)
• Bubble sort


  1. mylist = []

  2. n = len(mylist) - 1

  3. noMoreSwaps = False

  4. while noMoreSwaps == False: noMoreSwaps = True

  5. for i in range(0,n): if mylist[i] > mylist[i + 1]: Temp = mylist[i]

  6. mylist[i] = mylist[i + 1]

  7. mylist[i + 1] = Temp

  8. noMoreSwaps = False
• Abstract Data Types (ADT)


  Data structures that define the operations that can be performed on them
• Initialise stack (using ADT and OOP)

  1. Stack = [Node() for i in range(8)]

  2. TopOfStack = NULLPOINTER

  3. FreeListPtr = 0

  4. for Index in range(7): Stack[Index].Pointer = Index + 1

  5. Stack[7].Pointer = NULLPOINTER
• Initialise stack (without ADT and OOP)

  1. TopOfStackPointer = NULLPOINTER

  2. Stack = [None for i in range(MAXSTACKSIZE)]
• Initialise queue (using ADT and OOP)


  1. Queue = [Node() for i in range(8)]

  2. HeadOfQueue = NULLPOINTER

  3. EndOfQueue = NULLPOINTER

  4. FreeListPtr = 0

  5. for Index in range(7): Queue[Index].Pointer = Index + 1

  6. Queue[7].Pointer = NULLPOINTER
• Initialise queue (without ADT and OOP)

  1. Queue = [EMPTYSTRING for i in range(MAXQUEUESIZE)]

  2. FrontOfQueue = NULLPOINTER

  3. EndOfQueue = NULLPOINTER

  4. NumberInQueue = 0
• Linked list


  A data structure where each element contains a pointer to the next element
• Initialise linked list (without OOP)

  1. myLinkedList = [27, 19, 36, 42, 16, None, None, None, None, None, None, None,]

  2. myLinkedListPointers = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, -1]

  3. startPointer = 4

  4. nullPointer = -1

  5. heapStartPointer = startPointer + 1
• Initialise linked list (using OOP)


  1. List = [ListNode() for i in range(8)]

  2. StartPointer = NULLPOINTER

  3. FreeListPtr = 0

  4. for Index in range(7): List[Index].Pointer = Index + 1

  5. List[7].Pointer = NULLPOINTER
• Binary tree


  A tree-like data structure where each node has at most two child nodes
• Initialise binary tree


  1. Tree = [TreeNode() for i in range(8)]

  2. RootPointer = NULLPOINTER

  3. FreePtr = 0

  4. for Index in range(7): Tree[Index].LeftPointer = Index + 1
• Find item in linked list (without OOP)

  1. found = False

  2. itemPointer = startPointer

  3. while itemPointer != nullPointer and not found: if myLinkedList[itemPointer] == itemSearch: found = True

  4. else: itemPointer = myLinkedListPointers[itemPointer]

  5. return itemPointer
• Find item in linked list (using OOP)


  1. CurrentNodePtr = StartPointer

  2. while CurrentNodePtr != NULLPOINTER and List[CurrentNodePtr].Data != DataItem: CurrentNodePtr = List[CurrentNodePtr].Pointer

  3. return(CurrentNodePtr)
• Find item in binary tree

  1. ThisNodePtr = RootPointer

  2. while ThisNodePtr != NULLPOINTER and Tree[ThisNodePtr].Data != SearchItem: if Tree[ThisNodePtr].Data > SearchItem: ThisNodePtr = Tree[ThisNodePtr].LeftPointer

  3. else: ThisNodePtr = Tree[ThisNodePtr].RightPointer

  4. return(ThisNodePtr)
• Push to stack (using ADT and OOP)

  1. if FreeListPtr != NULLPOINTER: NewNodePtr = FreeListPtr

  2. Stack[NewNodePtr].Data = NewItem

  3. FreeListPtr = Stack[FreeListPtr].Pointer

  4. Stack[NewNodePtr].Pointer = TopOfStack

  5. TopOfStack = NewNodePtr

  6. else: print("no space for more data")
• Push to stack (without ADT and OOP)


  1. if TopOfStackPointer < MAXSTACKSIZE - 1: TopOfStackPointer += 1

  2. Stack[TopOfStackPointer] = NewItem

  3. else: print("stack full")
• Join queue (using ADT and OOP)

  1. if FreeListPtr != NULLPOINTER: NewNodePtr = FreeListPtr

  2. Queue[NewNodePtr].Data = NewItem

  3. FreeListPtr = Queue[FreeListPtr].Pointer

  4. Queue[NewNodePtr].Pointer = NULLPOINTER

  5. if EndOfQueue == NULLPOINTER: HeadOfQueue = NewNodePtr

  6. else: Queue[EndOfQueue].Pointer = NewNodePtr

  7. EndOfQueue = NewNodePtr

  8. else: print("no space for more data")
• Add to queue (without ADT and OOP)

  1. if NumberInQueue == 0: FrontOfQueue = 0

  2. if NumberInQueue < MAXQUEUESIZE: EndOfQueue += 1

  3. if EndOfQueue > MAXQUEUESIZE - 1: EndOfQueue = 0

  4. Queue[EndOfQueue] = NewItem

  5. NumberInQueue += 1

  6. else: print("no space for more data")
• Insert into linked list (without OOP)

  1. if heapStartPointer == nullPointer: print("Linked list is full")

  2. else: tempPointer = startPointer

  3. startPointer = heapStartPointer

  4. heapStartpointer = myLinkedListPointers[heapStartPointer]

  5. myLinkedList[startPointer] = itemAdd

  6. myLinkedListPointers[startPointer] = tempPointer

  7. heapStartPointer += 1
• Insert into linked list (using OOP)

  1. if FreeListPtr != NULLPOINTER: NewNodePtr = FreeListPtr

  2. List[NewNodePtr].Data = NewItem

  3. FreeListPtr = List[FreeListPtr].Pointer

  4. PreviousNodePtr = NULLPOINTER

  5. ThisNodePtr = StartPointer

  6. while ThisNodePtr != NULLPOINTER and List[ThisNodePtr].Data < NewItem: PreviousNodePtr = ThisNodePtr

  7. ThisNodePtr = List[ThisNodePtr].Pointer

  8. if PreviousNodePtr == NULLPOINTER: List[NewNodePtr].Pointer = StartPointer

  9. StartPointer = NewNodePtr

  10. else: List[NewNodePtr].Pointer = List[PreviousNodePtr].Pointer

  11. List[PreviousNodePtr].Pointer = NewNodePtr

  12. else: print("no space for more data")
• Insert into binary tree

  1. if FreePtr != NULLPOINTER: NewNodePtr = FreePtr

  2. Tree[NewNodePtr].Data = NewItem

  3. FreePtr = Tree[FreePtr].LeftPointer

  4. Tree[NewNodePtr].LeftPointer = NULLPOINTER

  5. if RootPointer == NULLPOINTER: RootPointer = NewNodePtr

  6. else: ThisNodePtr = RootPointer

  7. while ThisNodePtr != NULLPOINTER: PreviousNodePtr = ThisNodePtr

  8. if Tree[ThisNodePtr].Data > NewItem: TurnedLeft = True

  9. ThisNodePtr = Tree[ThisNodePtr].LeftPointer

  10. else: TurnedLeft = False

  11. ThisNodePtr = Tree[ThisNodePtr].RightPointer

  12. if TurnedLeft: Tree[PreviousNodePtr].LeftPointer = NewNodePtr

  13. else: Tree[PreviousNodePtr].RightPointer = NewNodePtr

  14. else: print("no space for more data")
• Pop from stack (using ADT and OOP)

  1. if TopOfStack == NULLPOINTER: print("no data on stack")

  2. Value = Stack[TopOfStack].Data

  3. ThisNodePtr = TopOfStack

  4. TopOfStack = Stack[TopOfStack].Pointer

  5. Stack[ThisNodePtr].Pointer = FreeListPtr

  6. FreeListPtr = ThisNodePtr
• Pop from stack (without ADT and OOP)

  1. Item = EMPTYSTRING

  2. if TopOfStackPointer == NULLPOINTER: print("no data on stack")

  3. else: Item = Stack[TopOfStackPointer]

  4. TopOfStackPointer -= 1

  5. return(Stack, TopOfStackPointer, Item)
• Leave queue (using ADT and OOP)

  1. if HeadOfQueue != NULLPOINTER: Value = Queue[HeadOfQueue].Data

  2. ThisNodePtr = Queue[HeadOfQueue].Pointer
• Pop (using ADT and OOP)

  1. If TopOfStack == NULLPOINTER: print("no data on stack"), Value = ""

  2. Value = Stack[TopOfStack].Data

  3. ThisNodePtr = TopOfStack, TopOfStack = Stack[TopOfStack].Pointer, Stack[ThisNodePtr].Pointer = FreeListPtr, FreeListPtr = ThisNodePtr
• Pop (without ADT and OOP)

  1. If TopOfStackPointer == NULLPOINTER: print("no data on stack")

  2. Item = Stack[TopOfStackPointer], TopOfStackPointer -= 1
• LeaveQueue (using ADT and OOP)

  1. If HeadOfQueue != NULLPOINTER: Value = Queue[HeadOfQueue].Data, ThisNodePtr = Queue[HeadOfQueue].Pointer, If ThisNodePtr == NULLPOINTER: EndOfQueue = NULLPOINTER, Queue[HeadOfQueue].Pointer = FreeListPtr, FreeListPtr = HeadOfQueue, HeadOfQueue = ThisNodePtr

  2. Else: print("queue empty"), Value = ""
• RemoveFromQueue (without ADT and OOP)

  1. If NumberInQueue > 0: Item = Queue[FrontOfQueue], NumberInQueue -= 1, If NumberInQueue == 0: FrontOfQueue = NULLPOINTER, EndOfQueue = NULLPOINTER, Else: FrontOfQueue += 1, If FrontOfQueue > MAXQUEUESIZE - 1: FrontOfQueue = 0

  2. Else: print("queue empty")
• delete (Linked List without OOP)


  1. If startPointer == nullPointer: print("Linked List empty")

  2. Else: index = startPointer, While myLinkedList[index] != itemDelete and index != nullPointer: oldIndex = index, index = myLinkedListPointers[index], If index == nullPointer: print("Item", itemDelete, "not found"), Else: myLinkedList[index] = None, tempPointer = myLinkedListPointers[index], myLinkedListPointers[index] = heapStartPointer, heapStartPointer = index, myLinkedListPointers[oldIndex] = tempPointer
• DeleteNode (Linked List using OOP)


  1. ThisNodePtr = StartPointer, While ThisNodePtr != NULLPOINTER and List[ThisNodePtr].Data != DataItem: PreviousNodePtr = ThisNodePtr, ThisNodePtr = List[ThisNodePtr].Pointer, If ThisNodePtr != NULLPOINTER: If ThisNodePtr == StartPointer: StartPointer = List[StartPointer].Pointer, Else: List[PreviousNodePtr].Pointer = List[ThisNodePtr].Pointer, List[ThisNodePtr].Pointer = FreeListPtr, FreeListPtr = ThisNodePtr

  2. Else: print("data does not exist in list")
• factorial (recursive)


  If n == 0: return 1, Else: return n * factorial(n - 1)
• fibonacci (recursive)


  If n <= 1: return n, Else: return (fibonacci(n - 1) + fibonacci(n - 2))
• tower_of_hanoi (recursive)


  1. If n == 1: print(f"Move disk 1 from rod {from_rod} to rod {to_rod}"), return

  2. tower_of_hanoi(n - 1, from_rod, aux_rod, to_rod)

  3. print(f"Move disk {n} from rod {from_rod} to rod {to_rod}")

  4. tower_of_hanoi(n - 1, aux_rod, to_rod, from_rod)
• read_file


  1. Try: with open(filename, "r") as file: content = file.read(), return content

  2. Except FileNotFoundError: print(f"Error: {filename} not found."), return None

  3. Except IOError: print(f"Error: Unable to read {filename}."), return None
• write_to_file


  1. Try: with open(filename, "w") as file: file.write(content), print(f"Data written to {filename} successfully.")

  2. Except IOError: print(f"Error: Unable to write to {filename}.")
• append_to_file


  1. Try: with open(filename, "a") as file: file.write(content), print(f"Data appended to {filename} successfully.")

  2. Except IOError: print(f"Error: Unable to write to {filename}.")
• read_record_from_file


  1. Try: with open(filename, "r") as file: record = file.readline().strip(), If record: return record, Else: print("No more records found in the file."), return None

  2. Except FileNotFoundError: print(f"Error: {filename} not found."), return None

  3. Except IOError: print(f"Error: Unable to read from {filename}."), return None