Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP3121/9101 23T2 — Assignment 2

Due Monday 23rd of October at 6pm Sydney time  (week 7)

In this assignment we review some basic algorithms and data structures, and we apply the greedy method. There are three problems each worth 20 marks, for a total of 60 marks.  Partial credit will be awarded for progress towards a solution.  We’ll award one mark for a response of “one sympathy mark please” for a whole question, but not for parts of a question.

Any requests for clarification of the assignment questions should be submitted using the Ed forum.

We will maintain a FAQ thread for this assignment.                                                                        .

For each question requiring you to design an algorithm, you must justify the correctness of your algorithm.  If a time bound is specified in the question, you also must  argue that your algorithm meets this time bound.  The required time bound always applies to the worst case  unless otherwise specified.

You must submit your response to each question as a separate PDF document on Moodle.  You can submit as many times as you like. Only the last submission will be marked.

Your solutions must be typed, not handwritten. We recommend that you use LaTeX, since: .  as a UNSW student, you have a free Professional account on Overleaf, and

. we will release a LaTeX template for each assignment question.

Other typesetting systems that support mathematical notation (such as Microsoft Word) are also acceptable.

Your assignment submissions must be your own work.

. You may make reference to published course material (e.g. lecture slides, tutorial solutions) without providing a formal citation. The same applies to material from COMP2521/9024.

. You may make reference to either of the recommended textbooks with a citation in any format.

. You may reproduce general material from external sources in your own words, along with a citation in any format.  ‘General’ here excludes material directly concerning the assignment question. For example, you can use material which gives more detail on certain properties of a data structure, but you cannot use material which directly answers the particular question asked in the assignment.

. You may discuss the assignment problems privately with other students.  If you do so, you must acknowledge the other students by name and zID in a citation.

.  However, you must write your submissions entirely by yourself.

– Do not share your written work with anyone except COMP3121/9101 staff, and do not store it in a publicly accessible repository.

– The only exception here is UNSW Smarthinking, which is the university’sofficial writing support service.

Please review the UNSW policy on plagiarism. Academic misconduct carries severe penalties.

Please read the Frequently Asked Questionsdocument, which contains extensive information about these assignments, including:

.  how to get help with assignment problems, and what level of help course staff can give you

. extensions, Special Consideration and late submissions

.  an overview of our marking procedures and marking guidelines

.  how to appeal your mark, should you wish to do so.

Question 2 Ruins

Your boss has decided to take everyone on a mandatory vacation to a ruin. To be on the safe side of the law, they haven’t said anything explicitly, but have very strongly  suggested everyone should look for treasure to hand in at the end of the trip.

All k employees have entered the ruins and located a piece of treasure each.  However, an earthquake has struck, and the ruins have started to collapse.  There are conveniently exactly  k rooms with a stairwell to escape from, but every time someone travels to an adjacent room, the doorway collapses, so no door can be used twice, and are too small to let more than one person through them at a time.  After leaving the stairwell, it collapses, so only one employee can escape using each stairwell.

You are given a graph G with n vertices and m edges, where each vertex represents a room, and each edge represents a doorway connecting adjacent rooms.  You may assume that  n < m. You are also given two arrays, E[1..k] and X[1..k], being a list of rooms with an employee and a list of rooms with a stairwell respectively.

2.1    [10  marks] Your boss, ever greedy, has started freaking out about rescue costs, and wants to know exactly how many employees will be able to escape.  Thankfully, they had the foresight to give everyone in the ruin a communication device, so everyone can communicate as they escape to coordinate their paths.  Determine the maximum number of employees that can escape the ruins in O(k(m + k)) time.

2.2    [5 marks] In a stoke of “genius,” your boss has uncovered a magic scroll, which has activated teleporters in some of the rooms! If an employee enters a room with a teleporter, they can choose to teleport to any other room with a teleporter inside. However, your boss needs to throw a gold coin into a wishing well every time an employee travels through the teleporter, and only has C coins.

You are given another array, T[1..n] where T[i] is true if the room represented by vertex i contains an active teleporter, and false otherwise. Determine the maximum number of employees that can escape the ruins now that teleporters can be used, without teleporting more than C times in total, in O(k(m + k)) time.

2.3    [5 marks] Your boss has found a large supply of gold coins to use to power the teleporter, but wants to keep as many gold coins as they can for themselves.  Determine the maximum number of employees that can escape the ruins, while minimising the number of uses of the teleporter, in O(k(m + k)log k) time.

If there is a solution that allows more employees to escape, but requires more uses of the teleporter, it should be chosen instead.

Design an O(mlog n) algorithm which determines the smallest number of transmissions required to send Blake the message without Song intercepting any of the confidential material.

3.3    [6  marks] Before sending the message, Gerald remembered that Song is an expert cyber- criminal who can break the encryption and intercept the entire message if the same byte travels over more than one unencrypted link, even if it’s just a skull emoji!

Using the above example, Gerald could send the first 3 bytes along the path v1  → v4  → v7 , then the remaining bytes along the path v1  → v2  → v5  → v7 , as this path includes only one unencrypted link.  He can not use the path v1   → v3  → v6  → v7 , as this includes more than one unencrypted link.

Design an O(mlog n) algorithm which determines the smallest number of transmissions required to send Blake the message without Song intercepting any of the confidential material.

Figure 1: Gerald,  Blake  and  Song  are  commonly  used  characters to illustrate network users (image from  Wikipedia) .