Mästarprov 1

Mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Vi tar mycket allvarligt på detta och följer KTH:s riktlinjer om att misstänkta fall av samarbete ska anmälas till rektor. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; inskannade handskrivna lösningar går bra) senast tisdag 18 oktober 2022 klockan 18:00. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du kontrollera att du är inloggad i Canvas. Klicka i så fall på inloggningsikonen i den gråa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske 21–28 oktober i Zoom eller på KTH för någon av lärarna. Boka tid för en 10 minuters (om du har löst en uppgift) eller 20 minuters (om du har löst 2-3 uppgifter)  muntlig redovisning senast 18 oktober klockan 19. Bokningslistorna läggs upp 17 oktober, se sist på denna sida. Vänta med att boka tid tills du har lämnat in uppgiften.

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera algoritmen muntligt och reda ut eventuella oklarheter.

Läs uppgifterna mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om något är oklart, företrädesvis på föreläsningarna 28 september-3 oktober eller via diskussioner i kursrummet. Formatet/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.

Mästarprovet är ett obligatoriskt moment i kursen. Det består av tre uppgifter som motsvarar betygskriterierna för E, C respektive A. För godkänt (betyg E) krävs helt rätt på en av uppgifterna. Helt rätt på två av uppgifterna ger betyg C och alla rätt ger betyg A. Ett mindre fel på en uppgift sänker betyget ett steg. Läs mer om betyg under rubriken Examination och slutförande i kurs-PM.

För att se exempel på hur utförliga lösningarna bör vara kan du titta på lösningar till tidigare mästarprov, både autentiska studentlösningar och mönsterlösningar. Där finns också tips om hur man skriver pseudokod, som du bör läsa innan du formulerar dina algoritmer. 

Uppgift 1 Elnät för notställsbelysning

Betygskriterium: utveckla algoritmer med datastrukturer för enkla problem givet en konstruktionsmetod.

I en konsertsal sitter musikerna utplacerade på bestämda platser, och varje notställ har en egen lampa med en lampsladd som precis bara räcker ner till golvet. För att alla notställslampor ska få ström behöver en elektriker bygga ett nät av grenuttag och sladdar där uttagens antal och sladdarnas längd anpassas av elektrikern efter behovet. Det behöver finnas ett eluttag under varje notställ. Det finns bara ett vägguttag i konsertsalen, och det sitter 150 centimeter ifrån närmaste notställ (som råkar vara tubaspelarens). Problemet är att designa ett nät av sladdar med grenuttag som använder så lite sladd (elkabel) som möjligt och inga oanvända eluttag.

Indata är en symmetrisk $n \times n$-matris som på plats $(i,j)$ anger hur lång sladd som skulle krävas för att dra el från notställ $i$ direkt till notställ $j$ (utan att passera något annat notställ, sladdlängden kan vara större än avståndet fågelvägen mellan notställen, eftersom det ofta inte är möjligt att dra sladden rakt mellan notställen). Tubaspelarens notställ är nummer $n$. Sladdlängden anges med ett positivt heltal som anger antalet centimeter sladd. Grenuttagen får bara placeras under notställen.

Utdata är en lista med material (alltså skarvsladdar med grenuttag) som behövs för att bygga det optimala nätet som kan förse alla notställ med el.
Varje element i listan beskriver en skarvsladd med grenuttag genom fyra tal: längden på sladden, antal eluttag i grenuttaget, numret på notstället där sladden ska kopplas in och numret på notstället där grenuttaget ska finnas. Vägguttaget anges med nummer 0. Ordningen mellan elementen i listan spelar ingen roll.

Exempel: 

Representera indata som en graf och använd en grafalgoritm för att konstruera en effektiv algoritm som löser problemet. Beskriv algoritmen med pseudokod, och beräkna algoritmens tidskomplexitet (ange den med ett ordouttryck). Det är tillåtet att använda och hänvisa till en algoritm från kurslitteraturen i din lösning, om du gör tydligt varifrån algoritmen är hämtad och hur den anropas i din algoritm.

Något korrekthetsbevis för din pseudokod behövs inte i denna uppgift, men du ska redogöra för vad som skulle behöva visas i ett korrekthetsbevis.

Uppgift 2 Viktiga möten

Betygskriterium: utveckla algoritmer med datastrukturer för icketriviala problem.

Företaget Effektiv Diskurs AB har bara ett mötesrum och dessutom en policy som kräver att man måste ange en prioritet för varje planerat möte. Din uppgift är att designa en algoritm som schemalägger så många viktiga möten som möjligt.

Indata till algoritmen är en lista av möten, där varje möte har ett unikt löpnummer, en beskrivning, en starttid, en sluttid och en prioritet. Listan i indata är sorterad efter stigande sluttid. Inga schemalagda möten får krocka och du ska maximera summan av prioriteterna för alla schemalagda möten. Ett möte som börjar på exakt samma tid som ett annat möte slutar anses inte krocka.

Exempel:

Här går det att schemalägga möte 1 och 3 eftersom de inte krockar och då blir den totala prioriteten 5+2=7. Men det är bättre att bara schemalägga möte 2, trots att det krockar med alla andra möten, eftersom det har en högre prioritet.

Du kan anta att alla löpnummer, tider och prioriteter är positiva heltal.

Deluppgifter

2a. Definiera en lämplig rekursionsekvation med vars hjälp du kan uttrycka den optimala totala prioriteten. 

2b. Tidskomplexiteten för en naiv rekursiv algoritm som beräknar den optimala totala prioriteten enligt rekursionsekvationen skulle bli exponentiell. Konstruera istället en effektiv algoritm för problemet (som är polynomisk i indatas storlek). Använd pseudokod för att beskriva algoritmen. Analysera tidskomplexiteten. Motivera också att algoritmen är korrekt.

2c. Anpassa algoritmen i 2b så att den inte bara beräknar den optimala totala prioriteten, utan också anger vilka möten som ska schemaläggas. Det finns inget krav på i vilken ordning mötena ska skrivas ut. Även denna algoritm ska beskrivas med pseudokod. Utöver tydlig och väldokumenterad pseudokod behöver du däremot inte motivera korrekthet och du behöver inte heller analysera tidskomplexiteten.

Uppgift 3 Optimal analys av ringar i vas

Betygskriterium: utveckla algoritmer med datastrukturer för svårare problem med den metod som passar bäst.

En vanlig lek är att ställa en vas på golvet, ställa sig en bit ifrån vasen och försöka kasta ner ringar i vasen. Uppgift 3 handlar om att analysera var ringarna landar i vasen, givet vasens inre dimensioner och ringarnas radier.

När en ring kastas ner i vasen kommer den att fastna på det översta stället i vasen där den inre diametern i vasen är mindre än ringens yttre diameter. Innan nästa ring kastas plockas den förra ringen upp, så det kan aldrig bli så att ringar fastnar på varandra i vasen.

Vasen är drejad och därför rak och rotationssymmetrisk runt den lodräta centrumaxeln. Bilden nedan visar ett exempel på ett hur ett tvärsnitt av vasen kan se ut. Sidorna består av linjesegment och möts längst ner i origo.

Indata: $(x_1,y_1),\ldots,(x_m,y_m), c_1,\ldots,c_n$ där alla tal är positiva rationella tal, $m\le n$ och $y_1<y_2<\cdots<y_m$

$(x_i,y_i)$ anger koordinater för vasens vägg från vasens botten och uppåt och $c_i$ anger radie på ring $i$.

Utdata: $h_1, \ldots, h_n$ där $h_1\le h_2\le \cdots\le h_n$

som anger på vilka höjder (dvs y-koordinater) som ringarna landat på. Notera att ordningen i utdata inte är samma som ringarnas ordning i indata utan efter stigande höjd.

Algoritmen ska vara så effektiv som möjligt, med tidskomplexiteten uttryckt med en ordoklass i n (med enhetskostnad).

Du ska visa att din algoritm är optimal (med avseende på ordoklass). Du ska också tydligt tala om vad som krävs (allmänt sett) för att bevisa korrektheten för den typ av algoritm som du skrivit och sedan bevisa korrektheten för din algoritm. Formulera invarianter för slingor och ingångs- och utgångsvillkor för eventuella hjälpfunktioner. Det är tillåtet att använda och hänvisa till en algoritm från kurslitteraturen i din lösning, om du gör tydligt varifrån algoritmen är hämtad och hur den anropas i din algoritm. Du behöver inte visa korrektheten för hjälpalgoritmer från kurslitteraturen.

Detaljerade bedömningskriterier

English version of the Swedish text of Mastery test 1

(Note: this is an English translation of the Swedish text. In case of any discrepancies between the two versions, the Swedish version is the authoritative one.)

The mastery test must be solved individually and presented both in writing and orally. No collaboration is allowed, see further the code of honour. In other words you must not discuss solutions with anyone until all oral presentations have been conducted. This is something we take seriously. According to KTH regulations, suspected forbidden collaboration must be reported to the rector. The submissions are checked for plagiarism.

Written solutions must be handed in in Canvas (as PDF; scanned handwritten solutions are fine) by Tuesday October 18, 2022, at 18:00 (Stockholm time). It is important that you submit on time! If you do not see a submission button on this page, check that you are logged in to Canvas by clicking the login icon in the grey menu to the left.

Write your name and KTH address at the top of the front page of your solution. Read through your solutions before the oral presentation, which will be over Zoom or at KTH between October 21 and 28 with one of the assistants or teachers of the course. Book a time for a 10 minute oral presentation (if you have solved one problem) or 20 minute oral presentation (if you have solved 2-3 problems) no later than October 18, at 19:00 (Stockholm time). The booking slots are published on October 17 at the bottom of this page. Do not book a slot until you have submitted your written solutions.

It is important that you prepare for the oral presentation. In order for you to pass you should be able to clearly explain and motivate the algorithm orally and sort out any unclear parts. Format/data structure for input and output can be choosen freely unless otherwise specified in the problem.

Read the problems very carefully so that you do not accidentally base your solutions on a misconception. If something is unclear, ask a teacher of the course, preferrably at the lectures September 28-October 3 (in Swedish) or using Canvas discussions.

The mastery test is a mandatory part of the course. It consists of three problems corresponding to the grading criteria for E, C and A respectively. For a passing grade (E), you need to solve one problem completely and correctly. Solving two problems completely and correctly gives grade C, and solving all problems gives grade A. A smaller error on one problem lowers the grade one step. Read more about grades in the course memo (in Swedish).

To see examples of how extensive the solutions should be you can look at solutions for earlier mastery tests, both authentic student solutions and model solutions. At that page there is also advice on how to write pseudocode, which you should read before you start formulating your algorithms. 

Problem 1 An electrical grid for music stand lighting

Grading criterion: develop algorithms with data structures for simple problems given a construction method.

