ComputerScienceExpert
$18/per page/
Hi please help me with my homework. No PLAGIARISM.
Advanced Java Gang,
We reviewed some important data structures and discussed why understanding a variety of
data structures is critical to your success as a programmer. Take time this week to review
the data structures we covered – arrays, linked lists, stacks, queues, hash tables, trees. For
example see if you can write a Stack class that could store String objects. You could try
writing the Stack class using a static Java array, a Dynamic Java Array (e.g., ArrayList), or
a LinkedList. You could try implementing three different Stack classes (each one using a
different underlying data structure). Imagine how your programming skills will improve and
how your self confidence as a programmer will improve if you get as much programming
practice as possible. If you are a more advanced student, try implementing a hash table on
your own (don’t use the Java HashTable class, rather write the class yourself!). Review your
data structures course book, if necessary.
I demonstrated in class how to download Eclipse so that you don’t need to install it. Make
sure you bring your computer to class next week (Sept. 15th) and have Eclipse installed.
For next week’s class (Sept. 15th) I asked that you work on a programming exercise.
Import the numSearch project (use numSearch.zipfound in the Yahoo Group or in the OSC
Handouts section) into Eclipse – I demonstrated how to do this in class. The program
includes a random number generator so that you can add thousands of numbers to a variety
of data structures.
For the programming exercise:
1. Add the numbers to an ArrayList so that there are no duplicates in the
list. Don’t use the contains() method of the ArrayList class – I want you to get
practice writing the necessary code yourself. Test that your method works – don’t
use the random number generator for your tests because it may not get duplicates
for small array sizes. After you know your algorithm works, you can use the random
number generator and try adding thousands of numbers to the list. 2. Once that works, try something a little more complicated. Add the numbers to an
ArrayList such that the list has no duplicates and is always sorted. This means
that after you add a number to the list, the list is still sorted. Once again, test that
your algorithm works with only a few numbers before using the random number
generator. I showed one algorithm you could use to do this: create a “hole” in the
array by “pushing down” elements of the array after you figure out where the number
should be inserted. A second (alternative) approach would to add the new number
to the end of the list. Then keep swapping numbers until everything is in the correct
order. So for example, if you already have 10 numbers in the list (at indexes 0 to 9), add the new number at index 10. Then compare the numbers at index 9 and index
10. If the number at index 10 is less than that at index 9, swap them, otherwise you
are done. Then if you did a swap, compare the numbers at index 8 and 9 and repeat
the process until you find there is no need to swap the numbers. Try both algorithms if you can. Remember you want to get as much practice as
possible. That is how you will become a better programmer. You won’t become a
good programmer by only reviewing slides or by taking the easy way out. 3. Try a different data structure such as the LinkedList class:
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
Keep the LinkedList sorted after adding a new number. 4. See how much time it takes for your algorithms to work – as you increase the
number of integers you add to the data structure how is the amount of CPU
affected? In other words, if you use 100,000 integers and then 200000 integers is
the difference in time twice as long? Since we are using random numbers you will
get slightly different results with every run, but you can identify the pattern. Is there
any difference in time between using a LinkedList and an ArrayList?