Java代写 | CSI2110 – Assignment 2

CSI2110 – Assignment 2

Part 1 – Short Exercises (45 points)
Download the file from the course web site and unzip it; this will produce two eclipse ready projects: Part1 and Part2
Import the Part1 project into eclipse
The project contains the following packages
datastructures: contains the implementation of the net.datastructures.LinkedBinaryTree and net.datastructures.ArrayStack
assignment2: contains the csi2110.assignment2.ShortExecises main class
Exercise 1 (15 points)

Change the implementation of the preOrder traversal method found in the csi2110.assignment2.ShortExecises class so that it is no longer recursive. Use the net.datastructures.ArrayStack as an auxiliary structure in order to achieve that purpose.

Exercise 2 (15 points)

Implement a queue using the java.util.ArrayList as an auxiliary structure. The following directives must be respected:

The queue should be called ArrayListQueue and be placed in the datastructures package
The queue should implement the interface datastructures.Queue<E>



Exercise 3 (15 points)

In level order traversal, all the nodes at a level are visited before passing to the next level. The operation starts at the level 0 where the root is visited, and then proceeds to level 1, where the all nodes (children of the root) are visited from left to right, and then proceeds to level 2 where the same process repeats… Therefore, a level order traversal of the tree shown in figure 1 would result in the following sequence of traversal: A, B, C, D, E, F and G.

Figure 1: Tree Used to Demonstrate the Level Order Traversal Concept

Use the net.datastructures.ArrayListQueue implemented in Exercise 2 as an auxiliary structure in order to complete the implementation of the levelOrder method in the csi2110.assignment2.ShortExecises class.

Part 2 – Mini-Project (55 points)

Bob just got hired as a Java programmer at company ISC. His first work assignment is to implement yet another simple Text Editor in Java that provides the following functions:

Allows users to enter textual information into the editor
Allows users to undo actions performed
Allows users to open pre-written text files
Allows users to invoke a spell check operation to verify the correctness of the words in the text document
Bob’s Implementation

To implement the spell check operation, Bob made use of a file that contains the most commonly used English words listed in alphabetical order. We will refer to this file as the English Words List (EWL). In his program, he performs the following two steps:

Reads the EWL file and stores its words in a Node List structure
For each word in the text, checks if it can be found in the Node List. If it cannot be found, then the word is judged to be incorrectly spelled.

To implement the undo operation, Bob made use of a stack structure to store all user actions. Whenever undo is called, the last user action is popped, examined and its effects are reversed. For instance, if the last user action was adding a letter, the undo operation would delete that same letter.

Current Issues

Bob implemented the program, and to his disappointment, his boss raised the following issues:

The spell check operation is too slow. Most of the time is wasted traversing the Node List to look for entries.
The undo operation should not allow a user to reverse edits indefinitely. Number of allowable “undos” should be limited to 10 in order to limit the amount of previous actions saved in memory.

Bob quickly realized why he is facing these issues:

Searching for a word in a Node List is taking too long (worst case: O(n) word comparisons). He needs to make use of a structure and algorithm(s) that allows him to implement a better search mechanism (worst case: O(log2(n)) word comparisons).
His stack needs to be implemented in a way where its size does not grow beyond a preset limit. Once the size of the stack reaches this limit, it starts to leak and therefore dropping the oldest entries in the structure. He therefore needs a leaky stack!
Your Task

You are hired at ISC as a consultant in charge of helping Bob. You are responsible for the following tasks (after all, they are paying you a hefty salary):

Exercise 1 (35 points) – Employ an alternative structure to hold the words instead of the Node List (core.structures.NodeList). Note that the words are already ordered alphabetically in the EWL file. Your new structure (which we have already seen in class) should allow the search mechanism to be optimized (refer to the HINT below). In order to succeed at this task, you have to:
Implement the new structure yourself (you cannot use one of the standard java structures). Note that all of the functions defined in its ADT must be implemented. The new structure should be placed in the core.structures package.
Integrate an optimized search mechanism (O(log2n) complexity) into the new structure. Assume that each word comparison (test) is counted as one primitive operation, regardless of the length of the word.
Make sure the structure does not have a static size since other words may later be added to the EWL file. The program should be able to accommodate such updates of the EWL file without changing the implementation.
Edit the class core.EwlListAdaptor in order to reference the new structure as opposed to the old one.

Exercise 2 (20 points) – Implement the leaky stack previously discussed using a linked structure. An array based implementation is not acceptable. In order to achieve this task, you need to extend the core.structures.AbstractStack abstract class. Place your new class in the textEditor.core.structures package. Also, make sure the textEditor.gui.TextEditorGui class references the new stack instead of the old java.util.Stack.
HINT: Since the words are already ordered alphabetically in the EWL file, reading them into an array list would allow you to perform a very effective search on the words using one of the algorithms we have seen in class.  Side note: if you use an AVL tree, the numerous rebalancing will cause the load time (time it takes to load the words into the structure) to be larger than that of the array list implementation, think about it…
Download the file from the course web site and unzip it; this will produce two eclipse ready projects: Part1 and Part2
Import the Part2 project into eclipse
The contents of the Part2 directory is organized as follows:
Src folder: contains all the java source files of the Text Editor program.
Properties folder: contains the file that configures the Text Editor program.
Config folder: contains the ewl.txt (the file containing a list of the most popular English words) and about.txt.
txt file: contains the RFC of the TCP protocol. This file will be used to test the efficiency of the program.
Run the Text Editor program (TextEditorGui is the main class) (see figure 2)
Experiment with the Text Editor by testing its spell check and undo functionalities. These two commands can either be called from the menu on the top or using keyboard shortcuts (F7 for spellcheck and ctrl+z for undo)
Open the file TCP_RFC.txt contained in the file. This is the Request for Comment (RFC) for the TCP protocol. Run the spell check command. The TCP RFC is a lengthy file and will give the Text Editor quite a work out. When the spell check operation is finally completed, a list of the incorrectly spelled words will be displayed (see figure 3). Also, the following sentence will be printed in the console: “Time it took to finish spellcheck operation: x ms” (where x is the amount of milliseconds it took to complete the spell check). As you improve your implementation, x should decrease.

How to Submit

After completing the assignment, make sure you follow these steps for submission:

Create a zip file out of the Assignment2 directory (should contain the Part1 and Part2 directories)
Submit the on the Brightspace website.
Note: In case your project does not compile, You MUST create a readme file that includes the methods that you have implemented and why your project does not compile.

Figure 2: Text Editor Interface

Figure 3: Window Pop-up Displaying Incorrectly Spelled Words

Figure 4: You celebrating when you’re done…


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:itcsdx