University of Arizona, Department of Computer Science

CSc 120: Fake News

This program is behaviorally identical to the fake news program from Assignment 6, with three exceptions:

The program will be altered to use Python lists instead of your LinkedList class.
Sorting will be done using the merge sort algorithm. (Merging of lists starts on slide 88 in the class notes on recursion. Slides on merge sort then follow.)
If more than one word has the same count, those words are shown in alphabetical order, as specified under Output Format.

Expected Behavior

As in Assignment 6. Your program should be in a file fake_news_ms.py.

Recursion Limit

Python will hit the recursion limit with the double recursion in msort(). To prevent this, you need to import sys import sys at the top of your program. Then in your main() function, set the recursion depth with the call sys.setrecursionlimit(4000).

Input format

As in Assignment 6.

Output format

As in Assignment 6 but with an important difference: if more than one word has the same count, those words are shown in alphabetical order. Here are two places in the example output where that ordering is evident:

In example 1 note that "the" and "trump" both appear 35 times; "the" is shown first because it is lexicographically less than "trump".
In example 2 there is a four-way tie between "are", "fbi", "not", and "over".

In the vernacular of sorting it is said that the count is a primary key and the word itself is a secondary key.

Programming Requirements

Instead of using a LinkedList that contains instances of Node, change your code to use a Python list that contains instances of a new class, Word:
class Word
An object of this class represents information about a word. It should contain (at least) the following attributes:
- _word: the word string.
- _count: a count of the number of occurrences of the word.
It should implement (at least) the following methods:
- __init__(self, word): initializes the object's attributes as follows: _word is set to word; _count is set to 1.
- word(self): returns the value of _word.
- count(self): returns the value of _count.
- incr(self): increments the value of _count.
- __lt__(self,other) returns True if self.word() is less than other.word() and False otherwise.
- __str__(self) and, optionally, __repr__(self).
On assignment 6 you wrote a sort() method for LinkedList. In this problem the Python list of Word instances must be sorted using the merge sort algorithm. Code for the msort(L) function is shown in the slides on recursion class notes on recursion.

Errors

As in Assignment 6, there is no error checking required for this program.

Examples

Some examples of the behavior of this program are given here.