Lab 10

Lab 10 Instructions #

Reminders #

  • Tuesday’s class will be a lecture as part of the Embedded EthiCS program. The lecture will be held at the 10:30 am ET slot by Samuel Dishaw on ethical issues in software engineering.

  • There will be a short graded writing and reviewing assignment based on this lecture, so you will want to attend the lecture if at all possible. For those in the second lab slot who cannot attend the lecture, we will make available a video fo the lecture.

  • Get out paper and pencil. You’ll need it for this lab.

  • Don’t forget to check out the lab solutions, distributed tomorrow.

  • While you’re waiting for lab to begin in earnest, please read the lab puzzle on the next page.

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, we would have all of the exams scanned in, and then have one of the teaching staff sort the already scanned-in 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.

  1. 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.

A. $O(n)$

B. $O(n^2)$

C. $O(n\log n)$

D. $O(1)$

E. $O(10n)$

F. $O(n^3)$

G. $O(n/10)$

H. Not enough information to determine.