SIT221 Data Structures and Algorithms Trimester 2, 2019 Practical Task 6.2 (Credit Task) Submission deadline: 10:00am Monday, September 2 Discussion deadline: 10:00am Saturday, September 14 General Instructions In this task, answer all the following questions and complement each answer with a detailed explanation. 1. After hearing about a Binary Max‐Heap data structure, Johnny English decides to implement it for his supper‐duper algorithm. However, as he was not paying enough attention in class, his implementation of the DownHeap procedure (also widely known in the literature as Max‐Heapify) is not absolutely correct. He gave us the following pseudocode of his implementation: Function JE_DownHeap(index x):If ( H[Left(x)].key > H[x].key ){Swap elements H[x] and H[Left(x)]JE_DownHeap(Left(x))}ElseIf ( H[Right(x)].key > H[x].key ){Swap elements H[x] and H[Right(x)]JE_DownHeap(Right(x))}Your task is to give an example of a max‐heap for which the above JE_DownHeap procedure fails. More specifically, you need to propose a heap where the root 1 is the only node breaking the essential Max‐Heap Property so that running the above procedure JE_DownHeap(1) does NOT result in a valid max‐heap. Use your instance to clearly illustrate how such heap may look like. You must draw the heap before and after running JE_DownHeap(1). Note that your instance can be made quite small. 2. Assume now that Johnny English has eventually fixed the aforementioned problem and developed a correct implementation of a max‐heap that provides all the standard operations such as: ‐ DeleteMax, Insert(K), IncreaseKey(X, K), in a logarithmic log time; and ‐ Max, in a constant 1 time, where is the number of stored elements. Johnny English wants to add a new capability to this max‐heap .Specifically, he would like to implement a DeleteElement(X) operation that removes element H[x] from the max‐heap consisting of elements in a logarithmic log time. Note that the H[x] does not need to be the maximum‐key element in .Also, naturally, has to maintain the Max‐Heap Property after deletion of H[x]. Your task is to help Johnny English by providing a pseudocode of such a DeleteElement(X) operation with a brief analysis of its running time as function of elements. 3. Johnny English knows that the maximum element of a binary max‐heap can be obtained by means of Maxoperation in a constant 1 time. He however wants you to develop an efficient method (in pseudocode) that finds the maximum element in log time, where 1 Remember that both insertion and removal in a binary max‐heap of size takes a log time. SIT221 Data Structures and Algorithms Trimester 2, 2019 Further Notes You may find exploring the content of chapter 9.3 of the course book “Data Structures and Algorithms in Java” by Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser (2014) useful to solve these tasks. You may access the book on‐line for free from the reading list application in CloudDeakin available in 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 solutions are hand‐written, do not forget to bring them with you. Cloud students must record a short video explaining their work and use a sort of white‐board, e.g. a graphical editor, or a scanned document with the answers. Answer all additional (theoretical) questions that your tutor may ask you. Questions are likely to cover lecture notes, so attending (or watching) lectures should help you with this compulsory interview part. 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 this task that may impact your performance and your final grade in 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. 本团队核心人员组成主要包括BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论