#### DocDiff

##### 1Introduction

Consider the problem of comparing two text documents. Why might you want to do this? Perhaps you want to check for plagiarism, search for articles similar to a particular one you’re studying, or have uncovered a new manuscript and want to know whether it’s a legitimate Shakespeare or a fake. All these require being able to determine the similarity between documents.

##### 2Theme Song

Changes by David Bowie

##### 3Definition

In this assignment we will define a document as a List<String>, with each string representing a word. Here’s an example of a document:
 [list: "The", "quick", "brown", "fox", "jumps"]

In order to compute the similarity between two documents, we associate each document with a mathematical vector, which here we will represent using a list of numbers. The indices of the vector correspond to words that are found in either document. The value at each index is how many times the corresponding word occurs in the document.This is called the bag of words model. It’s a “bag” because, like a set, order doesn’t matter, but the count does.

For example, the documents [list: "a", "b", "c"] and [list: "d", "d", "d", "b"] would result in vectors of length 4, accounting for all unique words ("a", "b", "c", and "d"):

 "a" "b" "c" "d" [list: "a", "b", "c"] 1 1 1 0 [list: "d", "d", "d", "b"] 0 1 0 3

Therefore, the two documents will respectively have the representations [list: 1, 1, 1, 0] and [list: 0, 1, 0, 3].

Note: When comparing two documents, the same length vector is used for both documents because the vector accounts for all the words across both documents.

We assume that two words are the same if they have the same characters in the same order, ignoring upper- and lower-case (Pyret has functions to upper- or lower-case a string, and for sorting; you can look up these functions in the string and list libraries.)

We define the overlap between two documents, represented this way, to be proportional ($$\propto$$) to the dot product of these two document vectors:

$overlap(\vec{d_1}, \vec{d_2}) \propto \vec{d_1} \cdot \vec{d_2}$

To obtain a formula, we normalize this dot-product. We will choose a simple method, which is to divide by the squared magnitude of the larger vector:

$overlap(\vec{d_1}, \vec{d_2}) = \frac{\vec{d_1} \cdot \vec{d_2}}{max(\|\vec{d_1}\|^2,\|\vec{d_2}\|^2)}$

where the magnitude of a vector $$\vec{x}$$, denoted as $$\|\vec{x}\|$$, is given by $$sqrt(\vec{x} \cdot \vec{x})$$. Observe that this means every document will have an overlap of 1 with itself, and any two documents that have no words in common will have overlaps of 0 with each other.

##### 4Assignment

Define a function
 fun overlap(doc1 :: List, doc2 :: List) -> Number: ... end
where doc1 and doc2 are lists of strings and overlap returns a number. This function computes the overlap of two non-empty documents, defined by the formula above. You should not round any of the calculated numbers.

Note that we are not asking you to consider efficiency of implementation.

##### 5Language Use

You may not use built-in sets; everything in the list library is permitted. You will also need the string library.

Recall from Assignments that you should not use any other built-in functions or libraries unless an assignment explicitly permits you to.

##### 6Background

You will find this chapter useful in learning to convert from Racket to Pyret, and this one useful for learning more about lists in Pyret.

##### 7A Warning

You’ll be reusing DocDiff later in the semester! Therefore, if you falter in this assignment, you’ll want to make sure you understand what you did wrong.

Template

##### 9Computing and Society

How well do plagiarism detectors actually work?

Write

In your submission, you will be asked to paste your favorite paragraph, sentence, and phrase from the reading or, if it’s a video (as some will be), to transcribe your favorite sentence, phrase, and word.

In addition, your homework is to go to this plagiarism checker and paste something from an article into it. Then, tweak your snippet to try and trick the detector without changing the meaning of your snippet. What is the most interesting tweak you were able to make? Think of this as a testing exercise for the software!

Your writeup of your findings should be brief and crisp. Anything longer than three paragraphs (excluding the text you pasted in, of course) is definitely too long. Be concrete by drawing on your experience. You can prepare your writeup in whatever editor you want; submit in text or PDF.

##### 10General Instructions

Please keep these instructions in mind for the rest of the semester:
• Many of your assignments will have a computing and society component, as above. In each case, we will expect you to provide some proof of having read/watched the work. Your writeup must follow the instructions above except if we indicate otherwise.

• The starter template (as above) gives names for files. Please don’t change these! The autograder is expecting the same names, so you know how that goes.

##### 11Friendly Reminders

Since this is your first assignment, we want to provide a few reminders here:
• The textbook is free and online. It can be very helpful in reviewing lecture content and finding examples if you get stuck.

• The Pyret Documentation is online.

• You are expected to follow the practices of the Pyret style guide.

• The course staff is here to help you! If you have any questions, make sure to come to hours [Staff] or post on Campuswire.

• Remember to test your functions thoroughly!

##### 12Handing In

You will submit three separate files, named docdiff-code.arr, docdiff-tests.arr, and docdiff-common.arr (which may effectively be empty).