In a concert hall, the musicians sit in designated places, and each music stand has its own lamp with a lamp cord that just barely reaches the floor. In order for all music stand lamps to be powered, an electrician needs to build a network of branch sockets and cords where the number of sockets and the length of the cords are adjusted by the electrician according to need. There needs to be an electrical outlet under each music stand. There is only one wall outlet in the concert hall, and it can be found 150 centimeters from the nearest music stand (which happens to be the tuba player's). The problem is to design a network of cords with power outlets that uses as little cord (power cable) as possible and no unused power outlets.

Input is a symmetric $n \times n$-matrix, where element $(i,j)$ defines the length of the cord that would be needed to connect an outlet at the music stand $i$ to the music stand $j$ (without passing any other music stand, the length of the cord may be greater than the shortest distance between the end points, because it is often not possible to run the cord straight between the end points). The tuba player's music stand has number $n$. The cord length is specified with a positive integer indicating the number of centimeters of cord. The branch sockets may only be placed under the music stands.

The output is a list of materials (i.e. cords with branch sockets) needed to build the optimal network that can supply all music stands with electricity.
Each element in the list describes a cord with a branch outlet using four numbers: the length of the cord, number of electrical sockets in the branch outlet, the number of the music stand where the cord is to be connected and the number of the music stand where the branch outlet is to be located. The wall socket is indicated with the number 0. The order between the elements in the list does not matter.

Example: 

Represent the input data as a graph and use a graph algorithm to construct an efficient algorithm that solves the problem. Describe the algorithm in pseudocode, and calculate the algorithm's time complexity (express it using a big O expression). It is allowed to use and refer to an algorithm from the course literature in your solution, if you make it clear where the algorithm is taken from and how it is called in your algorithm.

Proof of correctness for your pseudocode is not needed in this task, but you must explain what would need to be shown in a proof of correctness.

Problem 2 Important meetings

Grading criterion: develop algorithms with data structures for non-trivial problems.

The company Effektiv Diskurs AB has only one meeting room and, in addition, a policy that requires you to specify a priority for each scheduled meeting. Your task is to design an algorithm that schedules as many important meetings as possible.

The input to the algorithm is a list of meetings, where each meeting has a unique sequence number, a description, a start time, an end time, and a priority. The list in the input is sorted by ascending end time. No scheduled meetings may conflict, and you shall maximize the sum of the priorities of all scheduled meetings. A meeting that starts at exactly the same time as another meeting ends is not considered a clash.

Example:

Here it is possible to schedule meeting 1 and 3 because they do not clash, and then the total priority becomes 5+2=7. But it would be better to only schedule meeting 2, even though it conflicts with all other meetings, because it has a higher priority.

You can assume that all sequence numbers, times and priorities are positive integers.

Tasks

2a. Define a suitable recursion with the help of which you can express the optimal total priority.

2b. The time complexity of a naive recursive algorithm that calculates the optimal total priority according to the recursion would become exponential. Instead, construct an efficient algorithm for the problem (i.e. polynomial in the size of the input). Use pseudocode to describe the algorithm. Analyze the time complexity. Also justify that the algorithm is correct.

2c. Adapt the algorithm in 2b so that it not only calculates the optimal total priority, but also specifies which meetings to schedule. There is no requirement in which order the meetings should be printed. This algorithm must also be described with pseudocode. In addition to clear and well-documented pseudocode, however, you do not need to justify correctness, nor do you need to analyze the time complexity.

Problem 3 Optimal analysis of rings in a vase

Grading criterion: develop algorithms with data structures for more difficult problems using the most suiting approach.

A common game is to place a vase on the floor, stand some distance from the vase and try to throw rings into the vase. Problem 3 is about analyzing at which heights the rings land in the vase, given the inner dimensions of the vase and the radii of the rings.

When a ring is thrown into the vase, it will stick to the uppermost spot in the vase where the inside diameter of the vase is smaller than the outside diameter of the ring. Before the next ring is thrown, the previous ring is picked up, so it can never happen that rings get stuck to each other in the vase.

The vase is straight and rotationally symmetrical around the vertical central axis. The picture below shows an example of how a cross-section of the vase might look. The sides consist of line segments and meet at the bottom at the origin.

Input: $(x_1,y_1),\ldots,(x_m,y_m), c_1,\ldots,c_n$ where all numbers are positive rational numbers, $m\le n$ and $y_1<y_2<\cdots<y_m$

$(x_i,y_i)$ indicate the coordinates for the wall of the vase from the bottom of the vase and upwards, and $c_i$ indicates the radius of ring $i$.

Output: $h_1, \ldots, h_n$ where $h_1\le h_2\le \cdots\le h_n$

which will indicate at which heights (i.e. y coordinates) the rings landed. Note that the order in the output is not the same as the order of the rings in the input - instead they should be ordered by ascending height.

The algorithm should be as efficient as possible, with the time complexity expressed by an big O class in n (using unit cost).

You must show that your algorithm is optimal (with respect to big O class). You should also clearly state what is required (generally speaking) to prove the correctness of the type of algorithm you wrote and then prove the correctness of your algorithm. Formulate invariants for loops and pre and post conditions for any helper functions. It is allowed to use and refer to an algorithm from the course literature in your solution, if you make it clear where the algorithm is taken from and how it is called in your algorithm. You do not need to demonstrate the correctness of auxiliary algorithms from the course literature.

Detailed grading criteria

Mastery test 1 is graded according to the grading criteria for the intended learing outcomes developing algorithms with data structures as well as analyzing algorithms for efficiency and correctness. In addition, the learning outcome of comparing alternative algorithms and data structures with respect to efficiency and reliability will naturally be exercised in the algorithm construction.

To make it extra clear how the three problems are graded and in order for the assistants taking the presentations keeping the requirements at the same level, there are detailed grading criteria, which the assistants assess both in writing and orally using a grading sheet.

The following table shows the requirements for the different problems.

Example solutions

Example solutions for Mastery Test 1 will be published in the Swedish version of this page when all oral presentations have been conducted (28 October). Until then, it is not allowed to discuss the problems with anyone else.