ITI 1121. Introduction to Computing II - Summer 2015

Assignment 4 (100 points, weight 6.25%)

(Last Modified in July 25, 2015)

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.

Learning objectives

Part 1: Generating Partial Permutations (45/100)

A permutation of n is an ordering of all the numbers in {1,2, . . . ,n}.
For example, the following are two different permutations of 5:

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):
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:

You are given classes: We give a sample output for alphabets {a,b,c,d}, {1,2,3,4,5}, respectively:

Output Mode UPTOSIZE size=3 alphabet size=4

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;

Part 2: Practice with Binary Search Tree and Ordered Lists (50/100)

This part builds on classes you have used in Laboratory 11 and Laboratory 13.

The first thing to be done will be do add an auxiliary method to the class

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 class, we have created a class
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 and inserting these lists one by one. However, the students with their grades can become available at any given point in time, even after the tree has being created and a list with some students with that grade have already been inserted into the binary search tree. This require that the method "add" for this structure has to be done a bit more carefully.

The BinarySearchTree<StudentListWithGrade> will be stored inside a class
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

To test the class, you have been given that must not be modified.


The following statements:
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);

Produce the output:
Showing Tree Format:

Showing list Format:

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 directory must contain the following files (with your implementation):

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.