15-121 SPRING 2010 [CORTINA]

LAB 2

In this lab, you will complete a class to represent a set of television channels for a cable TV system. The class will read the television channel data from a text file. Each television channel in the file consists of a number followed by a name on the same line. For example: 

101 National Geographic Channel
The first line in the file contains the number of channels stored in the file. Click HERE for a copy of the data file to view. NOTE: The channels in the file are already in alphabetical order based on channel name.

EXERCISES

Download the CableTV.zip project folder. Inside there is a class named Channel which represents a single TV channel with two fields, a number and a name, along with the usual accessors and mutators.

SETUP INSTRUCTIONS: When you extract the zip file, you should get a folder named CableTV with two folders inside: bin and src. Move this CableTV folder into your workspace for Eclipse. Then start a new project with the name CableTV.

  1. In the class named CableSystem, the constructor has one parameter specifying the name of the data file that contains the television channel data. The constructor opens the file and loads the data into an array leaving no empty cells. If the file is not there, it reports an error and exits the program. Read through the constructor and explain to your partner how it works. In the constructor, write additional comments to explain why the two indicated statements are needed.

  2. In the CableSystem class, complete the method search1 that performs a linear search of the array for the channel number given the name in the parameter. Examine only those channels that are necessary to determine your answer. The method should output the number of array cells that are examined during the search and then return the number of the channel corresponding to that name (if found) or -1 if not found. Use the main method in this class to test your solution before you move on.

  3. In the CableSystem class, complete the method search2 that performs a binary search of the array for the channel number given the name in the parameter. In binary search, examine the middle element for the target. If it is not there, examine the middle element of whichever half the target might be in. If that element is not the target, examine the middle element of whichever half of the halves the target might be in, ... etc. (See the course notes for an algorithm for binary search.) The method should output the number of array cells that are examined during the search and then return the number of the channel corresponding to that name (if found) or -1 if not found. Use the main method in this class to test your solution.

    Use the compareTo method of the String class to compare strings for lexicographical ordering. Lexicographical ordering is like alphabetical ordering, but includes uppercase, lowercase, digits, punctuation, etc. If s1 and s2 are Strings,

    s1.compareTo(s2) returns a negative integer if s1 comes before s2 lexicographically
    s1.compareTo(s2) returns a positive integer if s1 comes after s2 lexicographically
    s1.compareTo(s2) returns 0 if s1 is equal to s2

  4. Determine the maximum number of array cells that need to be examined in the search1 and search2 methods as a function of the number of channels in the array (call this n), and use the program to try to verify your solution. Complete the comment at the beginning of the CableSystem class that gives your answers with an explanation.

HANDIN

If you worked with another student, put both of your names in a comment at the beginning of your program. At the end of recitation, create a zip file of your program and submit it to the handin server http://handin.intro.cs.cmu.edu/v1. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER

  • Modify the constructor you wrote so that the channels are stored in the array in numerical order by number instead of channel name order. Modify the search methods correspondingly.

  • Modify the constructor so that the channels are stored in the array in random order. (Store them first and then shuffle them using a random number generator.) Which search method cannot be used now? Why?

  • Read up on inheritance and determine why we need to implement equals and hashcode methods in the Channel as they are.