Suoritettu

java assignment

Using Java implement the following data structures and associated algorithms. Implement and automatically run the required test cases. Make sure your submission compiles and runs on AFS.

Tries

A Trie is a type of Tree that can be used to efficiently represent a set of strings. Tries can also be used to implement Dictionaries where the keys are strings. The edges in a Trie represent characters. The sequence of edges on a path from the root to another node represents the characters, in order, in a string (if that string was inserted into the Trie). Each node stores pointers to its children and a boolean value indicating if the node terminates a path that represents a string inserted into the Trie. The figure below shows the Trie built from the set of strings on the left. In the figure below the path from the root to “act” follows the edges labeled a-c-t, in the set of strings shown on the left. Note that the strings are not actually stored at the nodes (it’s shown that way for illustrative purpose) but they can be reconstructed from the sequence of edges using a preorder traversal of the Trie.

In this project you will implement a simplified version of a Trie. Specifically:

 The Trie must be implemented using a linked node implementation where each node stores (1) an array of pointers (or references, if using Java) to its child nodes and (2) a boolean flag indicating if the node represents the end of a path that represents a string in the Trie.

 For simplicity, you can make the following assumptions:

1. All strings will are lower case

2. All strings will consist of ASCII characters

3. All strings will contain alphabetical characters only (a-z)

4. All nodes store a fixed-sized array of pointers to child nodes (specifically, 26, one for each lowercase ASCII character).

 Each bucket of the child node pointer array is mapped to a corresponding ASCII character. For example, if you name the node’s child pointer array children then children[0] will represent the edge for the character ‘a.’ If such an edge exists then there will be a pointer to a child node. If no such edge exists then children[0] will store a null pointer. The same is true for the edge

representing the character ‘b’ (stored at children[1]), character ‘c’ (at children[2]), etc. Note that the above figure does not follow this scheme, but the figure below does.

In this project you will implement a Trie data structure and the following algorithms:

 InsertString(String str) – Inserts a new String str into the Trie. The Trie is initially empty. Note that, as you insert the characters of str that some of the rquired nodes may already exist. As you are traversing the Trie (according to the characters of str) you may need to add new nodes into the Trie or you may be able to reuse nodes that already exist.

For example, if you insert “and” after you inserted “ant” then nodes and edges for the “a” and “n” already exist and only an edge“d” will need to be inserted as a link to the appropriate child of “n.” Similarly, if you try to insert the word “an” after “ant” and “and” have been inserted then the node terminating the path with the edges “a” and “n” already exists and the only operation required is to switch the node from not representing a word to representing a word.

 StringExists(String str) – Returns a boolean value indicating if the String str is stored in the Trie.

 PrintStrings(String str) – Prints all of the Strings inserted into the Trie to standard output. This requires a preorder traversal of the tree. The preorder traversal must be implemented using the stack data structure described below.

Stacks

The PrintStrings operation will require a preorder traversal of the Trie. While this procedure could be implemented recursively, it is often implemented iteratively using a Stack. You will implement an array-based stack called ArrayStack to support PrintString’s preorder traversal of the Trie. ArrayStack will consist of the following operations: push(), pop(), top(), and isEmpty(). You cannot assume that the ArrayStack only stores pointers/references to Trie nodes, as you will also need a way to keep track of the current String. One option is to have the stack store entries that consists of a TrieNode and a String storing the characters on the path from the root to the current node. The array-based stack will start at some initial minimum size and grow/shrink as elements are pushed or popped. This should be done in an efficient way (i.e., don’t create a new array that is one size larger than the previous array when a new element is pushed onto the stack).

Test Cases

These must be run automatically by your program. Your program will take no user input.

Insert the following Strings into the Trie, in the following order: ant, cat, zoo, zone, bat, band, bean, fish, fishing, banana, catch, cannot, can, find, fix, any, zone, zoos, zoo

Determine if the following Strings are in the Trie: fin, find, baton, bat, ban, catching, ant, zones, can

Print all of the words stored in the Trie using the PrintStrings operation.

Example Code (in Java, untested, not compiled)

public class Trie {

private TrieNode root = null;

public Trie() {

}

public void insertStr(String str) {

}

public boolean strExists(String str) {

}

public void printStrs() {

}

}

public class TrieNode {

private boolean strInTrie = false;

private final TrieNode [] children = new TrieNode[26];

public TrieNode() {

}

}

public class ArrayStack {

private ??? [] arr;

public ArrayStack() {

}

public void push(???) {

}

public TrieNode pop() {

}

public TrieNode top() {

}

public boolean isEmpty() {

}

}

