Catalog Description: A continuation of Computer Science 150 and 150L, topics include analysis of algorithms, with emphasis on computational complexity and advanced algorithms including self adjusting trees, hashing, graphs, sorting, searching, hashing methods, and greedy algorithms.
Graphical test programs that can help you identify problems in your container classes.
I will post more information as I am able. The test suite is version 1 and some updates are already planned. To use simply unzip the rar files. Drop the .class files with your class files and the .java with your source. Note that I did not provide source for the class files and I may not have provided class files for the sourde. While you should not need source files for the class files some students had problems with this llast year. We were able to compile from the command line and then everything worked. I haven't completed testing out side my environment so please be patient, more instructions will follow ASAP.Implement ArrayOperations and Vector classes. You'll need the Visitor interface to test your code. The Sample_Visitor class provides an example of implementing a visitor interface and using a visitor object.
No constructor needs to be explicitly provided for the array operations class but to use it you will have to call a default constructor and create an object. You can argue (perhaps correctly) that these methods really ought be static, but interfaces do not allow static methods and I wanted you to implement an interface. Thus you will have to create an object to call these methods in your test code.
Implement a Linked List class. You'll need the Visitor interface (from Project 1) to test your code. The Sample_Visitor class provides an example of implementing a visitor interface and using a visitor object.
Implement the Stack and Queue Interfaces. You'll also need all of the interfaces from Projects 1 and 2 as well as completed code from project 1 and 2 to test your code. Your Stack and Queue classes must use the Vector and Linked List classes from Project 1 & 2. Meet all of the following criteria:
Implement the CS220_SimpleSortingAlgorithms_Interface. This will require that you implements the following sorting algorithms:
As usual you may introduce additional methods as you see fit. Here a simple yet viable testing strategy might create an array or sorted data, scramble it or reverse it in a clone, call the sort routing using the clone, then verify that the result matches the original sorted data.
Implement the CS220_FastSortingAlgorithms_Interface. This will require that you implements the following sorting algorithms:
As usual you may introduce additional methods as you see fit. Here a simple yet viable testing strategy might create an array or sorted data, scramble it or reverse it in a clone, call the sort routing using the clone, then verify that the result matches the original sorted data.
Portfolio of projects 1-5 due. Must include testing code etc. This will be assigned 5 grades. This will also be the day of our exam 1.
Implement the CS220_BinarySearchTree_Interface.
As usual you may introduce additional classes and methods as you see fit.
Implement appropriate Graph representations and algorithms as described below.
As usual you may introduce additional classes and methods as you see fit.
No interface will be provided. Your design will be part of your grade.
Write a program that creates random weighted connected graphs then use this to implement and tests:
Your program should produce output representing the graph and the solution.
A path can be presented as (1-5-4-17-.....)
A weighted path can be presented as
(1,5,20), (5,4,14),
but any clear representation will suffice.
You may have a representation for each problem
or you can reuse your representation if appropriate.
Find the asymptotic complexities of the Fast Sorting Algorithms (see project 5). Give proofs that justify your conclusions.
Participate in 4 Walk-thrus. 3 as reviewer and 1 as the coder. Submit a copies of your reports. Your Walk throu reports must also appear at the end of the year in your updated portfolios.
