The BitVectors are an ancient and immortal race of 10,000, each with a 10,000 bit genome. The race evolved from a single individual by the following process: 9,999 times a BitVector chosen at random from amongst the population was cloned using an error-prone process that replicates each bit of the genome with 80% fidelity (any particular bit is flipped from parent to child 20% of the time, independent of other bits).

Write a program to guess the reproductive history of BitVectors from their genetic material. The randomly-ordered file bitvectors-genes.data.gz contains a 10,000 bit line for each individual. Your program's output should be, for each input line, the 0-based line number of that individual's parent, or -1 if it is the progenitor. Balance performance against probability of mistakes as you see fit.

To help you test your program, here is a much smaller 500 x 500 input dataset: bitvectors-genes.data.small.gz, along with its solution file: bitvectors-parents.data.small.

Implement a simple standalone TCP-based chat server, using the following protocol:

The server responds to all commands with either:

    OK<CRLF>

or, when an error occurred, with:

    ERROR <reason><CRLF>

<CRLF> indicates the bytes '\r\n'.

Upon connecting to the server, the client sends:

    LOGIN <username><CRLF>

Clients can create new chatrooms or join existing chatrooms (chatrooms begin with the character '#') by doing:

    JOIN #<chatroom><CRLF>

Clients can leave chatrooms by sending:

    PART #<chatroom><CRLF>

Clients can be in multiple chatrooms at once.

Clients can send a message to a chatroom:

    MSG #<chatroom> <message-text><CRLF>

Clients can send a message to another user:

    MSG <username> <message-text><CRLF>

When a message is sent to a chatroom the user is in, the server sends to the appropriate client:

    GOTROOMMSG <sender> #<chatroom> <message-text><CRLF>

or if the message is sent directly from one user to another:

    GOTUSERMSG <sender> <message-text><CRLF>

Finally, the client can log off by sending:

    LOGOUT<CRLF>

    C: LOGIN alice 

    S: OK

    C: JOIN #news

    S: OK

    C: MSG #news hi everyone

    S: GOTROOMMSG bob #news nothing much happened after that

    S: OK

    S: GOTROOMMSG alice #news hi everyone

    S: GOTUSERMSG carol hi alice, where've you been?

    C: MSG carol on vacation

    S: OK

    C: LOGOUT

    <server closes connection>

Data provided by MovieLens at the University of Minnesota.

Strawberries are growing in a rectangular field of length and width at most 50. You want to build greenhouses to enclose the strawberries. Greenhouses are rectangular, axis-aligned with the field (i.e., not diagonal), and may not overlap. The cost of each greenhouse is $10 plus $1 per unit of area covered.

Write a program that chooses the best number of greenhouses to build, and their locations, so as to enclose all the strawberries as cheaply as possible. Heuristic solutions that may not always produce the lowest possible cost will be accepted: seek a reasonable tradeoff of efficiency and optimality.

Your program must read a small integer 1 ≤ N ≤ 10 representing the maximum number of greenhouses to consider, and a matrix representation of the field, in which the '@' symbol represents a strawberry. Output must be a copy of the original matrix with letters used to represent greenhouses, preceded by the covering's cost. Here is an example input-output pair:

4
..@@@@@...............
..@@@@@@........@@@...
.....@@@@@......@@@...
.......@@@@@@@@@@@@...
.........@@@@@........
.........@@@@@........

90
..AAAAAAAA............
..AAAAAAAA....CCCCC...
..AAAAAAAA....CCCCC...
.......BBBBBBBCCCCC...
.......BBBBBBB........
.......BBBBBBB........

Run your program on the 9 sample inputs found in this file and report the total cost of the 9 solutions found by your program, as well as each individual solution.

Objective You want to meet a friend at O'Hare airport at noon and return home the same day. Given a date and an origin airport, find the pair of nonstop flights that gets you to Chicago and home again on that date, minimizing your total time away from home, subject to the constraint that you are at O'Hare at noon.

Details Your program, which must be written in Java, will work by scraping our http://matrix.itasoftware.com website. Create an account on that site called "candidate_YourName" for your program to use. (Please include your name and email address in your registration in case we need to contact you.) Your program should accept two command-line inputs as follows:

   java -jar OHareAffair.jar YYYY-MM-DD airportCode

For example, for a traveler from Baltimore on July 4th, your program might be invoked as follows:

   java -jar OHareAffair.jar 2006-07-04 BWI

   Travelling round-trip from BWI to ORD on 2006-07-04:

   Trip length: 6:21
   Outbound: American Airlines Flight AA3991 (10:03a-11:04a)
   Return: United Airlines Flight UA1236 (1:30p-4:24p)

   Trip length: 6:39
   Outbound: United Airlines Flight UA641 (9:45a-10:47a)
   Return: United Airlines Flight UA1236 (1:30p-4:24p)

   Trip length: 6:54
   Outbound: American Airlines Flight AA3991 (10:03a-11:04a)
   Return: American Airlines Flight AA4009 (2:09p-4:57p)

Strive to make your code clean and robust, and to report errors cleanly. Be sure to include your source, any necessary libraries, and instructions on how to run it.

To be precise: if the integers from 1 to 999,999,999 are expressed in words (omitting spaces, 'and', and punctuation[1]), and sorted alphabetically so that the first six integers are

• eight
• eighteen
• eighteenmillion
• eighteenmillioneight
• eighteenmillioneighteen
• eighteenmillioneighteenthousand

• twothousandtwohundredtwo

The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?

[1] For example, 911,610,034 is written "ninehundredelevenmillionsixhundredtenthousandthirtyfour"; 500,000,000 is written "fivehundredmillion"; 1,709 is written "onethousandsevenhundrednine".