Question 1
You can refer to SLinkedList.py to develop your codes.
(a) You must create a Python program to implement the linear list by a doubly linked list.
You need to implement the following requirement of ADT of a Linear List and other operations which should contain the follow methods:
isEmpty(): return true iff the list is empty, false otherwise size(): return the size of the list get(i): return the i th element of the list indexOf(el): return the index of the first occurrence of el in the list, return -1 if x is not in the list
remove(index): remove and return the indexth element, elements with higher index have their index reduced by 1 removeNode(Removekey): remove the node with given element, elements with higher index have their index reduced by 1
add(theIndex, x): insert x as the indexth element, elements with theIndex >= index have their index increased by 1
addAtHead(x): inert the x at the beginning addAtTail(x): inert the x at the end listprint(): print the list getFromBack(i): get i th element counting from the back of the list. E.g. for list: 2, 3, 5, 8, 9, getFromBack(1) will give 8 listprintFromBack(): print the linear list from the back to the front
You should start with the following definition of the Node and the DLinkedList: class Node:
def __init__(self, el = None, n = None, p=None):
self.next = n self.prev = p self.element = el
class DLinkedList: def __init__(self): self.head = None self.tail = None
The program should contain the following main to test and run:
#Testing Program def main():
list1 = DLinkedList() print(list1.isEmpty()) print("Size of list: ", list1.size()) list1.addAtHead("Fri") list1.addAtHead("Thu") list1.addAtHead("Wed") list1.addAtHead("Tue") list1.addAtHead("Mon") list1.addAtHead("Sun")
print("List from the front", end=": ") list1.listprint()
print("List from the back", end=": ") list1.listprintFromBack()
print("Get from Index 2...", list1.get(2)) print("Remove Index 1.. ", list1.remove(1)) print("List from the front", end=": ") list1.listprint()
print("List from the back", end=": ") list1.listprintFromBack()
print("Index of Sun:", list1.indexOf("Sun")) print("Index of Wed:", list1.indexOf("Wed")) print("Size of list: ", list1.size()) print("Get from Index 1...", list1.get(1)) print("Try to add new node Bday") list1.add(2, "Bday")
print("List from the front", end=": ") list1.listprint()
print("List from the back", end=": ") list1.listprintFromBack()
print("Try to Remove a node") list1.removeNode("Wed")
print("List from the front", end=": ") list1.listprint()
print("List from the back", end=": ") list1.listprintFromBack()
print("getFromBack(3)", list1.getFromBack(3))
if __name__ == "__main__":
main()
When the completed program is executed, it should give the following outputs:
> python DLinkedList.py
True
Size of list: 0
List from the front: Sun / Mon / Tue / Wed / Thu / Fri /
List from the back: Fri / Thu / Wed / Tue / Mon / Sun /
Get from Index 2... Tue
Remove Index 1.. Mon
List from the front: Sun / Tue / Wed / Thu / Fri /
List from the back: Fri / Thu / Wed / Tue / Sun /
Index of Sun: 0
Index of Wed: 2
Size of list: 5
Get from Index 1... Tue
Try to add new node Bday
List from the front: Sun / Tue / Bday / Wed / Thu / Fri /
List from the back: Fri / Thu / Wed / Bday / Tue / Sun /
Try to Remove a node
List from the front: Sun / Tue / Bday / Thu / Fri / List from the back: Fri / Thu / Bday / Tue / Sun / getFromBack(3) Tue
(b) In this linked list implemented by doubly linked list, what operation(s) are improved in time efficiency?
Question 2
It is known that a complete binary tree with the post-order traversal gives
x y * a b - + p q + 3 * /
(a) Draw the tree;
(b) Give the level-order traversal
(c) Give the arithmetical expression.
Question 3
You are required to create a class called Organization in Python. When this class is called, it stores the information about an organization and they can be sorted by its site number. (Note: You may use the method sort() in List available in Python without working out the sorting details.)
The class should contain the following instant variables:
Fields Datatype
id int
site_no int
name String
region String
city String
workers int
cost float
revenue float
industry String
The class contains the following main() function.
def main(): orgList =[]
orgList.append(Organization(123, 12, 'ABB', 'KO','Seoul', 100)) orgList.append(Organization(23, 23, 'JC MOVE', 'ML',
'Melbourne'))
orgList.append(Organization(25699, 7, 'Voma', 'FF', 'Berlin',
150, 225, 7600050, 'Electronics'))
orgList.append(Organization(123, 10, 'ENGG', 'PH','ML', 400,
50))
orgList.append(Organization(40, 30, 'MOBileTech', 'VN', 'HoNiu'))
orgList.append(Organization(25699, 6, 'MaxHome', 'LON',
'Walford', 100, 2935, 1609335, 'Construction')) orgList[0].displayEmployee() orgList[2].displayDetail() print(orgList[0])
print(f"Total Organizations {Organization.orgCount}") orgList.sort()
print("The Organization with the minimum site number is ", orgList[0])
print("The Organization with the maximum site number is ", orgList[-1])
When its main() called and executed, the following output is given.
Name : ABB , Rank: 12 , Employee: 100
ID:25699, Name:Voma, Site:7, Employee:150, Industry:Electronics, City: Berlin, cost:225, revenue:7600050 ID:123, Name:ENGG has :10 Sites
Total Organizations 6
The Organization with the minimum site number is ID:25699, Name:MaxHome has :6 Sites
The Organization with the maximum site number is ID:40, Name:MOBileTech has :30 Sites
Question 4
Part (a)
You are required to complete the complete the following Python programme, numberGrouping.py, so that it gives the outputs as expected. It will generate a list of integers and group them according to the requirements.
It contains 3 functions:
1) nUniqueRandom – it generates n unique random unique number a range of lower to upper number (including the lower and the upper). The default values of n =10, lower = 1 and upper 20 and it returns a list of number in ascending order.
Hint: using random.sample
2) getGroups - it generates 8 groups and each group has four items. The original list should be not changed in the order.
Hint: Python Random shuffle() Method.
https://www.w3schools.com/python/ref_random_shuffle.asp
3) showGroup – it shows the list in the required format.
Ref: Python Program to Access Index of a List Using for Loop https://www.programiz.com/python-programming/examples/index-for-loop
[ numberGrouping.py ] import random
def nUniqueRandom(n= 12, lower=1, upper=20):
# Add Code #
def getGroups(list1, noOfGroup):
# Add Code #
def showGroup(L):
# Add Code #
# Main
# https://www.geeksforgeeks.org/python-main-function/ def main(): nums1 = nUniqueRandom() print(nums1)
nums2 = nUniqueRandom(32, 1, 200) print(nums2)
team_grouping =getGroups(nums1,3) print(team_grouping) print(nums1) showGroup(team_grouping) team_grouping =getGroups(nums2,8) print(team_grouping) showGroup(team_grouping)
if __name__ == "__main__":
main()
Sample Outputs:
> python numberGrouping.py
[1, 4, 5, 7, 8, 12, 13, 16, 17, 18, 19, 20]
[1, 7, 12, 18, 20, 36, 41, 63, 70, 74, 80, 82, 87, 90, 97, 101, 102,
104, 111, 126, 128, 130, 141, 152, 157, 162, 172, 179, 182, 185,
189, 200]
[[13, 19, 18, 12], [16, 17, 20, 1], [5, 8, 4, 7]]
[1, 4, 5, 7, 8, 12, 13, 16, 17, 18, 19, 20]
Group 1: Teams: [13, 19, 18, 12]
Group 2: Teams: [16, 17, 20, 1]
Group 3: Teams: [5, 8, 4, 7]
[[90, 172, 36, 18], [200, 128, 152, 157], [7, 179, 102, 41], [130,
20, 141, 162], [80, 104, 82, 12], [182, 1, 111, 63], [185, 189, 126,
74], [70, 101, 87, 97]]
Group 1: Teams: [90, 172, 36, 18]
Group 2: Teams: [200, 128, 152, 157]
Group 3: Teams: [7, 179, 102, 41]
Group 4: Teams: [130, 20, 141, 162]
Group 5: Teams: [80, 104, 82, 12]
Group 6: Teams: [182, 1, 111, 63]
Group 7: Teams: [185, 189, 126, 74]
Group 8: Teams: [70, 101, 87, 97]
> python numberGrouping.py
[1, 2, 3, 5, 8, 10, 11, 13, 16, 17, 19, 20]
[14, 15, 21, 24, 27, 30, 31, 34, 37, 41, 50, 61, 70, 83, 98, 102,
104, 105, 108, 113, 114, 117, 127, 134, 141, 149, 154, 163, 168,
177, 190, 198]
[[3, 16, 13, 10], [19, 17, 1, 2], [5, 11, 8, 20]]
[1, 2, 3, 5, 8, 10, 11, 13, 16, 17, 19, 20]
Group 1: Teams: [3, 16, 13, 10]
Group 2: Teams: [19, 17, 1, 2]
Group 3: Teams: [5, 11, 8, 20]
[[154, 117, 14, 104], [70, 141, 149, 134], [102, 114, 30, 61], [127,
21, 15, 198], [163, 31, 108, 37], [27, 113, 50, 24], [98, 105, 34,
83], [168, 177, 190, 41]]
Group 1: Teams: [154, 117, 14, 104]
Group 2: Teams: [70, 141, 149, 134]
Group 3: Teams: [102, 114, 30, 61]
Group 4: Teams: [127, 21, 15, 198]
Group 5: Teams: [163, 31, 108, 37]
Group 6: Teams: [27, 113, 50, 24]
Group 7: Teams: [98, 105, 34, 83]
Group 8: Teams: [168, 177, 190, 41]
Part (b)
You are required to complete the complete the following Python programme, teams.py, so that it gives the outputs as expected. It will generate a list of integers and group them according to the requirements. I
You need to fill up 2 more functions:
4) getAbbv– Get the abbreviation of the given team name.
5) getTeamName - Get the team name of a team abbreviation.
The file teams_full.txt contains team name with tab separating the name and its abbreviation.
import csv
# Ref: Importing Data from Tab Delimited Files with Python # https://www.pluralsight.com/guides/importing-data-from-tabdelimited-files-with-python
# Ref: Python | Remove spaces from a string
# https://www.geeksforgeeks.org/python-remove-spaces-from-a-string/
def read_team_list(fname):
tnames = [] tabbvs = [] with open(fname, newline = '') as teams:
teams_reader = csv.reader(teams, delimiter='\t')
for team in teams_reader: #print(team) tabbvs.append(team[1]) tnames.append(team[0].lstrip(" ")) tabbvs.pop(0) tnames.pop(0)
return tabbvs, tnames
def getAbbv(team_name, team_abbvs, team_names):
# Add Code #
def getTeamName(team_abbv, team_abbvs, team_names):
# Add Code #
def main():
filename = 'teams_full.txt'
team_abbvs, team_names= read_team_list(filename)
print(team_abbvs[:5]) print(team_abbvs[27:33]) print(team_names[27:33])
print("The abbreviation of Brazil is "+ getAbbv("Brazil", team_abbvs, team_names))
print("The abbreviation of Tokyo is "+ getAbbv("Tokyo", team_abbvs, team_names))
(idx, name) = getTeamName("GER", team_abbvs, team_names)
print(f"GER is {name} in index {idx}")
(idx, name) = getTeamName("HKG", team_abbvs, team_names) print(f"HKG is {name} in index {idx}")
if __name__ == "__main__":
main()
Expected Outputs:
> python teams.py
['AFG', 'ALB', 'ALG', 'ASA', 'AND']
['BRA', 'VGB', 'BRU', 'BUL', 'BFA', 'BDI']
['Brazil', 'British Virgin Islands', 'Brunei', 'Bulgaria', 'Burkina
Faso', 'Burundi']
The abbreviation of Brazil is BRA
The abbreviation of Tokyo is NOT FOUND
GER is Germany in index 74
HKG is Hong Kong in index 86
Part (c)
Hence, with the above programmes, create a new python program teamGrouping.py to generate a random list of the teams from the given list of teams. It should give 32 teams randomly and group them into 8 groups.
The following are the suggested hints for your starting:
from teams import * from numberGrouping import *
def getGrouping(team_grouping, team_abbvs, team_names):
### def showGroupInfo(groupLists):
### def getGroupList(filename, NoOfTeams, NoOfGroups):
### def main():
### if __name__ == "__main__":
main()
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
