Due date: Friday Jul 31 at 11:59PM.
The assignment must be uploaded on Virtual Campus by the due date.
Late assignments are accepted between 1 min late up to a maximum of 24 hours
late and they will receive a 30% penalty.
A partial permutation of n is a (ordered) sequence of numbers from {1,2, . . . ,n} that does not
have repeated numbers.
For example, the following are different partial permutations of 5 (of sizes 3, 4, and 5 respectively):
(3,1,5)
(1,4,2,5)
(1,4,2,5,3)
In class, you have learned how to generate all the strings from a given alphabet
by using a Queue data structure.
In this assignment, you will design a similar algorithm to generate a collection of partial permutations
of specified type. This method differs from the one that generates all the strings since not every string
and substring is valid; more specifically you need not consider strings or substrings that have
repetitions. It is expected that you do this efficiently. That is, using an algorithm that generates
all strings first and filters out the invalid ones at the time of printing is not an acceptable solution
as the memory requirements for the Queue would make it impossible to solve even moderate size instances.
You are better off restricting the sequences and subsequences considered to the ones that do not
contain repetitions.
Three variations of generation of partial permutations will be employed:
Output Mode UPTOSIZE size=3 alphabet size=4
<empty>;a;b;c;d;ab;ac;ad;ba;bc;bd;ca;cb;cd;da;db;dc;abc;abd;acb;acd;adb;adc;bac;bad;bca;bcd;bda;bdc;cab;cad;cba;cbd;cda;cdb;dab;dac;dba;dbc;dca;dcb;
Output Mode FIXEDSIZE size=4 alphabet size=5 1234;1235;1243;1245;1253;1254;1324;1325;1342;1345;1352;1354;1423;1425;1432;1435;1452;1453;1523;1524;1532;1534;1542;1543;2134;2135;2143;2145;2153;2154;2314;2315;2341;2345;2351;2354;2413;2415;2431;2435;2451;2453;2513;2514;2531;2534;25412543;3124;3125;3142;3145;3152;3154;3214;3215;3241;3245;3251;3254;3412;3415;3421;3425;3451;3452;3512;3514;3521;3524;3541;3542;4123;4125;4132;4135;4152;4153;4213;4215;4231;4235;4251;4253;4312;4315;4321;4325;4351;4352;4512;4513;4521;45234531;4532;5123;5124;5132;5134;5142;5143;5213;5214;5231;5234;5241;5243;5312;5314;5321;5324;5341;5342;5412;5413;5421;5423;5431;5432;
The first thing to be done will be do add an auxiliary method to the class BinarySearchTree.java:
In this exercise, you will be using a Binary Search Tree whose "key" is a course letter grade (A+, A, A-, B+, B, C+, C, etc.) and stores in addition to the letter grade, an ordered list of student names with this letter grade.
To fit this more complex structure as the element stored in the
BinarySearchTree.java class,
we have created a class StudentListWithGrade.java
This class is an ordered list of Strings representing student names and also
contains a letter grade. It implements the interface Comparable<StudentListWithGrade> and the comparison is solely based
on the letter grade (the list of student
does not enter into account for the comparison of objects in this class.
The effect of creating a BinarySearchTree<StudentListWithGrade > is that the binary search tree will store the list of students with a certain grade in each node and the binary search tree comparison of elements will be based on the letter grade associated with the list.
If the complete list of students for each grade were available before
creating this binary search tree, there would be not much else to be done
in this assignment, other than creating BinarySearchTree
The BinarySearchTree<StudentListWithGrade> will be stored inside
a class StudentByGrade.java.
To test the class StudentByGrade.java,
you have been given StudentByGradeTest.java
that must not be modified.
A SAMPLE OF BEHAVIOUR FOR THE ADD METHOD
The following statements:
Produce the output:
Showing list Format:
The directory must contain the following files (with your implementation):
This class will be responsible to handle the different types of insertion
via two methods add that must be implemented by you:
Note that the methods above will need to use the new find method of BinarySearchTree.java
This method receives a letter grade and student name.
The insertion must behave in the following way.
If the binary search tree does not contain a list of student with this grade,
such an object of class StudentListWithGrade must be created with this grade and student name,
and inserted into
the binary search tree.
If the binary search tree
already contains a student with this grade, this element (an instance of
class StudentListWithGrade) should be located in the tree
and the name must be inserted into this existing list.
This method receives an object of class StudentListWithGrade.
The insertion must behave in the following way.
If the binary search tree does not contain a list of students with the same grade
as the grade of myList, then myList is simply inserted into
the binary search tree.
If the binary search tree
already contains a student list with the same grade
as the grade of myList, this element (an instance of
class StudentListWithGrade) should be located and myList should be merged into it.
StudentByGrade course = new StudentByGrade();
course.add("A+","Smith"); course.add("B+","Curtis"); course.add("A+","Black");
course.add("B","Silva"); course.add("A-","Moura"); course.add("A+","Collins");
course.add("F","Maradona"); course.add("B","Rosa"); course.add("B","Pitt");
course.add("A","Bryan"); course.add("C","Ryan"); course.add("D", "Danny");
course.add("C", "Lennon"); course.add("E", "Newman"); course.add("C+", "Harrison");
System.out.println("Showing Tree Format:\n"+course.treeToString());
System.out.println("\nShowing list Format:\n"+course);
Showing Tree Format:
((((()F[Maradona](((()E[Newman]())D[Danny]())C[Lennon,Ryan](()C+[Harrison]())))B[Pitt,Rosa,Silva]())B+[Curtis](()A-[Moura](()A[Bryan]())))A+[Black,Collins,Smith]())
F[Maradona]
E[Newman]
D[Danny]
C[Lennon,Ryan]
C+[Harrison]
B[Pitt,Rosa,Silva]
B+[Curtis]
A-[Moura]
A[Bryan]
A+[Black,Collins,Smith]
Rules and regulations (5/100)
Please follow the general directives for assignments.
You must abide by the following submission instructions:
Include all your java files into a director called u1234567 where 1234567 is your student id.
Zip this directory and submit via blackboard.
The assignment is individual (plagiarism or collaborations towards the solution of the assignment between students will not be tolerated).
Read the information on academic fraud from other assignments.