[SOLVED] Csci 251 project one to five solutions

In this project, the students are required to implement the following algorithms:
Insert Sort, Select Sort, Quick Sort, and Merge Sort.

One file is given:CSCI251ProjOne.java. Please study this file to understand what
is going on. This file cannot be modified.

One file is to implement: MySort.java. In this file, the students must provide the
following public interface:
public static void insertSort(int [] arr);
public static void selectSort(int [] arr);
public static void quickSort(int [] arr);
public static void mergeSort(int [] arr);

The quick sort and merge sort must be implemented by using recursive thinking.
So the students may provide the following private static methods:
//merge method
//merge two sorted portions of given array arr, namely, from start to middle
//and from middle + 1 to end into one sorted portion, namely, from start to end
private static void merge(int [] arr, int start, int middle, int end);

//merge sort recursive version
//sort the portion of giving array arr, from begin to end private static void
mergeSortRecursive(int [] arr, int begin, int end);
//find pivot point for quick sort
private static int pivot(int [] arr, int begin, int end);
//quick sort recursive version
//sort the portion of giving array arr, from begin to end

private static void quickSortRecursive(int [] arr, int begin, int end);
The student need to have and only have the above public and private static
methods in his/her implementation of MySort class.

Run Demo:
ProjectOne.jar is available for students to download and run on their computer.
The students may run to demo in the terminal window to see how program
should run. The students may watch YouTube video “How to Run Jar file in the
Terminal Window” or refer to the file “How to Run Jar File in the Terminal
Window.pdf” on blackboard Projects folder
Due Date: To be announced on blackboard.

The purpose for this project is to reinforce the knowledge from Chapter Two of the textbook. The students will practice how to implement stack and queue data structure using list structure, for instance, ArrayList. The students will also apply stack and queue in real project, for instance, to check if a string is

a palindrom.

 

structure that has Last In First Out property (35%)

structure that has First In First Out property (35%)

(30%). This function returns true if sentence is a palindrome; false

otherwise.

Sample files:

Three sample files are given. The students should add necessary comments to all files and implement all functionalities in the given files. No extra functions can be added. No function name can be changed. The students should run the executable jar file to see how project should run. The students should zip whole project and submit it via blackboard link.

 

Due Date:

Will be announced on blackboard

This project is designed to help students to understand the HashTable and algorithms related to HashTable. The students need to implement two given classes: MyHashEntry and MyHashTable.

 

Three classes are given. The students shall not modify the ProjThree.java file. However, the students should understand this file. The other two files, MyHashEntry.java and MyHashTable.java, are the files that the students need to finish.

 

These two files, MyHashEntry.java and MyHashTable.java, must be implemented within the given design. The students cannot change the name of public methods. Please notice that the table must be implemented as generic data structure.

 

The students may run the given executable jar file to see how the project should work. When the students run the executable jar file, the students may

enter <ID, NAME> pairs. Please notice that ID or Name are all Strings with no white space in it.

 

Due date: will be announced on blackboard.

This project is designed to help students to understand the Binary Search Tree and algorithms related to Binary Search Tree. The students need to implement two given classes: TreeNode and BinarySearchTree.

 

Three classes are given. The students shall not modify the CSCI251ProjFour.java file. However, the students should understand this file. The other two files, TreeNode.java and BinarySearchTree.java, are the files that the students need to finish.

 

These two files, TreeNode.java and BinarySearchTree.java, must be implemented with in the given design. The students cannot change the name of public methods. The students cannot add extra public methods. However, the students may add private methods to make the implementation more clear and easier to read.

 

For instance, the toString method will return a String representation of a Binary Search Tree. The best way to do so is using recursive thinking. So the toString method actually is a driver method for private method nodeTravesal (see below). The implementation could be as following:

 

public String toString(){

return “(” + nodeTravesal(root) +”)”;

}

private String nodeTravesal(TreeNode<E> treeNode) {

if(treeNode == null)

return “–‐”;

return treeNode.getData().toString() + “(” + nodeTravesal(treeNode.getLeft()) +”, ” + nodeTravesal(treeNode.getRight()) + “)”;

}

 

The students may run the given executable jar file to see how the project should work.

 

Due date: will be announced on blackboard.

The purpose for this project is to reinforce the students’ knowledge on graph. The students will implement the Breadth First Search and Depth First Search for the graph.

 

The graph will be a direct weighted graph represented in adjunct matrix form. We assume that all weights are positive integers. The graph will be initialized from keyboard. When the students input the graph of n vertices, the students actually input an n by n matrix.

 

The matrix represents a simple direct weighted graph. There is no loop at vertex. No more than one edge from one vertex to another vertex. The vertices are numbered as 1, 2, …, n. The graph with n vertices is represented by an (n+1) by (n+1) matrix with row 0 and column 0 unused.

 

The entry on row i and column j is the weight of edge from vertex i to vertex j. For instance, if there is an edge of weight 8 from vertex i to vertex j (i != j), then entry on row i column j of the matrix will be 8. We assume that all weights are positive integers. If there is no edge from vertex i to vertex j (i != j), then the user will input 0 for the entry on row i column j of the matrix. However, the given code will automatically change that entry to be Integer.MAX_VALUE.

 

Two files are given. The one namedCSCI251ProjFive.java cannot be modified. However, the students should understand it. The one name MyGraph needs to be implemented. In fact, there are only two methods in this file need to be implemented. The students shall read the description of each method and implement the method accordingly. No methods declaration can be changed. No other public interface can be added.

 

The students may run the executable jar file to see how the finished project should run. In this implementation, when there are more than one choice of the vertices, it choose the one marked with lower number first.

 

Example Run:

Suppose the graph is following

For this graph, the student can view it as directed weighted graph. Each edge has two directions. On each direction, the weight is 1. So the array input will be:

0 1 0 0 1 0

1 0 1 0 1 0

0 1 0 1 0 0

0 0 1 0 1 1

1 1 0 1 0 0

0 0 0 1 0 0

 

If we run the BFS algorithm with startVertex 6, then the output should be 6, 4, 3, 5, 2,1,

If we run the DFS algorithm with startVertex 6, then the output should be 6, 4, 3, 2, 1,5,

Due date will be announced on blackboard.