Implement a BST in a language of your choice. (Shaffer gives you much of this in Java, but you still need to test and debug it, and add some more methods.) Use strings as the keys. Each method should report not only the right answer, but how long it took to run in milliseconds. (You can do this by printing a message, or by returning a tuple of values.)
Required operations:
treesort method that takes in a list
(of ints or strings, whichever you chose), sorts
it using a BST, and returns the sorted list.
Implement a min-heap in a language of your choice. (Shaffer gives you much of this in Java, but it's a max-heap, and you still need to test and debug it, and add some more methods.) Use ints as the keys. Each method should report not only the right answer, but how long it took to run in milliseconds. (See above.)
Required operations:
heapsort method that takes in a list of ints,
sorts it using a min-heap, and returns the sorted list.
Dr. Siegfried's traditional project for this course: a "concordance" program that takes in a bunch of text, breaks it into words, and produces an alphabetized list of words, with the number of times each word appears in the text. A "word" is defined, for purposes of this problem, as a sequence of one or more letters: you can throw away spaces, punctuation, numbers, newlines, etc.
For example, applying the program to the preceding paragraph should produce an answer like
1 A 1 Dr 1 Siegfried 3 a 1 alphabetized 1 an 1 and 1 appears 1 as 1 away 1 breaks 1 bunch 1 can 1 count 1 course 1 defined 1 each 1 etc 2 for 2 in 1 into 1 is 1 it 1 letters 1 list 1 newlines 1 number 1 numbers 5 of 1 problem 1 produces 1 program 1 project 1 punctuation 1 purposes 1 reads 1 s 1 sequence 1 spaces 2 text 1 that 2 the 2 this 1 throw 1 times 1 traditional 1 with 3 word 2 words 1 you
(I actually did the above in two lines with Unix shell filters, but since this is a data structures course, I want you to write it using data structures you've written yourself, in a language such as Java, C++, Scheme, Ruby, etc. You may use built-in list data structures such as ArrayList, LinkedList, etc. but nothing that comes with its own sorting or searching capabilities.)
Your methods should report not only the right answer, but also how long it took to execute the method, in milliseconds. I'll try it on some large samples of text, and will expect your method to run reasonably fast.
Project 6.5 from the Shaffer textbook: using bottom-up trees and union/find operations to group two-dimensional points into clusters.