CSP2348 Data Structures Assignment 2

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 one of 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 Java implementation using array, SLL and binary tree data structures. While all questions are of equal importance, pay more attention to Q2 and Q3 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.).

Q1). Array Application Programming:

A tiny programming project mimicking Lottos award checking system

A tiny Lotto system allows up to 1000 people play lotto with it. To play, each player is assigned an ID number (1 ID number 1000). Each player selects 6 distinct integer numbers from a barrel of 45 numbers (i.e., all integers are between 1 and 45, inclusive) as his /her game-numbers. All players gamenumbers are stored in a tiny database which, in this case, is replaced by a Java array, lotto[1000][6]. That is, for each player with ID number i, his/her game-numbers are stored in array lotto[i-1][05].

The tiny lotto system has three functions:

(1) The system can generate a sequence of numbers, called winning numbers, consisting of 6 distinct integers. Each winning number is also from the same barrel of 45 numbers (i.e., 1 winning number 45). The winning numbers can be randomly generated (or manually input) and then stored in the system;

(2) The system can check and calculate the total number of winners of each class, therefore generate a statistic table, as below:

Winners statistics: Winner class Total number of the winners
1st class
2nd class
3rd class
4th class

Notes:
A 1st class winner is one whose game-numbers match all 6 winning numbers;
A 2nd class winner is one whose game-numbers match any 5 winning numbers;
A 3rd class winner is one whose game-numbers match any 4 winning numbers;
A 4th class winner is one whose game-numbers match any 3 winning numbers.

(3) The system allows individual player check whether or not he/she is a lotto winner. When the player input his ID number k (1k1000), the system checks whether or not the player wins the lotto. That is, if his/her gamenumbers (stored in lotto[k-1][05] ) match

(a) all 6 winning numbers, the system prints his/her game-numbers in sequence, and then prints you are a top class winner, congratulations!

(b) any 5 winning numbers, the system prints his/her game-numbers in sequence, and then prints you are a 2nd class winner, congratulations!

(c) any 4 winning numbers, the system prints his/her game-numbers in sequence, and then prints you are a 3rd class winner, congratulations!

(d) any 3 winning numbers, the system prints his/her game-numbers in sequence, and then prints you are a 4th class winner, congratulations!

(e) less than 3 winning numbers, the system prints his/her game-numbers in sequence, and then prints Thanks for playing lotto. Good luck next time!

Your Task:

Design algorithms and/or write Java program/s to implement the above tiny Lotto system. To improve the systems performance, you are requested to

• sort individual game-numbers for each player; and
• use two different methods to implement the functions 2 and 3:
  • Method 1: it uses normal array searching algorithms (e.g., linear or binary search algorithms) to implement the matching between game-numbers and winning-numbers; and
  • Method 2: it matches the two sorted arrays (i.e., one containing the players game-numbers and the other containing the winning numbers) by sequentially comparing components of the two arrays (i.e., a scanning technique similar to that of the arrays-merging-algorithm, refer to Module 3).
• Compare the complexities of the above two methods in the step (ii) using O-notations .

To reduce your workload, a Java method is given in Appendix A that demonstrates how to randomly generate all players lotto data, i.e., gamenumbers, and store them in a Java array lotto[1000][6]. (You may modify the code and then include it as a part of your code/s)

Q2). Linked-list Programming:

SLL deletion and reverse operations

A unit_list class has been given in Workshop 05. The class uses an SLL to represent a list of student assessment results of a unit. Each SLL node contains a record of one student's assessment results. That is, it stores a student ID followed by the marks of three assessment components (A1_result, A2_result, and exam_result), all are in integers. For convenience, student information stored in the SLL is in ascending order by the student_ID field. The class given shows the technique of traversing an SLL, searching an SLL and inserting a node into the SLL.

Your Task:

(1) Deletion of an students information:

private static void delete_unit_result(unit_list u_list, int ID) { // your work here……. }

When being given a student ID (as input), the method searches the SLL to see if the student with that ID existed in the SLL or not. If it is existed, the method deletes the student information (i.e., the node in the SLL) and keeps all other student information in the SLL unchanged.

Note that the method requires no return (i.e., void return). As such, you should make sure that the first node of the SLL is not physically deleted from the SLL, even if it might be logically deleted (why?).

(2) Display/print the student information in descending order on the Student ID field:

private static void reverse_print_unit_result(unit_list u_list) { // your work here……. }

This method displays/prints all student information in descending order on student ID field. Please note that, to keep the unit_class work properly you should not destroy the original SLL (why?). To this, you may create a new SLL which is the reverse of the original SLL (or if you have to destroy the original SLL, make sure your recover it afterwards).

(3) Analyse the above methods using O-notation.

Q3). Binary tree traversal:

Print leaf and non-leaf node and tree-height

A Java code is given in TreeTest.java in Module 6 (see Task 3 of Workshop 6) It prints the Pre-order, In-order and Post-order traversal sequences of a given binary tree.

Your Task:

Analyze this code and modify it so that it would:

• print the Pre-order, In-order and Post-order traversal sequences of the given binary tree (already implemented);
• print all leaf nodes only (of the tree);
• print non-leaf nodes only (of the tree);
• print the height of the tree.

Test your code by creating a more complicated BST, e.g., using the following array to replace the array in the third line of the main method:

int [] a = {49, 76, 67, 29, 75, 18, 4, 83, 87, 40, 80, 46, 42, 43, 45, 41};