The Word Count That Crawled
Mr. Okafor teaches a second-year programming course with 26 students. The assignment asks students to read a 50,000-word text file and produce the frequency of each word. Priya submits a program that stores each new word in a list and checks membership with a loop before updating a parallel count list. Her program produces correct output on a 500-word file but takes 9.4 seconds on the full file; the class target is under 2 seconds. She also counts punctuation as part of words, so run. and run are separate entries. The project deadline is in one 55-minute class period. Mr. Okafor has seen six other students use the same list-based pattern, while four used a dictionary. He wants to respond in a way that improves their algorithm design, not just Priya's grade. He is considering whether to fix the code himself, hold a whole-class code review, or assign a targeted peer conference.
1. Diagnose the performance problem in Priya's program. Explain the complexity of her approach and a better data structure choice, including any tradeoffs.
Read the worked answer
Priya's membership check scans the list of unique words for every word in the file. If there are n words and u unique words, the total work is proportional to n times u in the worst case, which is quadratic when u grows with n. At 50,000 words, that is far more comparisons than the class target can tolerate. A dictionary or hash map gives average constant-time membership and insertion, so the whole count becomes linear in n. A sorted list plus binary search would reduce the membership check to logarithmic time but would require maintaining sorted order on every insertion and would still be slower and more complex than a dictionary for this task. The tradeoff is memory: a dictionary stores keys and counts, but the list already stores the unique words, so the extra memory is modest. Priya also needs normalization for punctuation and case, which is a separate correctness issue. The key teaching point is that the data structure determines the scaling behavior.
2. Choose an instructional response for the 55-minute class and justify it. Address Priya's confidence and the six other students who used the same pattern.
Read the worked answer
Mr. Okafor should not silently rewrite Priya's code. A whole-class code review is appropriate because the misconception is shared by at least seven students, but it should be structured so Priya is not held up as a negative example. He can anonymize two programs, one list-based and one dictionary-based, and ask pairs to predict running time on 1,000, 10,000, and 50,000 words. Then groups run a timing experiment and graph the results. This makes the scaling visible without personal criticism. In the last 15 minutes, Priya's group can refactor the list version to a dictionary and compare outputs. The peer conference is useful for the punctuation bug, but it is not sufficient for the complexity issue because the other six students need the same conceptual experience. The response should preserve Priya's ownership by asking her to present the refactored version or the timing graph.
3. Design a short assessment that determines whether students can choose an appropriate data structure for a new problem, not just recall that dictionaries are fast.
Read the worked answer
The assessment should present a new but small scenario, such as a teacher who needs to check whether a student ID is enrolled in a club of 2,000 members and who also needs to print members alphabetically. Students should choose a structure, justify it, and identify the cost of the operations. A strong answer might choose a dictionary for membership checks and a separate sorted list for printing, or a balanced tree that supports both, and should explain the tradeoff rather than name a structure. Mr. Okafor should include a small trace or timing prediction, for example: how many comparisons does a list membership check make on average if the ID is absent? He should also ask students to revise Priya's normalization step by writing three test cases for punctuation and case. The rubric should reward reasoning about operation frequency, data size, and ordering requirements. This assesses transfer because the scenario is not the same word-frequency task.