Rlab7

COSC 2436 – LAB7

Contents TITLE .............................................................................................................................................................. 1

TIME TO COMPLETE ...................................................................................................................................... 1

COURSE OBJECTIVES – LEARNING OUTCOME .............................................................................................. 1

LAB OBJECTIVES ............................................................................................................................................ 2

SKILLS REQUIRED........................................................................................................................................... 2

HOW TO DO EACH PART ............................................................................................................................... 2

REQUIREMENT lab5 ...................................................................................................................................... 3

HOW TO TURN IN THE LAB ........................................................................................................................... 3

HOW TO GRADE THE LAB .............................................................................................................................. 5

Note: in the instruction of the lab change “yourLastName” to your last name. In the example, change

Smith to your last name, change James Smith to your full name, change Mary Lane to the name that

users type in from the keyboard (if these words are in this instruction)

TITLE

Recursion Algorithm – Binary Search Tree

TIME TO COMPLETE

Two weeks

COURSE OBJECTIVES – LEARNING OUTCOME

[LO1] Provide UML class diagram and the code of data type classes Provide the pseudo-code or flowchart based on the requirement of a project before writing the code of the driver class. Also, can access data members of data type classes Describe and implement the inheritance relationship between super class and child classes. Can use abstract classes or interface and apply polymorphism to the real-life problem project [LO6]

Understand recursion and apply to determine and apply recursion algorithm to problems

[LO7] Describe and implement operations of Binary Search Trees [LO11] How to evaluate the performance of each operation algorithm of data structure type based on BigO and Density

LAB OBJECTIVES

-Complete the lab on time (Time Management)

-Can write the pseudo-code -Can provide UML of data type class -Can write comments in the program -Can write the code of data type classes including data members, no-argument constructor, parameter constructors, mutator methods, assessor methods, method toString and other methods -Can apply Inheritance concept to write the code of child classes that inherits data members, constructors and other methods from parent class -Can apply Polymorphism: using object of the parent class to point to object of child classes -Can organize the program with selection control structure: if..else, switch, do..while -Can create object and can access members of data type class -Can determine recursion algorithm to solve some small problems

-Learn how to create the object of Binary Search Tree structure

-Learn how to insert Nodes, fetch nodes, delete nodes and verify the Binary Search Tree is encapsulated and how

to show all nodes

-review how to access static methods from the other class

SKILLS REQUIRED

To this lab, students should review all the concepts required from the previous lab and add the following skills: -Learn how to use 4 steps to build up recursion algorithm then apply to write the recursion code -Learn how to create the data structure of type Binary Search Tree -Learn the algorithms and how to access the operations of Binary Search Tree, such as, insert, fetch, delete, update and showAll -How to verify Binary Search Tree structure is encapsulated -how to access static member of other class

HOW TO DO EACH PART

From now and on yourLastName will be changed to your last name Smith: change to your last name James Smith: change to your full name *Step1: -Create UML of data type classes: class Student and class Class -Read the requirement of each part; write the pseudo-code in a word document by listing the step by step what you suppose to do in main() and then save it with the name as Lab7_pseudoCode_yourLastName *Step2: -start editor eClipse, create the project → project name: FA2019_LAB7PART1_yourLastName or FA2019_LAB7PART2_yourLastNamee -add data type classes RecursionMethod_yourLastName (part 1) Student_yourLastName (re-use from lab6) -Add data structure BinarySearchTree_yourLastName(part2) -Add the driver class AccessStaticMethod_yourLastName(part1) FA2019_BinarySearchTreeDemo_yourLastName (part 2)

*Step3: Write the code of classes: -Re-use the code of data type classes from previous labs (class Student) -Write the code of BinarySearchTree_yourLastName: using the code on the page 394 – 396 for your reference and method showAll() on the page 406 Based on the pseudo-code write the java code of main() of the driver class

FA2019_ BinarySearchTreeDemo_yourLastName *Step4: compile and run the program *Step5: debug if there are any errors to complete the program

REQUIREMENT LAB7

LAB7 PART 1 DATA TYPE CLASS: class RecursionMethod_yourLastName. This is a special class that has no data members, no constructors, no mutator, no accessor method and no toString() method. It only includes 6 static recursion methods of the following:

n! Factorial of an integer n where n provided from the keyboard

an a power n, where a and n are int numbers provided from the keyboard

Sum (n) Sum(n) = 1 + 2 + 3 + .. + n where n is an int provided from the keyboard

Sum (m, n) Sum(m, n) = m + (m+1), (m+2) + … + n where m and n are int numbers provided from the keyboard

Fn Fibonacci sequence Fn = Fn – 1 + Fn-2; F0 = 0 and Fn1 = 1

GCD (n,m) The greatest common divisor (GCD) of two integers m and n; m > n where m, n are provided from the keyboard

