1

In another post, user1723 touched on a question I had while watching the lecture, sections, and walkthrough on pset6.

The question was, why would we need to sort our linked lists, when dictionaries, by nature, are already sorted?

During lecture, section and walk-through, references to the trade-off between "time needed to search an unsorted linked list" and "time spent sorting the list" seemed to ignore this huge elephant in the room: If the dictionary is sorted, then hashing it into linked lists by entering each new element at the beginning of its list would result in lists that are sorted in reverse order.

The obvious question, then, is: When this assignment is graded, are they planning to deliberately test it with an unsorted list of words that they are calling a "dictionary"?! (One respondent to user 1723 suggested that this is indeed a possibility.)

To me, calling an unsorted list of words a dictionary is as ridiculous as calling a random list of numbers a phone directory or calling a random list of cities a map.

It strikes me as rather deliberately perverse -- perverse, here, in the sense of "obstinately opposing what is reasonable" -- to claim your file is a "dictionary" if it is really a set of words in random order.

So... I'm gathering we need to proof our program against that sort of perversity anyway? I.e., is it correct to assume that a binary search of a "dictionary" we haven't spent time re-sorting ourselves is going to fail when graded?

2

Your question is:

When this assignment is graded, are they planning to deliberately test it with an unsorted list of words that they are calling a "dictionary"?!

You can assume that the 'dictionary' list of words given to you is sorted.

As the pset says:

You may assume that any dictionary passed to your program will be structured exactly like ours, lexicographically sorted from top to bottom with one word per line, each of which ends with \n. You may also assume that dictionary will contain at least one word, that no word will be longer than LENGTH (a constant defined in dictionary.h) characters, that no word will appear more than once, and that each word will contain only lowercase alphabetical characters and possibly apostrophes.

Staff would not explicitly tell you to assume a sorted dictionary if they were then going to throw an unsorted one at you.

1

The question was, why would we need to sort our linked lists, when dictionaries, by nature, are already sorted?

I assume because your program can accept an optional dictionary which might not be sorted as you want.

When this assignment is graded, are they planning to deliberately test it with an unsorted list of words that they are calling a "dictionary"?

Why not? You're program is supposed to be loading a dictionary. Regardless of whether it's already sorted or not, your program should be functioning correctly. Imagine a case in which you rely on the loaded dictionary being sorted while it's not. Serious problems could happen, right?

Also, there's many ways of sorting a dictionary. So a dictionary could be already sorted but not alphabetically maybe.

This is just my assumption. At the end, we're learning and practicing. It wouldn't harm if we learnt how to keep a linked-list sorted regardless of anything.

1

To me, calling an unsorted list of words a dictionary is as ridiculous as calling a random list of numbers a phone directory or calling a random list of cities a map.

It strikes me as rather deliberately perverse -- perverse, here, in the sense of "obstinately opposing what is reasonable" -- to claim your file is a "dictionary" if it is really a set of words in random order.

This usage is neither ridiculous nor perverse, it's just not one you've encountered before. In the computer science world, the term "dictionary" refers to an associative array:

Associative Array


From Wikipedia, the free encyclopedia

"Dictionary (data structure)" redirects here. It is not to be confused with data dictionary.

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

The fact that none of the words in the input dictionary are accompanied by definitions is a pretty big clue that the term "dictionary" wasn't being used the way you expected. Take note also that the problem set specification explicitly defined the dictionary variable:

Notice, incidentally, that we have defined the usage of speller to be

Usage: speller [dictionary] text

where dictionary is assumed to be a file containing a list of lowercase words, one per line...

The specs do go on to point out that the particular file they have provided you to use as the dictionary variable is sorted lexicographically (i.e., in alphabetical order) but nowhere do they say that you should assume this will always be the case.

Programming involves lots of special terminology and named variables that don't exactly describe what they store for the sake of keeping the name to a manageable length. You should try to get used to reading the specs carefully for what they say and not bringing in outside assumptions that might change your understanding of the problem.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .