COMP3027

Algorithm Design

Assignment 3

s1 2025

This assignment is due on May 7 and should be submitted on Gradescope.

All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Integrity” policies.

As a first step go to the last page and read the section:  “Advice on how to do the assignment.”

Problem 1. (100 points)

It is the year 3241 LY. You are the CEO of Theed Palace Space Vessel Engineering Corps (known as Theed Hangars for short), a starship manufacturing company based in the city of Theed on the planet Naboo. Among your esteemed range of products is the iconic N–1 starfighter, a single–seat patrol fighter used by the Royal Naboo Security Forces (RNSF).

One thing many denizens of Naboo might not understand, is that while Theed Hangars designs and carries out the finishing touches and quality assurance passes on all of its vessels, the bulk of the actual manufacturing work is outsourced to a vast supply chain of factories scattered across the Free Trade Zone. Theed Hangars has sought to capitalize upon this era of peace and prosperity in the galaxy by seeking to maximally leverage comparative advantage, establishing a delicate web of efficient manufacturing hubs across a multitude of star systems over the course of many decades.

To spare you the details, the three major elements of the N–1 starfighter con– struction pipeline are as follows:

1. The machining of the elegant N–1 spaceframe;

2. The attachment of the twin J-type engines, as well as the Monarc C-4 hyperdrive engine;

3. The fitout of the starfighter’s flight computer, sensor suite, armament, and life support systems.

Each of the major factories in the N–1 starfighter supply chain carries out one of these three steps in its entirety. It is important that each starfighter under construc– tion undergo each of these steps in the preceding order, since each step depends crucially on the completion of the prior.  (e.g.  the calibration of the starfighter’s flight computer and control systems requires that the engines already be in place.)

Unfortunately, not all is well in the Free Trade Zone – owing to the growing unrest with the excesses of the Trade Federation, many star systems have started moving towards imposing tariffs on inter–system trade.  For a supply chain as del– icate and fragmented as that of the typical Theed Hangars vessel, the impact of tariffs would be disastrous.

As CEO of Theed Hangars, you now find yourself scrambling from system to system, hoping to influence senators and other officials and obtain exemptions from their new and often harsh tariff regimes. Across many schmoozy meetings, a com– mon theme has emerged: quotas. If you can keep inter–system inputs into the fac– tories of a given system within a given quota, then the governing parties of the respective star systems will be able to sell a narrative to their constituents of bring– ing back local manufacturing to their system, and thus will exempt Theed Hangars from the brunt of the tariffs.

While all of this schmoozing in the halls of power is all good and well, you also have some pressing issues to address within the supply chain itself: most of the manufacturing hubs were established as joint ventures with their respective star systems’ local inhabitants or with foreign investment groups.  To keep a given factory open, it must remain profitable, which means it must produce a minimum output each year.

On the other hand, the RNSF has increased its order of record for N–1 starfighter procurement quite substantially this year, to a lofty total of X spaceframes. As you continue to hop between star systems to lobby for exemptions, you at the very least need a way to check: given the exemptions you have currently managed to win, is it possible to meet the N–1 order of record while respecting the agreed–to quotas and keeping all factories profitable?

Formally, you are given the following:

• A non–negative integer order of record for X N–1 starfighters.

• A set of star systems numbered from 1 to m.

• For each pair of star systems i, j, and each T  ∈ {frame, engines}, you are given a maximum allowable inter-system quota, a non–negative integer qijT  in– dicating the maximum amount of goods of type T which are allowed to be imported from system i to system j.

• A set of n factories. For each factory i, you are given...

– Its type, Ti  ∈ {frame, engines, fitout}.

– Its location, a star system Li  ∈ {1, . . . , m}.

– Its required output to remain profitable, a non–negative integer ai

– Its maximum manufacturing capacity, a non–negative integer bi.

Your task is to determine whether it is possible to assemble a supply chain schedule (i.e.  an assignment of spaceframes to frame, engines, and fitout factories), for X starfighters, such that each factory has capacity to complete work on the space– frames assigned to it, all inter–system quotas are respected, and so that all factories remain open.

a) Describe the algorithm.                                                                       [30 points]

b) Prove its correctness.                                                                             [50 points]

c) Establish its time complexity.                                                              [20 points]

Advice on how to do the assignment

• Assignments should be typed and submitted as 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.

• You may use paragraphs, lists or itemized points, pseudocode, or any combi– nation of the above to organize your algorithm description.  Do not include actual code in your submission. (Penalties will apply!)

• When designing an algorithm or data structure, it might help you (and us) if you give a brief (1–2 sentence) description of the overall idea, and after that develop and elaborate on details. If your algorithm is stated in pseudocode or the details of the algorithm are complex, then a brief description of the overall idea is required.  Remember that an assignment in this course is an exercise in effectively presenting and communicating technical ideas (i.e.  not just "solving the problem"), and will be graded accordingly.

• Refrain from explaining "why" your algorithm does what it does in the algo– rithm description itself.  The  "why" belongs in your proof.  Your algorithm description should be a lean, complete, and unambiguous statement of just "what" your algorithm is.

• If you use pseudocode in your algorithm description, avoid adhering to any particular pseudocode "standard". Each line should endeavour to be "prosaic" in describing the intended step, with mathematical notation interspersed to denote any objects or concepts which you feel cannot be conveyed clearly in prose. Treat the pseudocode in Kleinberg and Tardos as exemplary.

• In general, try to be prosaic rather than syntactic when describing your algo– rithm. Treat this as an advantage! You do not need to describe your algorithm to a compiler or interpreter, so you can focus on phrasing your description for ease of readability by a human reader.

• Be careful with giving multiple or alternative answers.  If you give multiple answers, then we will give you marks only for "your worst answer", as this indicates how well you understood the question.

• You can use the material presented in the lectures or textbooks without prov– ing it. You do not need to write more than necessary (see comment above).

• Unless otherwise stated, we always ask about worst–case analysis, worst–case running times, etc.

• If you use further resources (books, scientific papers, the internet,...)  to for– mulate your answers, then add references to your sources and explain it in your own words. Only citing a source doesn’t show your understanding and will thus get you very few (if any) marks.  Copying from any source without reference is considered plagiarism.