8006

i fucked up with that subject, Algorithms and Complexity Document Preview:

CAB301 Assignment 1Empirical Analysis of an Algorithmfor Inserting a Number Into a SetStudent name: (Student no. n1234567)Date submitted: 15 April 2018SummaryThis report summarises the outcomes of several experiments conducted to measure the timecomplexity of an algorithm for inserting a number into a set, where sets are represented asordered linked lists. The algorithm was implemented as a Python program and both thenumber of basic operations performed by the program and its execution time were mea-sured. The experimental results were found to be consistent with the theoretical predictionsfor this algorithm.1 Description of the AlgorithmThe algorithm of interest inserts a number into a set, assuming that sets are represented asordered linked lists [1,x2.3.3]. Insertions must preserve the list’s ordering and duplicatenumbers should not be inserted. Using ordered lists to represent sets, instead of unorderedones, reduces the average time required to insert a new number [1, Ex. 2.61].The algorithm required to do this is a common textbook example. Berman and Paulillustrate how insertion into an ordered list works with an example [2, pp. 44–45], althoughthey leave the algorithm itself “as an exercise” for the reader, as do Abelson and Sussman[1, Ex. 2.61]. The particular version of the algorithm used in this experiment is shown inFigure 1 on page 7. It is based on Schneider et al.’s explanation of how to insert an item ata particular point in a linked list [6, pp. 247–248].As usual in linked list algorithms, insertion of a new node at the beginning of the list(condition b in Figure 1) needs to be treated as a special case (statements c and d). Oth-erwise, however, the algorithm uses a loop (statements f and g) to search for the place toinsert the new node. The loop stops either when the end of the list is reached, or when anumber larger than the one we need to insert is encountered. Since we don’t want to insertduplicate numbers, a new…

Attachments:

CAB301-Ass1-S….pdfCAB301-Ass1-S….pdf