Lab 10

Lab 10 Instructions #

Reminders #

  • The short graded writing and reviewing assignment for the Embedded EthiCS module is now posted at the CS51 Canvas site.

  • 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

This year’s exams will be done entirely online, so computers will be used to provide efficient access to individual exams. But in the bad old days, exams were taken by filling out the answers on paper. We would 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 used 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.