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? 

You need to insert the following keys into a Red Black balanced tree: [7, 45, 12, 3, 94, 64, 43, 79].  After all the keys are inserted, which specific rotations were performed during the insertion process?  Remember, rotations are performed when double red violations are encountered.