the full task sheet

 Practical Task 4.1   (Pass Task)

Submission deadline: 10:00am Monday, August 19  Discussion deadline: 10:00am Saturday, August 31

General Instructions  A skip‐list is a probabilistic linked‐list‐like data structure that expects, for an ordered sequence of   elements,  a  log  runtime complexity for basic operations such as searching, insertion and removal. Importantly, it  supports  a  quick  insertion  that  is  not  possible  for  a  simple  array.  Fast  operations  are made  possible  by  maintaining  a  linked  hierarchy  of  layered  linked‐list  subsequences,  with  each  successive  subsequence  skipping over fewer elements than the previous.

1. This  task  asks  you  to  conduct  a  small  research  about  this  data  structure.  You  can  find  its  detailed  explanation in chapter 10.4 of the course book “Data Structures and Algorithms in Java”. You, of course,  may explore and refer to any other resources covering this topic. We expect you to grasp the idea and  structure of a skip‐list along with standard operations on it. As the results of your study, you must be able  to answer the following questions and discuss the related issues:

‐ How exactly is a skip‐list constructed from a series of linked‐lists? What does each of the linked‐lists  constituting a skip‐list store?

‐ What is a height of a skip‐list? How can we determine the height when adding new elements?  ‐ What is the runtime complexity for searching, insertion, and removal operations on a skip‐list? What

does  it  mean  when  we  say  that  the  complexity  of  these  operations  is  ‘expected’? What  is  the  difference between an expected bound on runtime complexity and a worst‐case bound?

‐ Compare a skip‐list to other data‐structures that you should already know, e.g. sorted arrays, singly  and  doubly  linked  lists. What  are  the  advantages  and  disadvantages  of  a  skip‐list?  Compare  the  complexities of the basic operations offered by a skip‐list to those of the mentioned data structures.

‐ How exactly does each of the standard operations work? Here, you should be ready to explain the  sequence of actions required to perform searching, insertion, and removal from a skip‐list.

2. Solve the following numeric example. Given the following sequence of coin tosses, where H stands for  head and T stands for tails:

T  H  T  T  H  H  T  T  H  T  H  T  H  H  T  H  H  T  T  H  H  T  H  T  T  H  T  T  T  H  T  H  T  H  T  T  H  T  H  H  T  T.

Build a skip‐list containing the following values:

1   40   11   85   86   5   0   8.

Show the full state of the skip‐list after each insertion. Note that you must explicitly state the meaning  you attach to heads and tails at the start of your answer. Remember that you must start tossing the coin  from  left  side of  the sequence and may not need  to use all  the  tosses  to build  the skip‐list. You may  assume as a height resolution policy that we allow a tower to grow as long as heads (or tails, as both can  be  used  interchangeably)  keep  getting  returned  from  the  given  sequence, which  emulates  a  random  number generator.

Further Notes   You will  find the answer to this task by reading chapter 10.4 of the course book “Data Structures and

Algorithms in Java” by Michael T. Goodrich, Irvine Roberto Tamassia, and Michael H. Goldwasser (2014).  You may access the book on‐line  for  free from the reading  list application  in CloudDeakin available  in

SIT221 Data Structures and Algorithms     Trimester 2, 2019

2

Resources  Additional Course Resources  Resources on Algorithms and Data Structures    Course  Book: Data structures and algorithms in Java.

Marking Process and Discussion  To get this task completed, you must finish the following steps strictly on time:

 Submit your answers to the task via OnTrack submission system. You may submit a hand‐written and then  scanned document, but ensure that the text is very clear to read. Note that this is a theoretical task, thus  we do not expect you to write any program code.

 Meet with your marking tutor to explain your solutions. When the solution is hand‐written, do not forget  to bring it with you.

 Show to your tutor how the standard operations on a skip‐list are performed. Cloud students must record  a short video explaining their work on the numeric instance along with execution of searching, insertion  and removal operations based on the example.

 Answer all additional (theoretical) questions that your tutor may ask you. Please, come prepared so that  the class time is used efficiently and fairly for all the students in it. You should start your interview as soon  as possible as if your answers are wrong, you may have to pass another interview, still before the deadline.  Use available attempts properly.

Note  that we will  not  check your  solution after  the  submission deadline and will  not discuss  it  after  the  discussion deadline. If you fail one of the deadlines, you fail the task and this reduces the chance to pass the  unit.  Unless  extended  for  all  students,  the  deadlines  are  strict  to  guarantee  smooth  and  on‐time  work  through the unit.

Remember that this is your responsibility to keep track of your progress in the unit that includes checking  which tasks have been marked as completed in the OnTrack system by your marking tutor, and which are still  to be finalised. When marking you at the end of the unit, we will solely rely on the records of the OnTrack  system and feedback provided by your tutor about your overall progress and quality of your solutions.

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.