On-line advertising has been one of the most booming markets since the first on-line ads showed up on the web and now it is a market of hundreds of billions of dollars globally and it still has not lost the steam. Google got $32.2 billion in advertising revenue which is 97% of Google’s total revenue in Q3 2010 - Q2 2011. By far the most lucrative venue for on-line advertising has been search, and much of the effectiveness of search advertising comes from the “AdWords” model of matching search queries to advertisements. For this project, you need to use Java to access an Oracle database and accomplish an on-line ads auction system using various bidding algorithms. 1.1.1 Definition of the AdWords Problem We are going to consider on-line algorithms for solving the AdWords problem, which is defined as follows. Given: • A set of bids by advertisers for search queries; • A click-through rate for each advertiser-query pair; • A budget for each advertiser; • A limit on the number of ads to be displayed with each search query. Respond to each search query with a set of advertisers such that: • The size of the set is no larger than the limit on the number of ads per query. • Each advertiser has bid on the search query. • Each advertiser has enough budget left to pay for the ad if it is clicked upon. The data set consists of three database tables: (primary keys are underlined) Queries(qid:INTEGER, query:VARCHAR(100)) Advertisers(advertiserId:INTEGER, budget:FLOAT, ctc:FLOAT) Keywords(advertiserId:INTEGER, keyword:VARCHAR(100), bid:FLOAT)