Lab 10

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.

Setup instructions #

Head to http://url.cs51.io/lab10 and follow the Lab Procedures.

Lab puzzle #

Figure 1: Sorting the exam

Little known fact about how we grade exams. We have all of the exams scanned in, and then have one of the teaching staff sort the already scanned-in paper midterms in order of the student ID on the first page. (I’ll explain why if you’re interested.) We use the following physical sorting algorithm (depicted in Figure 1):

  1. Place each midterm in a pile according to the first digit of its HUID. (You can see these piles in the figure.)

  2. For each pile,

    • Lay out the exams in the pile one by one in ID order in a long row on the floor, walking back and forth along the row inserting each exam where it goes.

    • Collect the exams in the row in order.

  3. Merge all of the piles into one to form the final sorted set of exams.

What is the worst-case asymptotic time complexity of this algorithm in terms of the number of exams $n$? (Assume that any operation involving manipulating a single exam or pile or walking along the row past an exam or stack of exams occurs in constant time.) In case of multiple correct answers, pick the tightest one.