USE PYTHON for the following questions. And the end of this page I have posted t
ID: 3871591 • Letter: U
Question
USE PYTHON for the following questions. And the end of this page I have posted tjo codes to work with for the questions.
Here are the codes:
binheap.py
import unittest
# this heap takes key value pairs, we will assume that the keys are integers
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0
def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
# print(len(self.heapList), i)
while (i > 0):
# print(self.heapList, i)
self.percDownRec(i)
i = i - 1
# print(self.heapList,i)
def percUpRec(self, i):
# ADD CODE HERE
pass
## def percUp(self,i):
## while i // 2 > 0:
## if self.heapList[i] < self.heapList[i//2]:
## tmp = self.heapList[i // 2]
## self.heapList[i // 2] = self.heapList[i]
## self.heapList[i] = tmp
## i = i // 2
##
def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUpRec(self.currentSize)
def percDownRec(self,i):
# ADD CODE HERE
pass
## def percDown(self,i):
## while (i * 2) <= self.currentSize:
## mc = self.minChild(i)
## if self.heapList[i] > self.heapList[mc]:
## tmp = self.heapList[i]
## self.heapList[i] = self.heapList[mc]
## self.heapList[mc] = tmp
## i = mc
def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDownRec(1)
return retval
def isEmpty(self):
if currentSize == 0:
return True
else:
return False
def size(self):
return self.currentSize
def __str__(self):
return str(self.heapList[1:])
class FooThing:
def __init__(self,x,y):
self.key = x
self.val = y
def getKey(self):
return self.key
def getValue(self):
return self.val
def setValue(self, newValue):
self.val = newValue
def __eq__(self,other):
if self.key == other.key:
return True
else:
return False
def __ne__(self,other):
if self.key != other.key:
return True
else:
return False
def __lt__(self,other):
if self.key < other.key:
return True
else:
return False
def __le__(self,other):
if self.key <= other.key:
return True
else:
return False
def __gt__(self,other):
if self.key > other.key:
return True
else:
return False
def __ge__(self,other):
if self.key >= other.key:
return True
else:
return False
def __hash__(self):
return self.key
class TestBinHeap(unittest.TestCase):
def setUp(self):
self.theHeap = BinHeap()
self.theHeap.insert(FooThing(5,'a'))
self.theHeap.insert(FooThing(9,'d'))
self.theHeap.insert(FooThing(1,'x'))
self.theHeap.insert(FooThing(2,'y'))
self.theHeap.insert(FooThing(3,'z'))
def testInsert(self):
assert self.theHeap.currentSize == 5
def testDelmin(self):
assert self.theHeap.delMin().getValue() == 'x'
assert self.theHeap.delMin().getValue() == 'y'
assert self.theHeap.delMin().getValue() == 'z'
assert self.theHeap.delMin().getValue() == 'a'
def testMixed(self):
myHeap = BinHeap()
myHeap.insert(9)
myHeap.insert(1)
myHeap.insert(5)
assert myHeap.delMin() == 1
myHeap.insert(2)
myHeap.insert(7)
assert myHeap.delMin() == 2
assert myHeap.delMin() == 5
def testDupes(self):
myHeap = BinHeap()
myHeap.insert(9)
myHeap.insert(1)
myHeap.insert(8)
myHeap.insert(1)
assert myHeap.currentSize == 4
assert myHeap.delMin() == 1
assert myHeap.delMin() == 1
assert myHeap.delMin() == 8
def testBuildHeap(self):
myHeap = BinHeap()
myHeap.buildHeap([9,5,6,2,3])
f = myHeap.delMin()
# print("f = ", f)
assert f == 2
assert myHeap.delMin() == 3
assert myHeap.delMin() == 5
assert myHeap.delMin() == 6
assert myHeap.delMin() == 9
if __name__ == '__main__':
suite = unittest.makeSuite(TestBinHeap)
unittest.TextTestRunner().run(suite)
node.py
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
ordered linked list.py
from node import Node
class OrderedList(object):
def __init__(self):
""" Constructs an empty unsorted list.
Precondition: none
Postcondition: Reference to empty unsorted list returned.
"""
self._head = None
self._tail = None
self._size = 0
self._current = None
self._previous = None
self._currentIndex = 0
def search(self, targetItem):
""" Searches for the targetItem in the list.
Precondition: none.
Postcondition: Returns True and makes it the current item if targetItem is in the list;
otherwise False is returned.
"""
def searchHelper():
""" Recursive helper function that moves down the linked list.
It has no parameters, but uses self._current, self._previous, and
self._currentIndex."""
# ADD CODE HERE
pass
# START OF SEARCH - DO NOT MODIFY BELOW CODE
if self._current != None and self._current.getData() == targetItem:
return True
self._previous = None
self._current = self._head
self._currentIndex = 0
return searchHelper() # Returns the result of searchHelper
## NON-RECURSIVE CODE WE ARE REPLACING
## def search(self, targetItem):
## """ Searches for the targetItem in the list.
## Precondition: none.
## Postcondition: Returns True and makes it the current item if targetItem is in the list;
## otherwise False is returned.
## """
## if self._current != None and self._current.getData() == targetItem:
## return True
##
## self._previous = None
## self._current = self._head
## self._currentIndex = 0
## while self._current != None:
## if self._current.getData() == targetItem:
## return True
## elif self._current.getData() > targetItem:
## return False
## else: #inch-worm down list
## self._previous = self._current
## self._current = self._current.getNext()
## self._currentIndex += 1
## return False
def add(self, newItem):
""" Adds the newItem to is sorted spot in the list.
Precondition: newItem is not in the list.
Postcondition: newItem is added to the list.
"""
if self.search(newItem):
raise ValueError("Cannot not add since item is already in the list!")
temp = Node(newItem)
temp.setNext(self._current)
if self._previous == None:
self._head = temp
else:
self._previous.setNext(temp)
if self._current == None:
self._tail = temp
self._size += 1
def remove(self, item):
""" Removes item from the list.
Precondition: item is in the list.
Postcondition: Item is removed from the list.
"""
if not self.search(item):
raise ValueError("Cannot remove item since it is not in the list!")
if self._current == self._tail:
self._tail = self._previous
if self._current == self._head:
self._head = self._head.getNext()
else:
self._previous.setNext(self._current.getNext())
self._current = None
self._size -= 1
def isEmpty(self):
""" Checks to see if the list is empty.
Precondition: none.
Postcondition: Returns True if the list is empty; otherwise returns False.
"""
return self._size == 0
def length(self):
""" Returns the number of items in the list.
Precondition: none.
Postcondition: Returns the number of items in the list.
"""
return self._size
def index(self, item):
""" Returns the position of item in the list.
Precondition: item is in the list.
Postcondition: Returns the position of item from the head of list.
"""
if not self.search(item):
raise ValueError("Cannot determine index since item is not in the list!")
return self._currentIndex
def pop(self, *pos):
""" Removes and returns the item at position pos of the list.
Precondition: position pos exists in the list.
Postcondition: Removes and returns the item at position pos of the list.
"""
if len(pos) == 0:
pos = self._size - 1
elif len(pos) != 1:
raise TypeError("Too many parameters to pop")
else:
pos = pos[0]
if not isinstance(pos, int):
raise TypeError("Position must be an integer!")
if pos >= self._size or pos < 0:
raise IndexError("Cannot pop from index", pos, "-- invalid index!")
self._current = self._head
self._previous = None
for count in range(pos):
self._previous = self._current
self._current = self._current.getNext()
if self._current == self._tail:
self._tail = self._previous
if self._current == self._head:
self._head = self._head.getNext()
else:
self._previous.setNext(self._current.getNext())
returnValue = self._current.getData()
self._current = None
self._size -= 1
return returnValue
def __str__(self):
""" Returns a string representation of the list with a space between each item.
Precondition: none
Postcondition: Returns a string representation of the list with a space between each item.
"""
def strHelper(current):
if current == None:
return ""
else:
return str(current.getData()) + " " + strHelper(current.getNext())
resultStr = "(head) " + strHelper(self._head) + "(tail)"
return resultStr
## def __str__(self):
## """ Removes and returns the item at position pos of the list.
## Precondition: position pos exists in the list.
## Postcondition: Removes and returns the item at position pos of the list.
## """
## resultStr = "(head)"
## current = self._head
## while current != None:
## resultStr += " " + str(current.getData())
## current = current.getNext()
## return resultStr + " (tail)"
if __name__ == '__main__':
myList = OrderedList()
assert myList.search('a') == False
myList.add('3')
myList.add('5')
myList.add('7')
assert myList.search('1') == False
assert myList.search('3') == True
assert myList.search('4') == False
assert myList.search('5') == True
assert myList.search('6') == False
assert myList.search('7') == True
assert myList.search('8') == False
print("ALL SEARCH TESTS PASSED!!!")
list tester.py
from ordered_linked_list import OrderedList
def main():
myList = OrderedList()
while True:
print(" Ordered List Tester Menu")
print("a - add")
print("r - remove(item)")
print("i - index(item)")
print("p - pop()")
print("pp - pop(position)")
print("s - search(item)")
print("l - length")
print("x - eXit")
print(" The current list is:", str(myList))
command = input(" Enter your choice: ").lower()
if command == 'a':
item = input("Enter item to add: ")
myList.add(item)
elif command == 'r':
item = input("Enter item to remove from list")
myList.remove(item)
elif command == 'i':
item = input("Enter item to determine index")
index = myList.index(item)
print("The item is at index:",index)
elif command == 'p':
item = myList.pop()
print("The item popped from the tail was:",item)
elif command == 'pp':
index = eval(input("Enter index to pop from:"))
item = myList.pop(index)
print("The item popped from the index was:",item)
elif command == 's':
item = input("Enter item to search for ")
found = myList.search(item)
print("The item search result:",found)
elif command == 'l':
print("The length of the list is:",myList.length())
elif command == 'x':
break
else:
print(" Invalid command only 'a', 'r', 'i', 'p', 'pp', 's', 'l', 'x' are valid ")
main()
Part A: Recall: We modified the textbook's ordered list ADT that uses a singly-linked list implementation by adding the_size, _tail, _current, _previous, and_currentIndex attributes OrderedList Object data next data next data next data next data next head 'm size4 previous currentIndex 3 current tail NON-RECURSIVE CODE WE ARE REPLACING def search(self, targetitem) def search (self, targetItem) if self- current != None and def searchHelper elf._current.getData)targetItem: """ Recursive helper function th t moves down the linked list It has no paraneters, but uses self._current, self._previous self. currentIndex.""" return True ADD CODE EERE self previous = None self. current= self- head self, current!ndex = 0 while self- current !-None ; if self. current.getData)targetItem: elif self._current.getData) > targetItem: else: #inch-worm down list return True return False # START OF SEARCH - DO NOT MODIFY BELO' CODE if self, current != None and self.-previous = self-current self._currentself._current.getNext) self- curr ntIndex +.. 1 self._current.getDatal) - targetitem: return True return False self. previousNone self._currentself._head self. currentIndex0 return searchHelper() # Returns the result of searchHelper a) What are the base case(s) for the searchRelper that halt the while-loop of the non-recursive search codc? b) What are the recursive case(s) for the searchHelper that replaces the while-loop of the non-recursive search codc? c) Complete the recursive searchHelper function in the search method of our OrderedList class in ordered_linked list.py. Test it with the 1istTester.py program.Explanation / Answer
import unittest
# this heap takes key value pairs, we will assume that the keys are integers
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0
def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
# print(len(self.heapList), i)
while (i > 0):
# print(self.heapList, i)
self.percDownRec(i)
i = i - 1
# print(self.heapList,i)
def percUpRec(self, i):
# ADD CODE HERE
pass
## def percUp(self,i):
## while i // 2 > 0:
## if self.heapList[i] < self.heapList[i//2]:
## tmp = self.heapList[i // 2]
## self.heapList[i // 2] = self.heapList[i]
## self.heapList[i] = tmp
## i = i // 2
##
def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUpRec(self.currentSize)
def percDownRec(self,i):
# ADD CODE HERE
pass
## def percDown(self,i):
## while (i * 2) <= self.currentSize:
## mc = self.minChild(i)
## if self.heapList[i] > self.heapList[mc]:
## tmp = self.heapList[i]
## self.heapList[i] = self.heapList[mc]
## self.heapList[mc] = tmp
## i = mc
def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDownRec(1)
return retval
def isEmpty(self):
if currentSize == 0:
return True
else:
return False
def size(self):
return self.currentSize
def __str__(self):
return str(self.heapList[1:])
class FooThing:
def __init__(self,x,y):
self.key = x
self.val = y
def getKey(self):
return self.key
def getValue(self):
return self.val
def setValue(self, newValue):
self.val = newValue
def __eq__(self,other):
if self.key == other.key:
return True
else:
return False
def __ne__(self,other):
if self.key != other.key:
return True
else:
return False
def __lt__(self,other):
if self.key < other.key:
return True
else:
return False
def __le__(self,other):
if self.key <= other.key:
return True
else:
return False
def __gt__(self,other):
if self.key > other.key:
return True
else:
return False
def __ge__(self,other):
if self.key >= other.key:
return True
else:
return False
def __hash__(self):
return self.key
class TestBinHeap(unittest.TestCase):
def setUp(self):
self.theHeap = BinHeap()
self.theHeap.insert(FooThing(5,'a'))
self.theHeap.insert(FooThing(9,'d'))
self.theHeap.insert(FooThing(1,'x'))
self.theHeap.insert(FooThing(2,'y'))
self.theHeap.insert(FooThing(3,'z'))
def testInsert(self):
assert self.theHeap.currentSize == 5
def testDelmin(self):
assert self.theHeap.delMin().getValue() == 'x'
assert self.theHeap.delMin().getValue() == 'y'
assert self.theHeap.delMin().getValue() == 'z'
assert self.theHeap.delMin().getValue() == 'a'
def testMixed(self):
myHeap = BinHeap()
myHeap.insert(9)
myHeap.insert(1)
myHeap.insert(5)
assert myHeap.delMin() == 1
myHeap.insert(2)
myHeap.insert(7)
assert myHeap.delMin() == 2
assert myHeap.delMin() == 5
def testDupes(self):
myHeap = BinHeap()
myHeap.insert(9)
myHeap.insert(1)
myHeap.insert(8)
myHeap.insert(1)
assert myHeap.currentSize == 4
assert myHeap.delMin() == 1
assert myHeap.delMin() == 1
assert myHeap.delMin() == 8
def testBuildHeap(self):
myHeap = BinHeap()
myHeap.buildHeap([9,5,6,2,3])
f = myHeap.delMin()
# print("f = ", f)
assert f == 2
assert myHeap.delMin() == 3
assert myHeap.delMin() == 5
assert myHeap.delMin() == 6
assert myHeap.delMin() == 9
if __name__ == '__main__':
suite = unittest.makeSuite(TestBinHeap)
unittest.TextTestRunner().run(suite)
node.py
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
ordered linked list.py
from node import Node
class OrderedList(object):
def __init__(self):
""" Constructs an empty unsorted list.
Precondition: none
Postcondition: Reference to empty unsorted list returned.
"""
self._head = None
self._tail = None
self._size = 0
self._current = None
self._previous = None
self._currentIndex = 0
def search(self, targetItem):
""" Searches for the targetItem in the list.
Precondition: none.
Postcondition: Returns True and makes it the current item if targetItem is in the list;
otherwise False is returned.
"""
def searchHelper():
""" Recursive helper function that moves down the linked list.
It has no parameters, but uses self._current, self._previous, and
self._currentIndex."""
# ADD CODE HERE
pass
# START OF SEARCH - DO NOT MODIFY BELOW CODE
if self._current != None and self._current.getData() == targetItem:
return True
self._previous = None
self._current = self._head
self._currentIndex = 0
return searchHelper() # Returns the result of searchHelper
## NON-RECURSIVE CODE WE ARE REPLACING
## def search(self, targetItem):
## """ Searches for the targetItem in the list.
## Precondition: none.
## Postcondition: Returns True and makes it the current item if targetItem is in the list;
## otherwise False is returned.
## """
## if self._current != None and self._current.getData() == targetItem:
## return True
##
## self._previous = None
## self._current = self._head
## self._currentIndex = 0
## while self._current != None:
## if self._current.getData() == targetItem:
## return True
## elif self._current.getData() > targetItem:
## return False
## else: #inch-worm down list
## self._previous = self._current
## self._current = self._current.getNext()
## self._currentIndex += 1
## return False
def add(self, newItem):
""" Adds the newItem to is sorted spot in the list.
Precondition: newItem is not in the list.
Postcondition: newItem is added to the list.
"""
if self.search(newItem):
raise ValueError("Cannot not add since item is already in the list!")
temp = Node(newItem)
temp.setNext(self._current)
if self._previous == None:
self._head = temp
else:
self._previous.setNext(temp)
if self._current == None:
self._tail = temp
self._size += 1
def remove(self, item):
""" Removes item from the list.
Precondition: item is in the list.
Postcondition: Item is removed from the list.
"""
if not self.search(item):
raise ValueError("Cannot remove item since it is not in the list!")
if self._current == self._tail:
self._tail = self._previous
if self._current == self._head:
self._head = self._head.getNext()
else:
self._previous.setNext(self._current.getNext())
self._current = None
self._size -= 1
def isEmpty(self):
""" Checks to see if the list is empty.
Precondition: none.
Postcondition: Returns True if the list is empty; otherwise returns False.
"""
return self._size == 0
def length(self):
""" Returns the number of items in the list.
Precondition: none.
Postcondition: Returns the number of items in the list.
"""
return self._size
def index(self, item):
""" Returns the position of item in the list.
Precondition: item is in the list.
Postcondition: Returns the position of item from the head of list.
"""
if not self.search(item):
raise ValueError("Cannot determine index since item is not in the list!")
return self._currentIndex
def pop(self, *pos):
""" Removes and returns the item at position pos of the list.
Precondition: position pos exists in the list.
Postcondition: Removes and returns the item at position pos of the list.
"""
if len(pos) == 0:
pos = self._size - 1
elif len(pos) != 1:
raise TypeError("Too many parameters to pop")
else:
pos = pos[0]
if not isinstance(pos, int):
raise TypeError("Position must be an integer!")
if pos >= self._size or pos < 0:
raise IndexError("Cannot pop from index", pos, "-- invalid index!")
self._current = self._head
self._previous = None
for count in range(pos):
self._previous = self._current
self._current = self._current.getNext()
if self._current == self._tail:
self._tail = self._previous
if self._current == self._head:
self._head = self._head.getNext()
else:
self._previous.setNext(self._current.getNext())
returnValue = self._current.getData()
self._current = None
self._size -= 1
return returnValue
def __str__(self):
""" Returns a string representation of the list with a space between each item.
Precondition: none
Postcondition: Returns a string representation of the list with a space between each item.
"""
def strHelper(current):
if current == None:
return ""
else:
return str(current.getData()) + " " + strHelper(current.getNext())
resultStr = "(head) " + strHelper(self._head) + "(tail)"
return resultStr
## def __str__(self):
## """ Removes and returns the item at position pos of the list.
## Precondition: position pos exists in the list.
## Postcondition: Removes and returns the item at position pos of the list.
## """
## resultStr = "(head)"
## current = self._head
## while current != None:
## resultStr += " " + str(current.getData())
## current = current.getNext()
## return resultStr + " (tail)"
if __name__ == '__main__':
myList = OrderedList()
assert myList.search('a') == False
myList.add('3')
myList.add('5')
myList.add('7')
assert myList.search('1') == False
assert myList.search('3') == True
assert myList.search('4') == False
assert myList.search('5') == True
assert myList.search('6') == False
assert myList.search('7') == True
assert myList.search('8') == False
print("ALL SEARCH TESTS PASSED!!!")
list tester.py
from ordered_linked_list import OrderedList
def main():
myList = OrderedList()
while True:
print(" Ordered List Tester Menu")
print("a - add")
print("r - remove(item)")
print("i - index(item)")
print("p - pop()")
print("pp - pop(position)")
print("s - search(item)")
print("l - length")
print("x - eXit")
print(" The current list is:", str(myList))
command = input(" Enter your choice: ").lower()
if command == 'a':
item = input("Enter item to add: ")
myList.add(item)
elif command == 'r':
item = input("Enter item to remove from list")
myList.remove(item)
elif command == 'i':
item = input("Enter item to determine index")
index = myList.index(item)
print("The item is at index:",index)
elif command == 'p':
item = myList.pop()
print("The item popped from the tail was:",item)
elif command == 'pp':
index = eval(input("Enter index to pop from:"))
item = myList.pop(index)
print("The item popped from the index was:",item)
elif command == 's':
item = input("Enter item to search for ")
found = myList.search(item)
print("The item search result:",found)
elif command == 'l':
print("The length of the list is:",myList.length())
elif command == 'x':
break
else:
print(" Invalid command only 'a', 'r', 'i', 'p', 'pp', 's', 'l', 'x' are valid ")
main()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.