Problem: k-Grams

In computational linguistics, a k-gram is a series of k consecutive words taken out of a piece of text. For example, in the text

                                         Mr. Owl ate my metal worm
there are four 3-grams, each of which is given below:

Mr. Owl ate

Owl ate my

ate my metal

my metal worm

k-grams are used extensively in computer science - especially in artificial intelligence and computational linguistics - and are at the heart of many techniques in machine translation.

Your job in this problem is to write a method

private ArrayList kGramsIn(ArrayList text, int k)

This method accepts two parameters - an ArrayList representing a piece of text and a num¬ber k. It should then return an Ar ray List (that is, an ArrayList of arrays of Strings) con¬taining all the k-grams in the text.

The text parameter to this method consists of an ArrayList containing all the words in the source text in the order in which they appear. For example, if the input text was "Mr. Owl ate my metal worm," the text parameter would be this ArrayList:

Mr. Owl ate my metal worm

Calling the above method on this text with k= 2 would produce an ArrayList containing the following 2-grams, each of which would be represented by a St ring [ ] of length two:

Mr. Owl
Owl ate
ate my
my metal
metal worm

Calling this method with k = 4 would produce an ArrayList containing these 4-grams, each of which would be represented by a St ring [] of length four:

Mr. Owl ate my
Owl ate my metal
ate my metal worm

In implementing this method, you can assume that the value of k will be greater than zero and no greater than the number of words in text.

Problem: Andy Warhol Paintings

The artist Andy Warhol produced a series of famous portraits made with only a small number of colors. Even with a limited color palette, the portraits are immediately recognizable and have since become iconic. In this problem, we'd like you to write a method that transforms a source image in the style of these prints.

Write a method

private Glmage andyWarholtze(GImage source, int[] palette) that accepts as input two parameters. The first parameter, source, will be an ordinary GImage. The sec¬ond parameter, palette, is an array of ints, each of which represents a color value (in the same way that each pixel in a G Image has its color represented by an int value).

This method should work as follows. For each pixel in the source image, you will change the color of that pixel to the color from palette that is "closest" to the original color. To help you determine which palette color is closest to a given pixel color, you can assume you have access to the following method:

private double stmtlarity0f(int colorl, int color2)

This method accepts as input two int values representing colors and returns a double between 0 and 1 that determines how similar those colors are. The higher the value returned, the more similar the colors are. When you're trying to figure out which color from the palette you should use to replace some pixel from the original image, you'll want to use the palette color that's most similar to the original pixel. (If two or more colors are tied for highest similarity, you can use any one of them.)

In implementing this method, you can assume that the palette has at least one color in it, but you should make no other assumptions about the image or the palette colors. There is no special significance to the order in which the colon appear in the palette array.

Write your answer to this problem on the next page, and feel free to tear out this page as a reference. Just for fim, here's the output of the method given as input a picture of a puppy:

Problem: Finding Coworkers

Suppose you have the organizational hierarchies of various companies showing who reports to who. For example, across three different companies, you might have this hierarchy information:

In this diagram, person e reports directly to person b, who reports directly to person a, who is the CEO of her company and therefore doesn't report to anyone.

This hierarchical information can be represented as a HashMapcSt ring , St ring> associating each per¬son with their direct superior (that is, the person one level above them in the hierarchy). As an excep¬tion, the heads of each organization are not present in the HashMap, since they don't report to anyone. For example, in the above picture, the key h would have value g, the key g would have value d, the key d would have value a, and a would not be a key in the map.

Given two different people you can tell whether they work for the same company by tracing from those people all the way up to their companies' CEOs, then seeing whether those CEOs are the same person. For example, in the above diagram, person e and person j work in the same company because both of them report (indirectly) to a. Similarly, person n and person k are in the same organization, as are per¬son c and person d. However, person j and person in are not in the same company, since person fs com¬pany is headed by person a and person m's company is headed by person k. Along similar lines, person and person b are in different companies, since person ar runs her own company (she doesn't report to anyone) and person b works at a company headed by person a.

Your job is to write a method

private boolean areAtSameCompany(String p1, String p2,
HashMap bosses)

that accepts as input two people and a HashMap associating each person with their boss, then reports whether pl and p2 work at the same company. You can assume the following:

• For simplicity, assume that everyone has just one boss, that each company has just one CEO, and that no person works at two or more companies.

• Everyone, except for the heads of companies, appear as keys in the HashMap. Therefore, if someone doesn't appear in the HashMap, you can assume that they are the head of a company.

• Names are case-sensitive, so "Karel" and "KAREL" are considered different people.

• pl and p2 may be the same person.

• There can be any number of levels of management between pl and her CEO and between p2 and his CEO, including 0, and that number of levels doesn't have to be the same.