Week-13 : Correction in priority queue

Today, we discussed about implementing priority queue using ArrayList and LinkedList. While using ArrayList, we don't have to shift elements after removeMin(). I have explained a better solution below.

When we are using

Unordered ArrayList:

• add(element e) => O(1)
• peekMin() => O(n)
• removeMin() => O(n)
• Here, removeMin() requires finding the min value => O(n), removing it and then, shifting the elements will take O(n).
• A better solution: Instead of shifting, just replace the gap with the last element of the ArrayList. This can be done in constant time [O(1)].

Unordered ArrayList with index value of min:

• add(element e) => O(1)
• peekMin() => O(1)
• removeMin() => O(n)
• Again instead of shifting, replace the gap with the last element. But, we have to keep track of the index of min. To update the min index, we must traverse the list. This will take O(n) time.

Week - 13

Sets & MultiMap

1. Link to presentation slides
2. Set interface code
3. ListSet code

Week-12 - Midterm II: Solutions

Problem 1:

In order to get a worst case running time of O(n^2), we should draw a tree in such a way that, depth() function is called at each level. Therefore, a tree with many leaves will run for the worst case.

Problem 2

ArrayList : O(n) for remove => O(n^2) run-time.
LinkedList: O(1) for remove => O(n) run-time

Reference: ArrayList Vs LinkedList

Problem 3

Code

Problem 4

Inorder and Breadth first traversal.

Problem 5

Code

Week-11

Class cancelled.

Week-10

We discussed 2 topics:

1. HashMap example: Roman Calculator example
2. Implementing stack using 2 queues. Link for more details
3. Quiz