LBSC 690: Introduction to Information Technology

Extra Credit Assignment

This assignment is worth 20 points. If you choose to do it, it is due before class on November 26.

LBSC 690: Extra Credit Assignment (Fall 2012)

The goal of this program is to type in a LOC subject code and for the program to return the name of subject associated with the code. For example, if you enter "F0178", the program should tell you "Atlantic coast. Middle Atlantic States: Maryland".

In the source file, there are three arrays, one with the start of the category (start), one with the end of the category (end), and one with the name of the category (name). The indices of the arrays are consistent. For example,

What you need to do is to complete the "Lookup" function so that it returns the category name.

The most efficient way to do this is called binary search. Start at the middle of all the arrays, and see whether the range you want is before or after your current position. Then do the same thing on either the first half or the second half of the list.

Note that there can be multiple categories that match - you can earn extra points for finding all valid categories (points for doing it as efficiently as possible).


You grade will depend on how efficient your implementation is. If you need to go through all the entries every time, you won't get many points (but you'll get some). If you need to go through on average half the entries, you'll get more points. A perfect solution should take on average no more than 12 lookups to find the appropriate range. Also note that there are ways to improve your score: find all appropriate categories given a query, automatically reformat queries, detect ill-formed queries, or allow a user to gracefully exit. Send your edited HTML file as an attachement to jbg@umiacs.umd.edu with the subject starting with [LBSC690 EC]. Make sure you name your HTML file your OIT username.