CMPT225, Spring 2021
Final Exam
Name_________________________
SFU ID: |__|__|__|__|__|__|__|__|__|
Problem 1
Problem 2
Problem 3
Problem 4
TOTAL
Instructions:
1. You should write your solutions directly in this word file,
and submit it to Coursys. Submitting a pdf is also ok.
2. Submit your solutions to Coursys before April 20, 23:59.
No late submissions, no exceptions
3. Write your name and SFU ID on the top of this page.
4. This is an open book exam.
You may use textbooks, calculators, wiki, stack overflow, geeksforgeeks, etc.
If you do, specify the references in your solutions.
5. Discussions with other students are not allowed.
Posting questions online asking for solutions is not allowed.
6. The exam consists of four (4) problems. Each problem is worth 25 points.
7. Write your answers in the provided space.
8. You may use all classes in standard Java, and everything we have learned.
9. Explain all your answers.
10. Really, explain all your answers.
Good luck!
Problem 1 [25 points]
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:16:50 GMT -05:00
https://www.coursehero.com/file/161942571/CMPT225-finaldocx/
, A. (15 points) In this question you need to design a data structure that supports
PriorityQueue with deletions. Specifically, you need to write the class
PriorityQueueWithDeletions. As a motivation you may think of a priority queue for a
printer that allows adding a document, removing a document in some order (e.g.
shorter documents are printed first), or a user can cancel the job. Specifically the class
needs to support the following operations:
The running time of each operation must be O(log(size of the queue)).
public class PriorityQueueWithDeletions<T extends Comparable<T>> {
public PriorityQueueWithDeletions() - creates an empty priority
queue
public Ticket add(T item) - adds a new element to the queue.
Returns a ticket that can be used to remove your item from the
queue.
public T removeHighestPriority() - removes the element with the
highest priority from the queue and
returns it.
public removeByTicket(Ticket t) - removes an element by ticket,
and returns the removed
element.
public int size() - returns the number of elements in the queue
public boolean isEmpty() - checks if the queue is empty
}
The running time of each operation must be O(log(n)), where n is the size of the
priority queue.
Explain your answer in detail. Define the class Ticket and explain how you use it.
Make sure Ticket does not allow the user to modify the queue adversarially.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:16:50 GMT -05:00
https://www.coursehero.com/file/161942571/CMPT225-finaldocx/
Final Exam
Name_________________________
SFU ID: |__|__|__|__|__|__|__|__|__|
Problem 1
Problem 2
Problem 3
Problem 4
TOTAL
Instructions:
1. You should write your solutions directly in this word file,
and submit it to Coursys. Submitting a pdf is also ok.
2. Submit your solutions to Coursys before April 20, 23:59.
No late submissions, no exceptions
3. Write your name and SFU ID on the top of this page.
4. This is an open book exam.
You may use textbooks, calculators, wiki, stack overflow, geeksforgeeks, etc.
If you do, specify the references in your solutions.
5. Discussions with other students are not allowed.
Posting questions online asking for solutions is not allowed.
6. The exam consists of four (4) problems. Each problem is worth 25 points.
7. Write your answers in the provided space.
8. You may use all classes in standard Java, and everything we have learned.
9. Explain all your answers.
10. Really, explain all your answers.
Good luck!
Problem 1 [25 points]
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:16:50 GMT -05:00
https://www.coursehero.com/file/161942571/CMPT225-finaldocx/
, A. (15 points) In this question you need to design a data structure that supports
PriorityQueue with deletions. Specifically, you need to write the class
PriorityQueueWithDeletions. As a motivation you may think of a priority queue for a
printer that allows adding a document, removing a document in some order (e.g.
shorter documents are printed first), or a user can cancel the job. Specifically the class
needs to support the following operations:
The running time of each operation must be O(log(size of the queue)).
public class PriorityQueueWithDeletions<T extends Comparable<T>> {
public PriorityQueueWithDeletions() - creates an empty priority
queue
public Ticket add(T item) - adds a new element to the queue.
Returns a ticket that can be used to remove your item from the
queue.
public T removeHighestPriority() - removes the element with the
highest priority from the queue and
returns it.
public removeByTicket(Ticket t) - removes an element by ticket,
and returns the removed
element.
public int size() - returns the number of elements in the queue
public boolean isEmpty() - checks if the queue is empty
}
The running time of each operation must be O(log(n)), where n is the size of the
priority queue.
Explain your answer in detail. Define the class Ticket and explain how you use it.
Make sure Ticket does not allow the user to modify the queue adversarially.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:16:50 GMT -05:00
https://www.coursehero.com/file/161942571/CMPT225-finaldocx/