DRIVER CLASS: class AccessStaticMethodDemo_yourLastName Provide the application AccessStaticMethodDemo_yourLastName that first display the menu to allow users to select any task. When the program completes one task, redisplay the menu to allow users to continue using the program until they select Exit AccessStaticMethod_Smith.java

1. n! (Factorial of an integer n) 2. an (a power n) 3. Sum(n) = 1 + 2 + 3 + .. + n 4. Sum(m, n) = m + (m+1), (m+2) + … + n 5. Fibonacci sequence Fn 6. GCD (The greatest common divisor of m and n) 0. Exit

For each selected task, display the message to ask the value of n (or values of m and n); calculate the result by accessing the static methods of class RecursionMethod_yourLastName. The output of each task in the following format: If selected task is 1 and n is 5 then the output is ----------------------------------------------

AccessStaticMethod_Smith.java

Factorial of the n = 5 is 120

----------------------------------------------

If selected task is 2 and the value of a is 3 and the value of n is 4 then the output is: ----------------------------------------------

AccessStaticMethod_Smith.java

Power 4 of the n = 3 is 81

----------------------------------------------

If selected task is 3 and the value n = 5 then the output is: ----------------------------------------------

AccessStaticMethod_Smith.java

Sum from 1 to n = 5 is 15

----------------------------------------------

If selected task is 4 and the value m = 3 and the value of n = 8 then the output is: ----------------------------------------------

AccessStaticMethod_Smith.java

Sum from m=3 to n=8 is 33

----------------------------------------------

If selected task is 5 and the value of n = 8 then the output is: ----------------------------------------------

AccessStaticMethod_Smith.java

Fibonacci at n = 10 is 55

----------------------------------------------

If selected task is 6 and value of m = 120 and n = 90 then the output is: ----------------------------------------------

AccessStaticMethod_Smith.java

Greatest Common Divisor (GCD) of 120 and 90 is 30

----------------------------------------------

LAB7 PART 2 DATA TYPE CLASS: Using the class Student_yourLastName from lab6 DATA STRUCTURE CLASS: BinarySearchTree_yourLastName (correction: line 110 return true; false; use the code on page 394 – 396 and showAll on page 406 Add the code to delete the root in 3 cases DRIVER CLASS Display the menu to allow users to select the following tasks: BINARY SEARCH TREE DEMO – JAMES SMITH

1. Insert 2. Fetch 3. Encapsulation 4. Update 5. Delete 6. Show all 0. EXIT

INSERT ONE STUDENT -Display message and read enough information to create one student -Insert this student to Binary Search Tree FETCH -Display message to ask for student id -If student with the entered student id is found, display the student information Otherwise display message “Student cannot be found”

ENCAPSULATION -Ask for information from the keyboard to create one student named as inputStudent -Insert inputStudent to the Binary Search tree -Read the student id of inputStudent to store to variable id -Ask for new last name from the keyboard then change last name of inputStudent -Fetch from Binary Search Tree a student with above id then store to fetchedStudent -Compare last name of inputStudent and last name of fetchedStudent. If they are the same display message “Binary Search Tree is NOT encapsulated”; otherwise display message “Binary Search Tree is encapsulated” UPDATE -Ask for the information of one student from the keyboard to create aStudent -Insert aStudent to Binary Search Tree -change the first name of aStudent -update aStudent with new first name to Binary Search Tree -if update success display message “The first name is changed”; otherwise display message: “Update not success” DELETE -Ask for a student id from the keyboard -Delete the student with entered id -If delete success display message “Student with the” + id + “ is deleted”; otherwise display message “delete not success” SHOW ALL Show all the nodes in the Binary Search Tree

HOW TO TURN IN THE LAB

Psuedo-code of main() of part1 and part 2 RecursonMethod_yourLastName.java AccessStaticMehod_yourLastName.java RecursonMethod_yourLastName.class AccessStaticMehod_yourLastName.class Student_yourLastName.java Class.java BinarySearchTree_yourLastName.java BinarySearchTreeDemo.yourLastName.java Student_yourLastName.class Class.class BinarySearchTree_yourLastName.class BinarySearchTreeDemo.yourLastName.class

HOW TO GRADE THE LAB

ITEMS SCORES

Turn in on time 3

PART1:

Factorial 1

an 1

sum of 1 to n 1

sum of m to n 1

nth term of Fibonacci sequence fn 1

GCD (m,n) 1

Handle the menu and the loop 0.5

Output correct format 1

Compile success and comment – access Static members correctly 3

PART2:

Data type class Student_yourLastName, class Class_yourLastName

Class about Binary Search Tree 1

-Add code for deleting the root in 3 cases 3

-Add showAll method 1

Driver class

-Handle menu 0.5

-Insert task 1

-Fetch task 1

-Encapsulation 1

-Update task 1

-Delete task 1

-ShowAll task 1

Compile success – qualified the requirements 3

comments 2

Lab7 scores 30