Taidot: Java

Näytä lisää: binary tree assignment java, memory assignment java applications, ncc assignment java, java, algorithm, school assignment java, file handling assignment java, project assignment java, car hire assignment java, project assignment java software development, operating system page replacement assignment java, search engine assignment java, anyone done bridge assignment java, java program using binary tree, java implementation source code tree, static methods assignment java, assignment java oxford, answering assignment java, java assignment java program process school registration, okoli assignment java

Tietoa työnantajasta:
( 2 arvostelua ) Fremont, United States

Projektin tunnus: #13055300

Myönnetty käyttäjälle:

$11 USD 1 päivässä
(36 Arvostelua)
4.8

33 freelanceria on tarjonnut keskimäärin 43$ tähän työhön

it2051229

Hi there, I would like to do this project if given the opportunity. Let me know if you are interested so I can have further details. Thanks.

$30 USD 1 päivässä
(1066 arvostelua)
7.6
dobreiiita

Hello I am Java and Algorithm expert and interested in this project. I have reviewed the attached file and confident to handle it perfectly. I have a lot of experience in helping in students with assignments Lisää

$55 USD 1 päivässä
(402 arvostelua)
7.4
DucNA

Hi there, I'm a senior software developer who have over 300 completed projects with 100% positive reviews and my account also is qualified by this site as a Preferred-freelancer. My portfolio: [login to view URL] Lisää

$29 USD 0 päivässä
(270 arvostelua)
6.6
AhmedLabib93

Hello My name is Ahmed, i'm a top rated freelancer. i worked over 250 projects and over 600 hours doing java projects. plus i passed freelancer java exam with top 15% plus i got 2 java certificate 1Z0-803 and 1Z0- Lisää

$60 USD 2 päivässä
(399 arvostelua)
6.6
wizard2015

Hi, I am experienced software developer and I am ready to complete this project. You can find more information about me and my professional experience on the my freelancer profile page. We can discuss all details in t Lisää

$50 USD 3 päivässä
(67 arvostelua)
6.2
$35 USD 1 päivässä
(119 arvostelua)
6.1
$150 USD 1 päivässä
(115 arvostelua)
6.2
$97 USD 1 päivässä
(17 arvostelua)
5.6
$25 USD 1 päivässä
(37 arvostelua)
5.7
dipakjadhav08

A proposal has not yet been provided

$35 USD 2 päivässä
(83 arvostelua)
5.4
neerajagrawal201

I have good knowledge in below mentioned skills by you. I also have some certifications in Java. I can share some of demos with you if you want for better understanding. Currently I'm working on a banking project in an Lisää

$30 USD 1 päivässä
(40 arvostelua)
5.0
oatechnology

Hi , hope you are doing well i am software engineer with 5 years experience in software development using Java I can help you to complete this project, also i can provide demo for your requirements hope to co Lisää

$50 USD 1 päivässä
(35 arvostelua)
4.6
dharamdaring

Hi, I am a software developer with 9+ years of experience in Java/J2EE and I have been writing algorithms for long. I believe I can write the program and deliver it to you with test cases as well in given time a Lisää

$30 USD 2 päivässä
(17 arvostelua)
4.3
SamamaJaved

Hello dear, I have good skills in java development. I have built tries and stack many more times. I have read your requirements. I can do this for you. Contact me so that we can proceed with you. Thanks.

$66 USD 1 päivässä
(21 arvostelua)
4.2
arehmanpk

Hi I hope you are having a great day. I can do this for you. Please contact me to discuss further. Thank you

$50 USD 1 päivässä
(14 arvostelua)
3.5
ams53

A proposal has not yet been provided

$43 USD 3 päivässä
(7 arvostelua)
3.3
infocentroidtech

Hi, Kindly watch my latest review regarding java's project. I have more then 10 years of experienced in java, i did lots of work on Swing,AWT, JDBC, servlet, JSP, Spring Kindly initiate the discussion

$77 USD 1 päivässä
(4 arvostelua)
3.5
shahzabkhan

I have very good experience in java. I've implemented many algorithms in java and worked in trees too. I've read your requirements and I can do that , I can implement tries as mentioned in descriptions

$66 USD 1 päivässä
(3 arvostelua)
2.4
giobong

Hello. I've wrote your Java assignment. It's pretty easy for me and I can do it for you tomorrow, because now I haven't time. If this interested you, please, contact me. Best Regards Giorgi.

$40 USD 2 päivässä
(2 arvostelua)
1.9
asimhussain26

A proposal has not yet been provided

$30 USD 1 päivässä
(3 arvostelua)
2.2