Question 1
Imagine that you are building an online plagiarism checker, which allows teachers in the land of Edutopia to submit papers written by their students and check if any of those students have copied whole sections from a set, D, of documents written in the Edutopian language that you have collected from the Internet. You have at your disposal a parser, P , that can take any document, d, and separate it into a sequence of its n words in their given order (with duplicates included) in O(n) time. You also have a perfect hash function, h, that maps any Edutopian word to an integer in the range from 1 to 1,000,000, with no collisions, in constant time. It is considered an act of plagiarism if any student uses a sequence of m words (in their given order) from a document in D, where m is a parameter set by parliament. Describe a system whereby you can read in an Edutopian document, d, of n words, and test if it contains an act of plagiarism. Your system should process the set of documents in D in expected time proportional to their total length, which is done just once. Then, your system should be able to pro- cess any given document, d, of n words, in expected O(n + m) time (not O(nm) time!) to detect a possible act of plagiarism.
Create a java implementation CheckPlagiarism.java that takes 3 commandline arguments - the corpus filename, the target filename and the length of the match sequence.
The corpus file has the format
:
For ex
134:"The quick brown fox jumped over the lazy dog"
145: "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc pellentesque turpis lorem, at convallis massa euismod quis. Cras blandit rutrum lacus tempor suscipit. Vestibulum in sagittis sem. Vestibulum id gravida felis. Morbi venenatis interdum purus a tincidunt. Aenean vel maximus magna."
The target file contains the text to be checked
For ex
The quick brown fox ate its breakfast slowly
The length is the minimum match required to prove plagiarism For ex 3
With the above example, your program should say "Plagiarized from 134". If the target were "The quick black fox ate its breakfast slowly" then it should print "Not Plagiarized". You may use standard implementations for string processing and hash tables.
Question 2:
Suppose there is a computer game, Land-of-Candy(LoC), where a player moves through a three-dimensional world defined by the cells in an n × n × n array, C. Each cell, C[i, j, k], specifies the number of points that a player in LoC gets when they are at position (i, j, k). At the start of a game in LoC, there are only O(n) nonzero cells in C; all the other O(n^3) cells in C are equal to 0. During the course of the game, if a player moves to a position (i, j, k) such that C[i, j, k] is nonzero, then all the points in C[i, j, k] are awarded to the player and the value of C[i, j, k] is reduced to 0. Then the game picks another position, (i', j', k'), at random and adds 100 points to C[i',j',k']. The problem is that this game was designed for playing on a large computer and now must be adapted to run on a smartphone, which has much less memory. So you cannot afford to use O(n^3) space to represent C, as in the original version. Describe an efficient way to represent C, which uses only O(n) space. Also describe how to lookup the value of any cell, C[i, j, k], and how to add 100 points to any cell, C[i, j, k], efficiently so that looking up the value of any cell, C[i, j, k], can be done in O(log n) worst-case time or better.
Implement the java version that plays Land-Of-Candy interactively.
A sample execution is shown below
tiny_mce_markergt; java LandOfCandy 100
Enter the next position (or p to print current board): 10 10 10
No candy here
Enter the next position (or p to print current board or q to quit): 10 20 10
Candy awarded! Total points: 100
Enter the next position (or p to print current board or q to quit): 73 20 10
Candy awarded! Total points: 200
Enter the next position (or p to print current board or q to quit): p
Candy found at
(11,22,33)
(65,78,16)
(99,99,99)
Enter the next position (or p to print current board or q to quit): q
tiny_mce_markergt;