Write program to implement autocomplete for given set

Assignment Help JAVA Programming
Reference no: EM131423523

Assignment

1. Purpose

The purpose of this assignment is to implement sorting algorithms for the autocomplete application.

2. Description

Write a program to implement autocomplete for a given set of N terms, where a term is a query string and an associated nonnegative weight. That is, given a prefix, find all queries that start with the given prefix, in descending order of weight.

Autocomplete is pervasive in modern applications. As the user types, the program predicts the complete query (typically a word or phrase) that the user intends to type. Autocomplete is most effective when there are a limited number of likely queries. For example, the Internet Movie Database uses it to display the names of movies as the user types; search engines use it to display suggestions as the user enters web search queries; cell phones use it to speed up text input.

In these examples, the application predicts how likely it is that the user is typing each query and presents to the user a list of the top-matching queries, in descending order of weight. These weights are determined by historical data, such as box office revenue for movies, frequencies of search queries from other Google users, or the typing history of a cell phone user. For the purposes of this assignment, you will have access to a set of all possible queries and associated weights (and these queries and weights will not change).

The performance of autocomplete functionality is critical in many systems. For example, consider a search engine which runs an autocomplete application on a server farm. According to one study, the application has only about 50ms to return a list of suggestions for it to be useful to the user. Moreover, in principle, it must perform this computation for every keystroke typed into the search bar and for every user!

In this assignment, you will implement autocomplete by sorting the terms by query string (with running time O(N log N) in sorting, or even better, where N is the of terms); binary searching to find all query strings that start with a given prefix (with running time O(log N)); and sorting the matching terms by weight (with running time O(M log M) in sorting, where M is the number of matching terms). Finally display results for the user. The following shows the top seven queries (city names) that start with AI M with weights equal to their populations.

Part 1: Autocomplete Term

Write an immutable data type Term.java that represents an autocomplete term: a query string and an associated integer weight. You must implement the following API, which supports comparing terms by three different orders: lexicographic order by query string (the natural order); in descending order by weight (an alternate order); and lexicographic order by query string but using only the first r characters (a family of alternate orderings). The last order may seem a bit odd, but you will use it in Part
3 to find all query strings that start with a given prefix (of length r).

Part 2: Binary Search

When binary searching a sorted array that contains more than one key equal to the search key, the client may want to know the index of either the first or the last such key. Accordingly, implement the following API:

Corner cases. Each static method should throw a java.lang.NullPointerException if any of its arguments is null. You should assume that the argument array is in sorted order (with respect to the supplied comparator).

Performance requirements. The firstIndexOf() and lastIndexOf() methods should make at most 1 + ⌈log2 N⌉ compares in the worst case, where N is the length of the array. In this context, a compare is one call to comparator.compare().

Part 3: Autocomplete

In this part, you will implement a data type that provides autocomplete functionality for a given set of string and weights, using Term and BinarySearchDeluxe. To do so, sort the terms in lexicographic order; use binary search to find the all query strings that start with a given prefix; and sort the matching terms in descending order by weight. Organize your program by creating an data type Autocomplete with the following API:

Corner cases. The constructor should throw a java.lang.NullPointerException if its argument is null or if any of the entries in its argument array are null. Each method should throw a java.lang.NullPointerException if its argument is null.

Performance requirements. The constructor should make proportional to N log N compares (or better) in the worst case, where N is the number of terms. The allMatches() method should make proportional to log N + M log M compares (or better) in the worst case, where M is the number of matching terms. In this context, a compare is one call to any of the compare()or compareTo() methods defined in Term.

Input format for testing

We provide a number of sample input files for testing. Each file consists of an integer N followed by N pairs of query strings and nonnegative weights. There is one pair per line, with the weight and string separated by a tab. A weight can be any integer between 0 and 2^63 - 1. A query string can be an arbitrary sequence of Unicode characters, including spaces (but not newlines).

• The file wiktionary.txt contains the 10,000 most common words in Project Gutenberg, with weights proportional to their frequencies.
• The file cities.txt contains over 90,000 cities, with weights equal to their populations.

Attachment:- Attachments.rar

Reference no: EM131423523

Questions Cloud

How statistically significant is the evidence : How statistically significant is the evidence? What assumptions does your analysis require? Do these assumptions seem reasonable in this case?
Discuss three aspects in maintaining professional conduct : Discuss at least three aspects in maintaining professional conduct while working on a forensics investigation. Include why each is important in determining professional credibility.
How did consumerism-new technology change american culture : The roaring twenties as it is often referred observed dramatic changes in American culture. During the 1920's there were dramatic changes politically, socially, and economically in the United States. The United States started to prosper. Technolog..
Write a short report about what student loan borrowers : Compute a 95% confidence interval for each of the questions, and write a short report about what student loan borrowers think about their debt.
Write program to implement autocomplete for given set : CPS 350- Write a program to implement autocomplete for a given set of N terms, where a term is a query string and an associated nonnegative weight. That is, given a prefix, find all queries that start with the given prefix, in descending order of ..
Determine how government regulations affect compensation : Determine how government regulations affect compensation and if the regulations are needed. Support your position with examples
Create an ishikawa diagram : Review the scenario below and create an Ishikawa diagram to analyse the problem presented. You should identify as many possible causes of the problem as possible and categorise them on different 'strands' of the Ishikawa diagram.
Examine the common elements of compensation packages : Examine the common elements of compensation packages. Determine which two elements you believe to be the most motivational to an employee and to you. Support your position
State the population of given survey : State the population of this survey and some likely values from the population distribution. Also explain why you might expect this population distribution to be skewed to the right.

Reviews

Write a Review

 

JAVA Programming Questions & Answers

  Create web application uses visual web java server

Create the Web application which uses Visual Web Java Server Faces framework and either Apache Tomcat or Glassfish as the server.

  Create your java source file with the public class

Create your Java source file with the public class and main() method (like homework 1). In the main() method, add code to prompt for the input line, read in the line of input, and print it out.

  Write a program that takes 10 values representin

Using a loop, write a program that takes 10 values representin exam grades (between 0 and 100) from the keyboard and outputs the minimum value, maximum value, and average value of all the values entered. Your program should not accept less than 0 ..

  Primary care-secondary care and tertitary care

Discuss the differences among primary care, secondary care, and tertitary care and the 6 C's of primary care

  Program that computes and prints the value of 6!/5! using

Write a Java program that computes and prints the  value of 6!/5! using Scanner.

  History of java

Add a class FillInQuestion to the question hierarchy of How To 10.1. An object of this class is constructed with a string that contains the answer, surrounded by _ _, for example, "The inventor of Java was _James Gosling_". The question should be ..

  Write a java program that draws a square abcd

Write a java program that draws a square ABCD. The points A and B are arbitrarily specified by the user by clicking the mouse button. The orientation of the points should be counter-clockwise.

  Explain the meaning of polymorphism

Explain the meaning of polymorphism

  Calculates the cutoff frequency in a simple rc circuit

Write a simple Java application which calculates the cutoff frequency in a simple RC circuit

  Ceate an application which represents a simplified course

create an application which represents a simplified course registration system using arraylists and hashmaps.define a

  Specify, design, and implement a class

Specify, design, and implement a class that can be used in a program that simulates a combination lock. The lock has a circular knob with the numbers 0 through 39 marked on the edge, and it has a three-number combination, which we will call x,y,z.

  Write a program that establishes two savings accounts

Write a program that establishes two savings accounts with saver1 having account number 10002 with an initial balance of $2,000, and saver2 having account 10003 with an initial balance of $3,000

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd