Structures and Algorithms Homework #6 Solution

Question 1:




Define a LinkedQueue class that implements the Queue ADT.







Implementation Requirement: All queue operations should run in (1) worst-case.




Hint: You would want to use a doubly linked list as a data member.













Question 2:




Many programming languages represent integers in a fixed number of bytes (a common size for an integer is 4 bytes). This, on one hand, bounds the range of integers that can be represented as an int data (in 4 bytes, only 232 different values could be represented), but, on the other hand, it allows fast execution for basic arithmetic expressions (such as +, -, * and /) typically done in hardware.




Python and some other programming languages, do not follow that kind of representation for integers, and allows to represent arbitrary large integers as int variables (as a result the performance of basic arithmetic is slower).




In this question, we will suggest a data structure for positive integer numbers, that can be arbitrary large.




We will represent an integer value, as a linked list of its digits.




For example, the number 375 will be represented by a 3-length list, with 3, 7 and 5 as its elements.




header trailer







3 7 5













Note: this is not the representation Python uses. Complete the definition of the following Integer class:




class Integer:

def __init__(self, num_str):




Initializes an Integer object representing the value given in the string num_str'''



def __add__(self, other):




Creates and returns an Integer object that represent the sum of self and other, also of type Integer'''



def __repr__(self):




Creates and returns the string representation of self'''
For example, after implementing the Integer class, you should expect the following behavior:



n1 = Integer('375')



n2 = Integer('4029')



n3 = n1 + n2



n3



4404




Note: When adding two Integer objects, implement the “Elementary School” addition technique. DO NOT convert the Integer objects to ints, add these ints by using Python + operator, and then convert the result back to an Integer object. This approach misses the point of this question.




Extra Credit:




Support also the multiplication of two Integer objects (by implementing the “Elementary School” multiplication technique):




def __mul__(self, other):




Creates and returns an Integer object that represent the multiplication of self and other, also of type Integer'''
Question 3:




In this question, we will suggest a data structure for storing strings with a lot of repetitions of successive characters.




We will represent such strings as a linked list, where each maximal sequence of the same character in consecutive positions, will be stored as a single tuple containing the character and its count.




For example, the string “aaaaabbbaaac” will be represented as the following list:




header trailer







(‘a’, 5) (‘b’, 3) (‘a’, 3) (‘c’, 1)













Complete the definition of the following CompactString class:




class CompactString:

def __init__(self, orig_str):




Initializes a CompactString object representing the string given in orig_str'''



def __add__(self, other):




Creates and returns a CompactString object that represent the concatenation of self and other, also of type CompactString'''



def __lt__(self, other):




returns True if”f self is lexicographically less than other, also of type CompactString'''



def __le__(self, other):




returns True if”f self is lexicographically less than or equal to other, also of type CompactString'''



def __gt__(self, other):




returns True if”f self is lexicographically greater than other, also of type CompactString'''



def __ge__(self, other):




returns True if”f self is lexicographically greater than or equal to other, also of type CompactString'''



def __repr__(self):




Creates and returns the string representation (of type str) of self'''
For example, after implementing the CompactString class, you should expect the following behavior:




s1 = CompactString('aaaaabbbaaac')



s2 = CompactString('aaaaaaacccaaaa')



s3 = s2 + s1 #in s3’s linked list there will be 6 ’real’ nodes



s1 < s2



False




Note: Here too, when adding and comparing two CompactString objects, DO NOT convert the CompactString objects to strs, do the operation on strs (by using Python +, <, , <=, = operators), and then convert the result back to a CompactString object. This approach misses the point of this question.




Question 4:




In this question, we will demonstrate the difference between shallow and deep copy. For that, we will work with nested doubly linked lists of integers. That is, each element is an integer or a DoublyLinkedList, which in turn can contain integers or DoublyLinkedLists, and so on.

Implement the following function:



def copy_linked_list(lnk_lst)




The function is given a nested doubly linked lists of integers lnk_lst, and returns a shallow copy of lnk_lst. That is, a new linked list where its elements reference the same items in lnk_lst.




For example, after implementing copy_linked_list, you should expect the following behavior:

lnk_lst1 = DoublyLinkedList()



elem1 = DoublyLinkedList()



elem1.add_last(1)



elem1.add_last(2)



lnk_lst1.add_last(elem1)



elem2 = 3



lnk_lst1.add_last(elem2)



lnk_lst2 = copy_linked_list(lnk_lst1)



e1 = lnk_lst1.first_node()



e1_1 = e1.data.first_node()



e1_1.data = 10



e2 = lnk_lst2.first_node()



e2_1 = e2.data.first_node()



print(e2_1.data)



10

Now, implement:






def deep_copy_linked_list(lnk_lst)




The function is given a nested doubly linked lists of integers lnk_lst, and returns a deep copy of lnk_lst.

For example, after implementing deep_copy_linked_list, you should expect the following behavior:

lnk_lst1 = DoublyLinkedList()



elem1 = DoublyLinkedList()



elem1.add_last(1)



elem1.add_last(2)



lnk_lst1.add_last(elem1)



elem2 = 3



lnk_lst1.add_last(elem2)



lnk_lst2 = deep_copy_linked_list(lnk_lst1)



e1 = lnk_lst1.first_node()



e1_1 = e1.data.first_node()



e1_1.data = 10



e2 = lnk_lst2.first_node()



e2_1 = e2.data.first_node()



print(e2_1.data)



1




Note: lnk_lst could have multiple levels of nesting.

Question 5:




In this question, we will implement a function that merges two sorted linked lists:




def merge_linked_lists(srt_lnk_lst1, srt_lnk_lst2)




This function is given two doubly linked lists of integers srt_lnk_lst1 and




srt_lnk_lst2. The elements in srt_lnk_lst1 and srt_lnk_lst2 are sorted.




That is, they are ordered in the lists, in an ascending order.




When the function is called, it will create and return a new doubly linked list, that contains all the elements that appear in the input lists in a sorted order.

For example:




if srt_lnk_lst1= [1 <-- 3 <-- 5 <-- 6 <-- 8],

and srt_lnk_lst2=[2 <-- 3 <-- 5 <-- 10 <-- 15 <-- 18],

calling: merge_linked_lists(srt_lnk_lst1, srt_lnk_lst2), should create and return a doubly linked list that contains:




[1 <-- 2 <-- 3 <-- 3 <-- 5 <-- 5 <-- 6 <-- 8 <-- 10 <-- 15 <-- 18].







The merge_linked_lists function is not recursive, but it defines and calls merge_sublists - a nested helper recursive function.




Complete the implementation given below for the merge_linked_lists function:




def merge_linked_lists(srt_lnk_lst1, srt_lnk_lst2):




def merge_sublists( ___________________________ ):




______________________________________________




______________________________________________




______________________________________________




______________________________________________




______________________________________________







return merge_sublists( ______________________________ )







Notes:




You need to decide on the signature of merge_sublists.



merge_sublists has to be recursive.



An efficient implementation of merge_sublists would allow



merge_linked_lists to run in linear time. That is, if & and ' are the sizes of the input lists, the runtime would be ( & + ').