Assignment 1

Objectives and example

A1.0 Audio:

With this assignment, we'll launch a theme that will pervade most future assignments in many future units: break a problem down into methods that need to be created to solve the problem.

It's a complement to the high-level pseudocode we've seen earlier:

Start with high-level pseudocode.
However, be thinking that parts of your pseudocode will involve calls to methods that you will write.
Then, implement and test these methods.
Finally, put the whole program together.

We'll show you how this is done for a slightly harder problem than the ones you will be assigned below.

Consider this problem: we want to process a string of letters and parentheses and decide whether the parentheses are "legit". That is, are the parentheses balanced? For example:

	String s = "()";
	s = "a(b(c(de)f))((g)h)";
	s = "What I said (I mean ... (really?)) was (I'm not sure now) that it's true";
	s = ")(";
	s = "()(()()(";

Here, the first three are balanced but the last two are not.

Our goal is to craft a method that will decide this question, to be used as follows:

	// Test #1: balanced
	String s = "()";
	boolean isBalanced = checkBalanced (s);
	System.out.println (isBalanced);

	// Test #2: balanced
	s = "a(b(c(de)f))((g)h)";
	isBalanced = checkBalanced (s);
	System.out.println (isBalanced);

	// ... (more tests) ...

A1.1 Exercise: At this point do not write any code. Try to sketch out a solution in pseudocode (in the assignment pdf). See how far you get before reading through the solution.

Now work through the solution

And now, on to your assignment. Good luck!

Assignment problems

Recall the example in Module 0 (of Unit-1) in which we rotated the elements of an array rightwards. Consider now a left rotation of an array:
Here, elements are shifted leftwards, and an element that is shifted "off the left end" is shifted into the rightmost position. We have described a left rotation by 1 position (each element gets shifted by one spot). One can generalize this to a rotation in which each element moves k spots to the left. An example with k=2 is shown above.
In a file called LeftRotate.java write a method called leftRotate (int[] A) that performs left rotation and test it with at least three different arrays (of different sizes), including int[] A={1,4,9,16,25}. The test arrays should be in main(). Following each test, print the resulting array to confirm that it was properly rotated.
Then, write a method called leftRotateByK (int[] A, int k) that achieves a left rotation of an integer array by k positions, where k is a variable you can change in the program. Test it out for k=2, k=3 and k=5 using the same test data, including int[] A={1,4,9,16,25}. Print the "before" and "after" arrays to show that it rotated correctly.
Consider the array
```
	int[] histogram = {2, 3, 8, 2, 1, 0, 3, 0, 6, 3};
```
Think of the elements in here as the heights of rectangles that will be drawn along the x-axis using DrawTool as shown below:
Such a picture is called a histogram. Write a program called Histogram.java that takes the histogram array and draws the rectangles. Don't forget that the width of each rectangle is slightly less than 1.0 and that you need DrawTool.java in the same directory.
Now, we'll use the above idea to construct and display a histogram using data. Consider this array of real-valued data:
```
	double[] data = {8.5, 6.6, 2.7, 2.1, 9.4, 0.9, 
			 2.1, 6.2, 8.3, 1.2, 2.2, 0.3, 
			 9.3, 2.6, 3.8, 2.5, 6.8, 8.1, 
			 8.8, 9.5, 1.8, 8.2, 1.5, 2.9, 
			 8.9, 3.1, 2.9, 4.6};
```
The above data was used to count how many data values are in the range 0 to 1 (answer: 2), how many in the range 1 to 2 (answer: 3), etc. Thus, this is the data used to generate the histogram counts in the previous exercise. Write a program called HistogramGeneration.java that takes the data array, uses it to generate a corresponding histogram array and draws the rectangles. Your code should have commented-out print's that demonstrate pro-active debugging.

In this exercise, you will take up the task of identifying the common suffix between two words. Thus, the following

    public static void main (String[] argv) 
    {
        char[] word = {'n','e','v','e','r'};
        char[] word2 = {'r','i','v','e','r'};
        char[] word3 = {'e','v','e','r'};
        char[] suffix = commonSuffix (word, word2);
        printArray (suffix);
        suffix = commonSuffix (word, word3);
        printArray (suffix);
    }

should print "ver" and "ever". Call your program Suffix.java, and write the methods that will make the above work. Your code should have commented-out print's that demonstrate pro-active debugging.

For this question, you will merely write plain text (in assignment1.pdf ) to explore natural language processing.
- Start by reviewing this (4-minute video) story about Watson.
- Find a website that explains the challenge of writing programs that understand natural languages. This is an active area of research called Natural Language Processing (NLP).
- What are other examples of NLP? Can you find software written in Java that performs NLP?
- Undoubtedly, you have "talked" to a computer program on the phone, for example, when you've called an airline or a bank, or phone company. Is this an example of NLP? Or is the computational challenge something else?
- What other major defeat of a human occurred at the hands of an IBM computer?

A1.2 Audio: