Background

Radio stations have a challenging job: Creating a daily play-list. At the beginning of each day, a radio station creates a daily play-list (a list of songs that it will play for that day). If a radio station wishes to stay in business, it will choose the songs that are likely to be most popular. It has been observed that the number of requests for a song in the preceding days is a good predictor of whether the song will be popular in the future. In fact, requests in recent days are better predictors of a song's popularity than requests in earlier days. For a given song, this observation is modeled by the exponential moving average: Pt = RtW + Pt-1(1 -W) where Pt is the predicted popularity of the song after day t, Rt is the fraction of requests for the song out all requests on that day, Rt = (# of requests for the song on day t) / (Total # of requests on day t) and W is the weight given to more recent requests and is in the range 0 ...1.

Problem 1 (C Grade): Radio Ga Ga

Given a list of songs, and sequences of daily song requests your program will need to create a play-list of a specied length that the radio station should play. Write a program called RadioGaGa.java that reads in a song list, and a sequence of song requests, spanning multiple days, and outputs a play-list of specied length for each following day. Input The input comprises a number of lines. The first line, contains an integer N, denoting the number of songs in the song list. This is followed by N lines, enumerating the songs. Each line consists of three values: a single word, denoting the title of the song; an integer T, denoting the length of the song (in seconds); and decimal value between 0 and 1 denoting the initial popularity of the song. For example: Red_Barchetta 371 0.5 The next line contains three values: an integer T, denoting the maximum length (in minutes) of the play-list, a double W denoting the weight attributed to new requests (see the formula above); and an integer D denoting the number of days of song requests to follow. For example, 22 0.5 2 species a T = 22 minute play-list, with a weight W = 0:5, and D = 2 days of song requests. Each day of requests consists of a number of lines. The first line contains the integer R, denoting the number of song requests to follow. The next R lines contain song titles from the previously loaded song list. (See Example section.)

Processing

The day 0 of programming begins after the list is read. Each following day begins after a day of song requests have been read. The play-list should be as close to the specified time T as possible without exceeding T minutes. Songs should be added to the list according to popularity (most popular to least pop- ular), with ties broken by song length. For example, if two songs are equally popular, the shorter one is preferred. If a song is too long to t on the play-list, it is passed over. The order of the songs on the play-list should be the order in which they were added. Output For each day (0 ...D) your program should output a play-list. I.e., there should be D + 1 play-lists. Each play-list consists of single line. Each line starts with an integer denoting the day followed by the play-list song titles in the order specified, separated by spaces. Each line is terminated by a new-line character. See next section for example of output. Example Sample Input 13 The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.55 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 22 0.5 2 5 Red_Sector_A Red_Sector_A Vapor_Trails Red_Sector_A Test_For_Echo 6 The_Garden Vapor_Trails 2112_Overture The_Garden Test_For_Echo 2112_Overture

Sample Output

0 Closer_To_The_Heart The_Garden Red_Sector_A The_Pass 1 Red_Sector_A Closer_To_The_Heart The_Garden The_Pass 2 The_Garden Red_Sector_A Closer_To_The_Heart Test_For_Echo Problem 2 (B Grade): Radio Network Instead of a single radio station, your program has to make play-lists for several radio stations that share the same song list. But, each radio station has its own demographic, which will result in song ratings that vary from station to station. Given a list of songs, and sequences of daily song requests for your radio stations, your program will need to create a play-list of a specifed length for each of the radio stations. Write a program called RadioNetwork.java that reads in a song list, a list of radio stations, and a sequence of song requests, spanning multiple days, and outputs a play-list for each radio station of specied length for each following day. Input The input is very similar to Problem 1. The first part of the input is a list of songs, identical to the input format in Problem 1. The song list is followed by two integers: an integer S, denoting the number of stations; and an integer D denoting the number of days, just like in Problem 1. These are followed by S radio station specifications. Each station specification consist of: a station identifier; the length of the play-list, T, in minutes (just like in Problem 1); and the weight W (just like in Problem 1). For example, CBC1 22 0.5 The last part of the input are the requests, these are similar to Problem 1, except that each request consists of two words: the identifier of the radio station to which the request was sent and the song title. For example, CBC1 The_Garden Please see full example below. Processing The processing is the same as in Problem 1 except for the following differences. Each radio station can have its own length of play-list T and its own weight W. A song request aspects the ratings of a song at the specified radio station and not all radio stations. That is, the request rate Rt for a song at a radio station is Rt = (# of requests for the song on day t at specified radiostation) / (Total # of requests on day t at specified radiostation) Each station's requests are only counted for the specified radio station. Output For each day (0 ...D) your program should output a play-list for each radio station. I.e., there should be S (D + 1) play-lists. The output for each day begins with an integer denoting the day. This is followed by S lines, each displaying a play-list for a radio station. Each play-list consists of single line. Each line has the format: + Station: Song1 Song2 Song3 ... For example, + CBC1: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass Each line is terminated by a new-line character. The play-lists should be in the same order as the input order of the radio stations. Example Sample Input 13 The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.55 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 3 1 CBC 22 0.5 CBC1 22 0.5 CBC2 22 0.5 5 CBC Red_Sector_A CBC1 Red_Sector_A CBC2 Vapor_Trails CBC Red_Sector_A CBC Test_For_Echo Sample Output 0 + CBC: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC1: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass + CBC2: Closer_To_The_Heart The_Garden Red_Sector_A The_Pass 1 + CBC: Red_Sector_A Closer_To_The_Heart The_Garden Test_For_Echo + CBC1: Red_Sector_A Closer_To_The_Heart The_Garden The_Pass + CBC2: Vapor_Trails Closer_To_The_Heart The_Garden Red_Sector_A

Problem 3 (A Grade): Radio Difference As a radio network baron, you are always in the lookout to cut corners and save money. If two radio stations are playing similar play-lists, then you can save money by eliminating one of the radio stations or aiming it at a different demographic. You need to determine which of your stations are too similar. The difference between two radio stations is defined as the sum of squares of the differ- ences between the ratings of the song ratings. That is, all radio stations have the same set of songs, each with their own ratings. Suppose the ratings for the songs at radio station U are u0, u1, u2,....uN, and the ratings for the same songs at radio station V are v0, v1, v2... vN, where ui and vi are ratings for the same song at the respective radio stations. Then the dierence between the two radio stations is: D(U; V ) = (u0 - v0)2 + (u1 -v1)2 + (u2 -v2)2 + ... + (uN - vN)2 If D(U; V ) is smaller than the specifed similarity threshold, then the two radio stations are too similar. Given a list of songs, and sequences of daily song requests for your radio stations, your program will need to determine if each pair of radio stations is too similar. Write a program called RadioDifference.java that reads in a song list, a list of radio stations, a sequence of song requests, and a similarity threshold. The program outputs all pairs of radio stations whose difference is less than the similarity threshold after all the requests in each day have been processed. Input The input is the same as Problem 2, except for one small difference. The song list is followed by three numbers (not two): an integer S, denoting the number of radio stations; an integer D, denoting the number of days of requests; and lastly, a double X, denoting the the similarity threshold. Please see full example below. Processing The processing is the same as in Problem 2 except that no play-lists are generated. Once all requests are processed, the difference for each pair of stations is computed and all pairs of stations whose difference is below the similarity threshold are displayed. Each pair that is displayed should only be displayed once, and the order of the stations should match the input order. Output For each pair of stations whose difference is below the similarity threshold, output the line Difference between U and V is below threshold where U and V are the station identifiers of the two stations. Note, that U must come before V in the radio station list. See next section for example of output. Example Sample Input 13 The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.55 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 3 1 0.2 CBC 22 0.5 CBC1 22 0.5 CBC2 22 0.5 5 CBC Red_Sector_A CBC1 Red_Sector_A CBC2 Vapor_Trails CBC Red_Sector_A CBC Test_For_Echo Sample Output Difference between CBC and CBC1 is below threshold