compX123 Assignment 3 s2 2024

Release Date: 2024 – 09 – 22 00:00:00

Assignment Content:

This assignment is due on September 22 and should be submitted on Grade – scope. All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.

Problem 1: Analyze the response generated by an AI regarding a specific problem. The problem is to determine if there is an item in a vending machine whose price is equal to the sum of two coins, one from you and one from your friend, while ensuring that both you and your friend contribute at least one coin. The provided algorithm uses a hash map and binary search, and you need to analyze whether the algorithm solves the problem, runs within the required time, and whether the description of the algorithm, the correctness argument, and the running time analysis are correct.

Problem 2: Design a data structure to support the router testing process, including operations such as initialization, adding data, retrieving the current delay, and retrieving the maximum delay. The data structure should meet specific time and space requirements. You need to briefly argue the correctness of the data structure and operations, analyze the running time of the operations, and the space of the data structure.

Problem 3: Design an algorithm to predict the spread of bushfires. Given an undirected graph and an array of initially burning vertices, compute all the burning vertices. The algorithm should run in O(n + m) time. You need to describe the algorithm in plain English, argue its correctness, and analyze its time complexity.

Submission Requirements:

Assignments should be typed and submitted as a pdf (no pdf containing text as images, no handwriting).

Start by typing your student ID at the top of the first page of your submission. Do not type your

name.

Submit only your answers to the questions. Do not copy the questions.

When asked to give a plain English description, describe your algorithm as you would to a friend over the phone, making sure to completely and unambiguously describe your algorithm, including all the important (i.e., non-trivial) details.

Be careful with giving multiple or alternative answers. Only the “worst answer” will be graded.

Some questions are easy (with the help of the slides or book). You can use the material presented in the lecture or book without proving it.

When answering questions, always prove/explain/motivate your answers.

When giving an algorithm as an answer, it does not have to be in the form of (pseudo-)code. If you do give (pseudo-)code, you still need to explain your code and ideas in plain English. Unless otherwise stated, we always consider the worst-case analysis and worst-case running times.

We are interested in the most efficient algorithms and data structures, but slower solutions may receive partial marks.

If you use additional resources (books, scientific papers, the internet, etc.) to formulate your

answers, add references to your sources and explain it in your own words. Copying from any source without reference is considered plagiarism.# COMPX123 Assignment 3