This lab helps students gain experience and proficiency with algorithm analysis and the concept of time complexity. Students will not write code, but rather will identify mystery code based on run times for different input sizes.
This assignment provides students with four short code segments and a program with a graphical interface. The provided program allows students to enter an input size and run one of four ‘mystery’ algorithms. Elapsed time is displayed after each run. Students must match code segments with 'mystery' algorithms. This requires that students plot run times for different input sizes for each 'mystery' algorithm, identify the asymptotic run time (big-O) of each code segment, then perform the matching.
Before attempting this assignment, students need a basic understanding of algorithm analysis, equivalent to one or two lectures on the topic and the ability to read and understand code written by someone else, including loops and arrays.
This assignment is inspired by David Levine’s Sort Detective. It is intended to be used in the same semester and can serve as a “warm-up” for that assignment.
I created this assignment for our second Computer Science course (Data Structures), which is taught to both majors and non-majors. This course draws an extremely diverse group of student with a wide range of previous experience with mathematics and problem solving. This assignment was given the second week of the semester and Sort Detective was assigned approximately 2/3 of the way through the semester.
Tips:
While this assignment could be given as a take home assignment, it is best in a small lab setting with an instructor circulating. Students may notice spikes and other behaviors in their observations of run time that they cannot explain. I use this as a way to informally discuss Java garbage collection, the behavior of the Java Virtual Machine, background processes, and other factors related to how an algorithm behaves in the real world. Alternatively students may be simply told that just as with all 'real' data, their observations will be noisy and and an average over multiple trials may be needed to spot trends.
The assignment may be used in classes taught using languages other than Java by changing the code snippets supplied to the students to the language of instruction or to pseudocode. The Java program (.jar) supplied may still be used in a non-Java class, as the students only need to run, not interact with that code.
Mischievous students have occasionally attempted to circumvent the assignment by decompiling or otherwise looking under the hood of the provided GUI. I explicitly forbid this and enforce it by awarding the majority of the points of the assignment for the students’ methods, reasoning, and supporting data, and few points for a correct matching.
This assignment provides a hands-on introduction to algorithm analysis and may allow a greater number of students to succeed with the topic, particularly those with less previous exposure to abstract concepts. Student feedback has indicated that the assignment was very useful in clarifying and cementing theoretical concepts.
This assignment does not require any coding by the students, and thus emphasizes that computer science is not just programming. For our students, it is one of their first experiences with a computer science assignment that is not coding focused and the first occasion where they are required to write anything of significance in order to convey their ideas in a computer science setting.
Students work in groups of two or three to solve the 'mystery,' and because of the computer time required for multiple runs of several algorithms at several input sizes, all members of the group need to communicate and participate in a hands on way in order to finish in a timely manner.