Ask your favorite Generative AI tool to predict how Merge Sort, Quick Sort, and Heap Sort will behave under the following scenarios:

• Random arrays

• Already sorted arrays

• Reverse sorted arrays

• Arrays with many duplicate values

Focus on time complexity trends, not exact runtime.  

• Paste the LLM response

• Cite the tool and prompt used

• No student commentary yet

In this part of the project, the student must submit a PDF document answering the followin questions:

• Which predictions made by the LLM were correct?
• Which were misleading or oversimplified?
• Where did your own hypothesis differ from the LLM?

• What did you learn about:

  • Algorithm analysis?
  • Empirical evaluation?
  • The limitations of Generative AI (if any)?

The document must :

• Present results in tables and plots

• Compare:

  • Algorithms

    • Y axis - average time per list, X axis - scenario, and a line for each algorithm
    • Y axis - total time, X axis - scenario, and a line for each algorithm

  • Each plot must have a text refering the plot explaining the results.

Consider a dynamically-sized array to which we append items. It starts with capacity 1, and doubles its capacity whenever it becomes full. Suppose the cost of inserting an item is 𝑂(1), and the cost of doubling from 𝑚 to 2𝑚 is 𝑂(m) .

Let the potential function be:  \phi = 2*n - capacity , where n are the items in the array at that moment in time.

What is the Amortized Cost for the operations?

An operating system has a Priority Queue implemented that when there are resources available takes a task from the queue and executes it.  The priority queue is based on the priorities assigned to each task.  If you decide to build a heap for the below task list, what will be the correct heap from the list below?  

Assume the smallest number in the task priority means it has the higher priority.

A Binomial Heap maintains a pointer to the minimum element in the heap.

Consider a dynamically-sized array to which we append items. It starts with capacity 1, and doubles its capacity whenever it becomes full. Suppose the cost of inserting an item is 𝑂(1), and the cost of doubling from 𝑚 to 2𝑚 is 𝑂(m) .

Let the potential function be: ϕ=2∗n−capacityϕ=2∗n−capacity \phi = 2*n - capacity , where n are the items in the array at that moment in time.

What is the Amortized Cost for the operations?

Which imbalances were found when inserting these keys on an empty AVL tree?:  

Keys: 48, 22, 27, 23, 12, 42

Using the cycle detection algorithm discussed in the class videos, what will be the resulting non-cycle version for the below graph assuming we want to minimize the overall weights?

Optional: Attach exam procedures in case you may want to get partial points if you get an answer wrong.

A Binomial Heap contains 3 binomial trees of degrees 11, 7, and 2.  How many elements does the heap contain?