Quiz 08

Quiz 08


Important notes:
  1. Do not start until you are instructed to do so!
  2. You will have 20 minutes once the proctor says to start.
  3. You will have brief additional time after we stop to scan and submit your solutions.

  4. Just before the quiz...
    1. Have a fully-charged smartphone and laptop, and still plug both in if possible
    2. Log into Gradescope on your phone
    3. Change the screen timeout setting on your phone to never, so your screen doesn't go black if you don't interact with your screen for a while.
      • iPhones: Settings / Display & Brightness / Auto-Lock / Never
      • Android: Settings / Display / Screen timeout / 10 minutes (or the maximum amount of time)
    4. Turn on Do Not Disturb (or otherwise turn off all notifications).
    5. Position your webcam so we can see:
      • Your desk
      • The paper you are working on
      • Your writing utensil(s)
      • Both of your hands
      • Your phone

  5. During the quiz:
    1. You may not ask questions during the exam.
      • If you are unsure how to interpret a problem, take your best guess.
      • If you feel a question is unfair because you could not ask a question about it, please email the instructor after the quiz and describe your concern. (We are working hard to make the questions extra clear this year, but we want to know when we fail.)
    2. You may not touch your laptop or webcam.
      • This includes muting yourself at any point; the proctors may mute you though.
    3. All of these must be visible at all times:
      • Your desk
      • The paper you are working on
      • Your writing utensil(s)
      • Both of your hands
      • Your phone, with the quiz webpage
    4. For any tech fails (laptop or internet stops working, etc.):
      1. Stop taking the quiz
      2. Email the instructor (rileyrd@cmu.edu) right away
      3. We will reply soon to set up a 1-on-1 oral quiz with the course faculty

  6. After the quiz:
    1. Follow all proctor instructions on how to end the quiz.
    2. If you finish early, wait patiently until the end of the quiz. (Note: Don't use your phone...)
    3. Keep everything in view (as noted above) until the proctor calls "time".
    4. When instructed, use your phone to scan your quiz and submit the PDF to Gradescope.
    5. After submitting to Gradescope, hold your phone up to the webcam to show the receipt.
    6. Even then, remain in quiz mode until the proctor calls "all clear"

Question 1 - Short Answer [4 pts]

What does it mean for a sort to be stable?

Question 2 - Sort Tracing [4 pts]

Consider the “bubble up” operation from Bubble Sort. Assuming you are given the following array of numbers, give the new order for the array after one pass of the “bubble up” operation is performed. Note: You are not running bubble sort to completion. Instead, you are just doing one pass of the “bubble up” operation. Clearly label your final answer.

[68, 52, 85, 22, 94, 50, 12, 32]

Question 3 - Iterating [12 pts]

Consider the following code for a Student class and a School class:

public class Student {
    private String name;

    public Student(String name) {
        this.name = name;
    }

    public String toString() {
        return this.name;
    }
}

public class School {
    private ListNode head;

    private class ListNode {
        private Student data;
        private ListNode next;

        private ListNode(Student data) {
            this.data = data;
            this.next = null;
        }

        public String toString() {
            return data.toString();
        }
    }

    // Adds to the end of the linked list
    public void add(Student p) {
        ListNode tmp = head;
        if (tmp == null) {
            head = new ListNode(p);
            return;
        }
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = new ListNode(p);
    }

    public static void main(String[] args) {
        School mySchool = new School();

        mySchool.add(new Student("Bob"));
        mySchool.add(new Student("Ahmed"));
        mySchool.add(new Student("Nora"));

        /*
         * The following loop should output:
         * Bob
         * Ahmed
         * Nora
         */
        for (Student s : mySchool) {
            System.out.println(s);
        }
    }
}

Right now, the for-each loop in the main method of School does not work. Java reports the following error: Can only iterate over an array or an instance of java.lang.Iterable

Modify the School class so that for-each loops work properly on it.

Note: You do not need to rewrite the entire School class. If you need to modify a line of code that already exists, just tell us what the new line is. If you need to add a new method or inner class, simply write the code for that method or inner class and add a comment explaining where it needs to go.

Hint: If you aren’t sure how to make for-each loops work, look at the title of this question for a hint.






Quiz 08