Sample Problems

These are some sample problems for the final. Some are closely based on problems that are actually on the final, others test issues that I think it is important for you to consider. As you might guess, there will be problems on the final that cover topics other than those given here and that have different forms than those given here.

Regular Expressions

Write a regular expression for comments in C. In C, a comment begins with /* and ends with */. A comment cannot contain */ although it may contain another /*.

Mutual Generation

Write two classes, Alpha and Beta such that the main() routine of Alpha generates the code for Beta and vice versa. Neither program should read the source code of the other.

I will not tell you how to do this sample problem. If you did the appropriate homework, it should be trivial.

Formatting

Using your input and output classes, sketch a program that one might use to format tables. The input to your program should be a file that contains:

• A type specification on the first line. This specification indicates how many data objects should appear on each line of the table, what type each element has, how many spaces should be allocated to each element, and how each element should be aligned.
• Data. You should not assume that all the data for one output line appear on the same input line.

Part of your goal in this problem is to determine a useful way to represent the form of the input.

Commenting

Consider the documentation that Sun supplies for class XXXX. How is this documentation ambigious? What else is wrong with the documentation? How might you improve it?

Profiling and Makefiles

Suppose you've written a series of profiling classes, including

• AddProfCommands which adds profiling commands to a a Java program, storing the results in a new file. These profiling commands will be used to write profiling data to the file profile.data when the updated class is compiled and executed. You would execute this class with
  java AddProfCommands original updated
• InsertProfData, which inserts profiling data into a original file, putting the results into a separate file. You would execute this class with
  java InsertProfData original data result
• Profiler, which provides the commands that AddProfCommands uses.

Assume that you wish to profile the class Alpha and that you may need to modify not just Alpha.java but also your profiling classes.

Write a makefile that can be used to automatically generate Alpha.prof, a profiled (with annotations as to number of executions) version of Alpha.java.

Associative Arrays

During class discussions, we came up with a number of benefits for using associative arrays, primarily in making it easier to do input, output, and debugging based on human-readable values. We also suggested that it might be possible to use normal arrays instead and "encode" each piece of text with a number.

• Argue that it is better to use normal arrays rather than associative arrays.
• Sketch the input and output routines that would be necessary to convert Bentley's topological sort routine into one that uses normal arrays.

Minimum Spanning Trees

An interesting problem one often encounters in dealing with graphs is that of finding the minimum spanning tree (MST) of a nonnegatively weighted graph. The MST is a subgraph spans the graph in that it is possible to find a path between any two nodes in the graph using only edges in the MST. The MST is the smallest such subgraph.

• Write a greedy algorithm to find the MST.
• What is the running time of your algorithm? What assumptions about the implementation of the graph did you make to come up with that conclusion?
• Is it correct? If so, sketch a proof. If not, find a counter-example.
• How might you test your algorithm?

Human Factors and Document Conversion

Many people criticize the Microsoft Word HTML generation facility for being insufficiently general and failing to accomodate the needs of hypertext authors. For example, one might want to automatically split a Word document into separate nodes, one per section. Suggest how you might design a more appropriate translation scheme for word. Make sure that your answer describes features, presentation of those features, and process by which you would validate your design.

Debugging

Upon implementing a variety of sorting algorithms in Java, you discover that they run significantly slower on our HP's than do corresponding versions written in Basic on old 80286s. Of particular concern is your quick sort routine.

Describe a process by which you might identify potential reasons for this slowness and improve the speed of your sorting routine.