Homework 1

Question 1.9 from the course text.

If you have already spoken to me about not being in town, then send your homework via email to hussein@vt.edu before 11am on 8 July (There are only 2 of you - any other files I receive will be ignored). All others must print out and submit the homework at the beginning of class.

Questions and Answers

• Q I am working on this problem now and so far I have written an algorithm for how to do the spell checking. I was wondering when the book says "time constraints" are we talking clock cycles, or nanoseconds or something diffrent altogether. Also I am assuming primitive operations means comparisons assignment statements etc. Right?
• A The question does not ask for an algorithm. It asks for a list of the "primitive operations" that must be implemented, and time constraints for each. In the context of data items and data structures, examples of operations that we spoke about today in class would include "search", "insert at head", "delete", "add", "multiply". Note that this question just requires a brief analysis - please do not get bogged down in details. Do not write code, and do not write algorithms. Think at the level of a "document" and a "dictionary".

• Q For the homework do we need to go into detail? For example when searching the dictionary for a word should we tell if we are using a binary search, etc?
• A The question does not ask what data structure should be used. It asks for the constraints of the problem. Simply provide a list of typical operations and typical time constraints on those, taking into account the size of the "document" and the "dictionary".

• Q I am still not sure of the time constraints, could you give me just 1 example and i can go off that.
• A Suppose we are sorting numbers (this is a different example) and we wish to sort 1000 sets of 20 numbers. Define sorting of 20 numbers to be a primitive operation. Suppose we wish to do this fairly quickly - let us define quickly as 10 seconds. Then the primitive operation of sorting 20 numbers should take at most 0.01 second.

Solution

1. Build-dictionary (taking a maximum of, say, 10 seconds) - creates a representation of the dictionary in main memory.
   • Includes 20000 Insert-into-dictionary operations, each of which will need to take an average of 0.0005 seconds.
   • Insert-into-dictionary may be preceded by Read-word-from-dictionary, which sequentially reads in a dictionary word from the ASCII listing in secondary storage. The time taken for this must be incorporated into the 0.0005 seconds (if we assume that I/O operations take the most time then the whole 0.0005 seconds would be allocated to this operation, and the previous one would require a relatively negligible amount of time)
2. Find-word-in-dictionary - checks if a particular word is in the dictionary.
   Suppose the maximum reasonable time to search 20 pages is 20 seconds. This means that each page must take at most 1 second. Assuming 66 lines per page and 14 words per line, this implies a time constraint of approximately 0.001 second per search operation.
   • This could be preceded by Read-word-from-document, which will take a negligible amount of time if we assume the document is in main memory.