Description
Question 1 (10 points)
You have list of Agile story statuses (“Ready”, “In Progress”, “Blocked”,
“Completed”). You would like to store these values in your application and they
will be accessed and searched several times but they won’t be changed. Which
built-in data structure can be used? List or Tuple? And Why?
Question 2 (10 points)
In the Queue implementation that was shown in the class, write delete() python
function to delete an item with specific value. Your function should access
elements in the queue using enqueue() and dequeue() functions only. Refer to
the enqueue() and dequeue() implementations that were demoed in the class.
Question 3 (10 points)
Develop python function that can be called to sort unsorted linked list in
ascending order of the data values in the Nodes.
– Use the Linked List implementation shown in the lecture.
– Your function should be named sort(self) and should be added to the
Linked List class
– Don’t add any additional pointers to the Linked List class (other than the
head variable).
– Don’t use any built-in sort() functions provided by Python.
Question 4 (10 points)
Write Python function to delete set of keys from a dictionary. Your function
should accept list of the keys to be deleted and the dictionary
delete_keys([“key1”,”key2”], dictionary)
Question 5 (10 points)
Develop Python function to remove duplicates from Singly Linked List (unsorted).
Use the Linked List implementation introduced in the class materials.
Question 6 (20 points)
Build a data structure named “Reverse Linked List”. This data structure should
have only two attributes: data and previous.
Create a class named ReversedLinkedList that keeps track of the linked list using
one attribute, named “tail”.
Step 1: Empty Data Structure
Step 2: Insert Node with Data of 17
Step 3: Insert Node with Data of 12
Data = 12
Previous = Node with Data 17
Data = 17
Previous = None
Tail
Tail
None
Data = 17
Previous = None
Tail
Conduct the following:
1. Create the Data Structure (storage data type and the organizer)
2. Create the insert() function
3. Create the delete() function. Predict its behavior from the insertion flow
shown above.
4. Create search() function that returns true/false based on if given data point
is stored in any of the nodes (i.e. search (12) → true, search (20) → false)
Question 7 (20 points)
Create Custom Tri-tree in which every node contains up to three children: too-big,
big and small. Your root node is always the first node that gets inserted in an
empty tree.
– Too-big children is identified if the difference between the new data and the
node’s data is 10 or more (i.e. new data – current data >= 10)
– Big children is identified if the difference between the new data node and
current data is less than 10 (i.e. 0 =< new data – current data < 10)
– Small children is identified if the new data is less than the current data (i.e.
new data – current data < 0)
Step 1: Empty Tree
Step 2: Insert Node with Data of 20
Root
None
Data = 20
Too Big = None, Big =
None, Small is None
Root
Step 3: Insert Node with Data of 40
Data = 20
Too Big = 40, Big =
None, Small is None
Root
Too-big
Data = 40
Too Big = None, Big =
None, Small is None
Step 4: Insert Node with Data of 29
Data = 20
Too Big = 40, Big = 29,
Small is None
Root
Too-big
Data = 40
Too Big = None, Big =
None, Small is None
Data = 29
Too Big = None, Big =
None, Small is None
Big
Step 5: Insert Node with Data of 45
Data = 20
Too Big = 40, Big = 29,
Small is None
Root
Too-big
Data = 40
Too Big = None, Big =
45, Small is None
Data = 29
Too Big = None, Big =
None, Small is None
Big
Data = 45
Too Big = None, Big =
None, Small is None
Big
Step 6: Insert Node with Data of 32
Based on the examples above, conduct the following tasks:
1. Create the data structure (custom data type and the organizer)
2. Create the insert() function for this data structure
3. Create the delete () function for this data structure
4. Create traversal() function for this data structure. Your traversal should
start with the small child, then the root node, followed by big child, then
too-big child. Your function should be recursive.
Data = 20
Too Big = 40, Big = 29,
Small is None
Root
Too-big
Data = 40
Too Big = None, Big =
45, Small is 32
Data = 29
Too Big = None, Big =
None, Small is None
Big
Data = 45
Too Big = None, Big =
None, Small is None
Data = 32
Too Big = None, Big =
None, Small is None
Big
Small
Common Penalties:
▪ Your GitHub repository is not public: 100% reduction (won’t be graded)
▪ Late submissions on Canvas or GitHub: 100% reduction (won’t be graded)