Lab 10 Instructions #
Reminders #
Get out paper and pencil. You’ll need it for this lab.
Don’t forget to check out the lab solutions, distributed tomorrow.
Do you have hints or tips about the course? Let us know: heads@cs51.io .
Setup instructions #
Head to http://url.cs51.io/lab10 and follow the Lab Procedures.
Lab puzzle #
Figure 1: Returning exams old school
Today’s lab puzzle is about returning graded exams old school: The n students have mailboxes labeled 1..n. The papers are in some random order. We use the following algorithm for distributing the papers to the students.
- Start at mailbox 1.
- For each exam in order:
a. Look up the mailbox number for the student.
b. Go to that mailbox and deposit the exam.
What is the worst-case asymptotic time complexity of this algorithm in terms of the number of exams (and mailboxes) n? (Assume that the operations taking constant time include inserting an exam in a mailbox and walking from one mailbox to an adjacent one.) In case of multiple correct answers, pick the tightest one.