<aside> 📣

The Exam 1 Review Session is scheduled for March 16, 2025 6:00 PM (PDT) on

**Zoom** with Dr. Stevens and our very special, incredibly wise, and slightly legendary guest, Dr. Linstead!

This is a fantastic opportunity to ask any and all questions about the exam and clarify any topics you’re still unsure about before test day.

The session will be recorded, so if you can’t attend live, you’ll still have access to the review. If you won’t be able to join, we strongly encourage you to submit your questions in advance, so we can address them during the session and you can catch the answers in the recording later. Looking forward to helping you all feel confident and prepared—see you Sunday! 🥳

</aside>

<aside> 💯

PA 3 has now been assigned. It is due March 20, 2025. This deadline will NOT be moved!

Exam 1 is March 18, 2025 check out the following to study:

• Exam 1 At-Home Review Questions new!
• Exam 1 Topics
• Quizzes Spring 2025
• All In-Class Lecture Notes
• All Slideshows
• Complete ZyBooks problems that were not assigned/ re-do the ones you’ve already done. </aside>

Review Questions:

<aside> 💯

Answers to Review Questions: Exam 1 In-Class Review Questions Answers

</aside>

1. Imagine you have a sorted list of names, and you are using binary search to find a certain name. Answer the following questions and explain your thought process:

   1. If the list contains 64 names, what is the maximum number of steps it would take to find the name?
   2. What if the size of the list doubles (to 128 names)?

2. Suppose you have a contact list where each element of the list is a Contact object. Each contact object contains a name and a phone number. The contact list is sorted in alphabetical order by name and and all contacts have a unique name. What is the Big Oh runtime of your algorithm if you wanted to do the following operations. Explain:

   1. You have a person’s name, and you want to find their phone number.
   2. You have a person’s phone number, and you want to find their name.
   3. You want to read through the phone numbers of every person whose name starts with the letter E.

3. You have been asked to consult on a project for Pely, a popular restaurant review app. They are trying to expand their interface to allow customers to get added to a wait list of a restaurant from their app. They need your input on the data structure they should use to add and remove people from their list easily and efficiently. They want you to take into consideration that the wait lists can grow and shrink very fast.

   ⚠️  assume people cannot leave the list in the middle they can either get seated or get added to the list.

   a. What data structure would you recommend for this feature? Why?

   b. Would you suggest implementing this data structure using a linked list or an array? Why?

4. Popular music streaming apps “Bannana Music” and “Dotify” have a “play next” feature that allows users to choose the song they want to listen to. However, the feature works differently in each of these apps as explained below:

   Imagine the user picks songs to listen to next in this order:

   PlayNext → “As It Was by Harry Styles"

   PlayNext → “Flowers by Miley Cyrus”

   PlayNext → “Kill Bill by Sza”

   What data structure is used by each streaming app to keep track of the songs’ playing order? Explain.

   Bannana Music’s resulting playing order	Dotify’s resulting playing order
   1.     Kill Bill by Sza
   2.     Flowers by Miley Cyrus
   3.     As It Was by Harry Styles	1.     As It Was by Harry Styles
   2.     Flowers by Miley Cyrus
   3.     Kill Bill by Sza

5. Suppose that you have a max priority queue consisting of “Task” objects.

   • Each task object has an escalationLevel attribute that is an integer value assigned at creation. The higher the escalation level value, the faster the task should be resolved. The Task class defines the “<” operator for Task objects based on escalationLevel, i.e.:
     • TaskA < TaskB returns true if TaskA.escalationLevel < TaskB.escalationLevel
   • We can create a new task with the following code: new Task(name, priorityLevel)
   • If two tasks with the same escalationLevel get added, the one that was added first should have greater priority (should leave the queue first)
   • Assume that the queue is stored in least to greatest order of escalationLevel (low priority → high priority)

   Knowing this information, answer the following questions:

   1. Assuming the queue starts as empty, draw the queue that would result from the following adds:

      add (new Task (a, 1))
      add (new Task (b, 2))
      add (new Task (c, 3))
      add (new Task (d, 1))
      

   2. Given the priority queue that was created above, what Task would be returned by calling the peek( ) method?

   3. What would the queue look like if we ran each of the following method calls in the order shown? Draw the resulting queue.

      remove ()
      remove ()
      add (new Task(e, 1))
      add (new Task(g, 3))
      add (new Task(f, 2))
      remove ()
      remove ()
      

   4. Explain how you would implement a stack using a single queue. Assume you have access to the code for the doubly linked list-based queue we wrote in class. Make sure you explain how you would go about creating the following methods and draw pictures as needed:

   <aside> ⚠️ you shouldn’t change anything in the ListQueue.h file. You are trying to create a ListStackQ class with the “guts” of it being the ListQueue. Just like in the ListQueue class the DblList is the “guts”. So, you ONLY have access to the ListQueue interface (i.e. add(), remove(), peek(), isEmpty(), size(), …)

   </aside>

   • push ( )
   • pop ( )
   • peek ( )

   1. Implement the deleteList() method in the DblList class below. This method should traverse the list and remove all nodes, effectively clearing it.

      Method to write:

      template<typename T>
      void DblList<T>::deleteList(){
          // TO DO FOR REVIEW
      }
      

      • DblList.h completed code