Analyse complexity and performance of their associated algorisms. • Apply abstract data types to programming practices. • Describe the concept, application, and specification of an ADT and employ classes to encapsulate ADTs. • Describe the general principles of algorithm complexity and performance.
CSP2348D Assignment 2, Trimester 1, 2021 CSP2348D Assignment 2, Trimester 1, 2021 CSP2348D Data Structures Assignment 2: A Mini Team Project - Algorithm Design, Analysis & Implementation Objectives from the Unit Outline • Analyse complexity and performance of their associated algorisms. • Apply abstract data types to programming practices. • Describe the concept, application, and specification of an ADT and employ classes to encapsulate ADTs. • Describe the general principles of algorithm complexity and performance. General Information: • This is a mini programming project, requiring up to two students to work as a team to complete it. It consists of six questions. You are required to do not only algorithm complexity analysis (to part of the questions), but also an implementation using either Python or Java programming language. (Note: if you wish to use a programming language other than Python or Java, please let your tutor know beforehand, and you may be required to demonstrate your work in the end). • It is your responsibility to form your team/group. Please send the details of your team members (i.e., the student IDs and names) to your tutor by the end of week 9. However if you really prefer to work individually, you may do so but no workload is to be reduced. • Algorithm complexity analysis is one of the most important skills covered by this unit. It can be done in either or both of theoretical algorithm analysis and experimental studies. The theoretical analysis is generally conducted by applying asymptotic theory/methods, such as in O-notation, etc., to the algorithm’s complexity function, which reflects the number of basic operations the algorithm has to execute over the input size, therefore to estimate the growth rate of the function. On the other hand, the experimental studies require implementation of the algorithm/s, thus to reveal the growth trend of the complexity function/s. • The first four questions are closely related, requiring array-based searching and/or sorting algorithm design and/or implementation skills. Q1 requests you design and implement an array-based sorting algorithm using specific sorting strategy. Q2~Q4 are for theoretical analysis and experimental study for array-based sorting algorithms. Part of the questions also requires algorithm analysis using big-O notation. The 5th question requires you design and implement part of the application scenario using SLL to represent the required information. Part of the codes has been completed. You are requested to complete the rest. The 6th question requires you modify an existing algorithm and then convert it into Python (or Java) code to implement specific application scenarios using binary tree data structure. Due: Friday in 2nd last teaching week, Trimester 1, 2021 @ 5:00 pm (see unit Schedule) Mark: 100 marks (which will then be converted to 30% of unit mark) CSP2348D Assignment 2, Trimester 1, 2021 Due @ 5:00 PM on Friday last teaching week, Trimester 1, 2021 Page 2 Main assignment document format requirement: Must contain Cover page Must show assignment title, student IDs and name/s of your team, due date etc. Executive Summary (optional) This should represent a snapshot of the entire report that your tutor will browse through and should contain the most vital information needed. Table of Contents (ToC) This must accurately reflect the content of your report and should be generated automatically in Microsoft Word with clear page numbers. Introduction Introduce the report, define its scope and state any assumption; Use in- text citation/reference where appropriate. Main body The report should contain (but not limited to): • Understanding of concepts/techniques involved in the report. • Any strategies used to solve the problems (e.g., an approach to develop a solution?) • The questions being solved/answered, e.g., Q1&Q3: must have: (i) key algorithm/s (in pseudo codes); (ii) algorithm analysis (if applicable); and, (iii) screen shots (showing execution results of the codes, at least one screenshot per function); Q5: algorithms and analysis using O-notation; screen snapshots of execution of the code (at least one snapshot per method to show the running result of your code); Q6: key screen snapshots of execution of the code (at least one snapshot for b), c) and d)); • Comment/Discussion or a critique of the solution developed /achieved, etc. • No Python/Java code be attached in body of the report (they should be saved as separate runnable codes and submitted as separate files). Conclusion Outcomes or main works done in this assignment. References A list of end-text reference, if any, formatted according to the ECU requirements using the APA format (Web references are also OK). Other requirement The report should be no more than 10 pages (excluding references, snapshots and diagrams). The text must use font Times New Roman and be not smaller than 12pt. Submission Instructions • Submit your Assignment 2 via Blackboard electronic assessment submission facility. For a detailed submission procedure, please refer to “How to submit your Assignment online” item in the Assessment section of this unit website. • Your submission should include the assignment main document (i.e., a report) and your Python (or Java) source codes. The main assignment document must be in report style, in Word or PDF format (see detailed format requirement above). Pages must be numbered. Your source code file/s must be runnable. • One submission per team - Your submission should be in a single compressed file (.zip), which contains your mini project report and source code file/s. Please name the zip file as
_< team-leader’s="" full="" name="">_A2_CSP2348.zip. • Remember to keep the copy of your assignment. No hard copy is required. • Your attention is drawn to ECU rules governing cheating and referencing. In general, cheating is the inclusion of the unacknowledged work of another person. Plagiarism (presenting other people's work and ideas as your own) will result in a Zero mark. • ECU rules/policies will apply for late submission of this assignment. CSP2348D Assignment 2, Trimester 1, 2021 Due @ 5:00 PM on Friday last teaching week, Trimester 1, 2021 Page 3 Background Information Arrays, linked lists and binary trees are typical data structures that are frequently used in many applications. While an array is a static data structure, linked lists and binary trees are among the most important yet simplest dynamic data structures. Many applications employ these data structures to model the applications scenarios. An array is a random-access structure. An array component can be accessed using a unique index in constant time. This property makes array the most effective data structure in term of component access; therefore the most frequently used data structure. A linked list is a sequential data structure, consisting of a sequence of nodes connected by links. Each node contains a single element, together with links to one or both neighbouring nodes (depending on whether or not it is an SLL or DLL). To access a linked list node, you must search it through the header of the linked list. Linked list is the simplest yet the most important dynamic data structures. A binary tree is a non-sequential dynamic data structure. It consists of a header, plus a number of nodes connected by links in a hierarchical way. The header contains a link to a node designated as the root node. Each node contains an element, plus links to at most two other nodes (called its left child and right child, respectively). Tree elements can only be accessed by way of the header. This assignment focuses on algorithm design, analysis, and implementation using array, SLL and binary tree data structures. While all questions are of equal importance, pay more attention to Q5 and Q6 as these questions enable you practise using typical linked list and binary tree based algorithms (e.g., SLL creation and data/link manipulation, binary tree traversals and their applications, etc.). (Go to next page) CSP2348D Assignment 2, Trimester 1, 2021 Due @ 5:00 PM on Friday last teaching week, Trimester 1, 2021 Page 4 Tasks Q1: design, analyse and write code/s to implement the Bubble sort algorithm Like Insertion-sort and Selection-sort algorithms, the Bubble-sort is one of the key elementary array- sorting algorithms. Its sorting strategy is as below: For a given array of n (comparable) elements, the algorithm scans the array n-1 times, where, in each scan, it compares the current element with the next one and swaps them if they are not in the required order (e.g., in ascending order, as usual). Based on this principle, do the following (assuming you are given an array of n integers): (i) Write the bubble sort algorithm (in pseudo code), which takes an array as input; Once this is done, (a) analyse your algorithm using O-notation by two ways, i.e., - by counting the number of comparisons; and - by counting the number copying operations; (b) convert your algorithm to Python (or Java) code, and test your code using an array of some 20 elements. (ii) Observe that, after the scanning the array for k (k = 1, 2, …) times, the top-k greatest values will be in their correct positions (of the sorted array). As such, when scanning the array for the (k+1)th time, it is not necessary to scan the full array (but a sub-array