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. Du får inte använda generativ AI för att lösa mästarprovsuppgifterna. Däremot får du gärna använda generativ AI för att typsätta med LaTeX. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; inskannade handskrivna lösningar går bra) senast tisdag 17 oktober 2023 klockan 19: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 23–27 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 17 oktober klockan 20. Bokningslistorna läggs upp 16 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 27 september-2 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 Billig numrering av hörn i en graf

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

Indata till problemet är en graf $G$ med hörnmängd $V$ och kantmängd $E$. ($G$ har minst ett hörn.)

Problemet är att numrera hörnen med talen $1,2,3,\ldots,\vert V\vert$.

Denna numrering ska beskrivas av en bijektiv funktion $f:V\longrightarrow\lbrace1,2,3,\ldots,\vert V\vert\rbrace$, som alltså utgör utdata.

Numreringen ska vara sådan att summan av alla $\vert f\left(u\right)-f\left(v\right)\vert$, där $\left(u,v\right)\in E$, blir så liten som möjligt.

Uppgift 2 Pyramider i pyramider

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

En rät pyramid är en geometrisk kropp som består av fyra likbenta trianglar som sidor på en kvadratisk bottenyta. Pyramidens storlek bestäms av två mått, bottenytans sida $s$ och pyramidens höjd $h$, se figuren.
                                                                         

Du känner nog till att formeln för pyramidens volym är $\frac{s^2h}{3}$. I denna uppgift tänker vi oss att varje pyramid bara består av ett tunt skal som utgörs av pyramidens fyra sidor. Pyramiden är öppen undertill och har inget innehåll. Detta gör att det går att sätta två pyramider (dvs pyramidskal) över varandra om det ena skalet är strikt större (både högre och bredare) än det andra. Den mindre pyramiden täcks då helt av den större. 

Problemet är att givet $n$ stycken pyramider avgöra hur många av dessa som maximalt kan placeras över varandra på ovanstående sätt så att varje pyramid täcks helt av närmast större pyramid. Pyramiderna ska staplas i en rak kedja ovanpå varandra.

Indata till detta problem är $n$ stycken pyramider $p_1,p_2,\ldots,p_n$ som var och en är beskrivna av ett par av två heltal $(p_i.s,p_i.h)$ där $p_i.s$ är sidans längd och $p_i.h$ är pyramidens höjd. $n\ne 0$.

Utdata är maximala antalet pyramider som kan placeras över varandra.

Konstruera en effektiv algoritm för problemet. Använd pseudokod för att beskriva algoritmen. Analysera tidskomplexiteten (med enhetskostnad) som högst får vara kubisk. Motivera också att algoritmen är korrekt.

Det är tillåtet att använda och hänvisa till en algoritm från kurslitteraturen (kursböckerna) 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 en hjälpalgoritm från kurslitteraturen.

Uppgift 3 Optimal minröjning

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

Ett hus med rektangulär bottenyta ska byggas i ett minerat fält. Innan man kan bygga huset måste alla minor i bottenytan röjas, samt också en rak väg fram till huset. Som tur är vet man läget för alla minor i minfältet. Uppgiften går ut på att konstruera en algoritm som så effektivt som möjligt hittar den optimala platsen för huset så att minimalt antal minor måste röjas för att bygga huset och vägen fram till huset.

Indata är en boolesk matris $F$ som beskriver var minorna finns i minfältet, samt två heltal $f$ och $g$. $F\left\lbrack i,j\right\rbrack$ är sant om det finns en mina i position $\left(i,j\right)$. $f$ anger bredden på framsidan på huset (räknat i antal kolumner i matrisen) och $g$ anger bredden på gavlarna (räknat i antal rader i matrisen), se exemplet. Huset ska byggas så att framsidan vetter nedåt i matrisen, dvs mot högre radindex. Vägen till huset ska gå från nederkanten av minfältet rakt upp till antingen vänster eller höger hörn på husets framsida. Vägen är lika bred som en kolumn i matrisen.

Indata: Boolesk matris $F\lbrack1..n,1..n]$ (där $n>1$) och heltal $f$ och $g$ som uppfyller olikheterna $2\le f\le n$ och $2\le g\le n$. 

Utdata: $\left(x,y\right)$ som är radnummer och kolumnnummer i matrisen för husets nedre vänstra hörn då huset, vars rektangulära basyta täcker $f$ kolumner och $g$ rader, placerats på det optimala sättet i minfältet, dvs så att antalet minor under husets basyta plus antalet minor under vägen fram till huset minimeras. Om det finns flera minimala lösningar ska en av dessa returneras.

Om huset gränsar till minfältets nedre kant (dvs om $x=n$) så behöver förstås ingen väg byggas fram till huset.

Nedanstående exempel visar en optimal placering av huset då indata är $n=8$, $f=4$, $g=3$ och $F$ har sant i dom positioner som markeras med M i exemplet. I optimala placeringen, som har $(x,y)=(4,4)$, går vägen fram till vänstra främre hörnet på huset och antalet minor som behöver röjas är 3.

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

Du ska visa att din algoritm har optimal tidskomplexitet (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.

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 president. You may not use generative AI to solve the mastery test preoblems. However, you are welcome to use generative AI for typesetting with LaTeX. The submissions are checked for plagiarism.

Written solutions must be handed in in Canvas (as PDF; scanned handwritten solutions are fine) by Tuesday October 17, 2023, at 19: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 23 and 27 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 17, at 20:00 (Stockholm time). The booking slots are published on October 16 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 27-October 2 (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 Cheap numbering of vertices in a graph

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

The input to the problem is a graph $G$ with vertex set $V$ and edge set $E$. ($G$ has at least one vertex.)
The problem is to number the vertices with the numbers $1,2,3,\ldots,\vert V\vert$.
This numbering is described by a bijective function $f:V\longrightarrow\lbrace1,2,3,\ldots,\vert V\vert\rbrace$, which is the output of the algorithm.
The numbering should be such that the sum of $\vert f\left(u\right)-f\left(v\right)\vert$ over all edges $\left(u,v\right)\in E$, is as small as possible.
This problem can be solved efficiently for some types of graphs, but seems difficult for a general graph.  You should therefore construct an algorithm using exhaustive search.
Describe your algorithm with pseudo code and calculcate its time complexity (make a tight analysis that you specify with big O).
A proof of correctness for your pseudo code is not needed in this problem, but you must explain what would need to be shown in a proof of correctness.
It is up to you to decide exactly how the input and output should be represented.

Problem 2 Pyramids in Pyramids

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

A square pyramid is a geometric shape consisting of four isosceles triangles as sides on a square bottom surface.  The size of the pyramid is determined by two measures, the side length $s$ of the bottom surface, and the height $h$ of the pyramid (see figure).
                                                                         

You are probably aware that the formula for the pyramids volume is $\frac{s^2h}{3}$. In this problem, we view a pyramid as consisting solely of a thin shell formed by its four sides. The pyramid is open at the bottom and has no content in its interior. This means that two pyramids (i.e., pyramid shells) can be placed on top of each other if one shell is larger (both taller and wider) than the other.  The smaller of the two pyramids is then completely covered by the larger one.

The problem is, given $n$ pyramids, to determine the largest number of pyramids that can be placed on top of each other in this way such that every pyramid (except the largest) is completely covered by the next larger pyramid. The pyramids must be stacked in a straight chain on top of each other.

The input to the problem consists of $n$ pyramids $p_1,p_2,\ldots,p_n$ each of which is descried by two integers $(p_i.s,p_i.h)$ where $p_i.s$ is the side length and $p_i.h$ is the height of the pyramid. $n\ne 0$.

The output is the maximum number of pyramids that can be placed on top of each other.

Construct an efficient algorithm for this problem.  Use pseudo code to describe the algorithm.  Analyze the time complexity (assuming unit cost) which should at most be cubic.  Also justify that the algorithm is correct.

It is allowed to use and refer to an algorithm from the course literature (textbooks) 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.

Problem 3 Optimal Mine Sweeping

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

A house with rectangular surface shape is being built in a minefield.  Before the house can be built, all mines under the house must be cleared, and a straight path to the house must also be cleared.  Fortunately, the locations of all mines in the minefield are known.  This problem is about constructing an algorithm which finds the optimal placement of the house in order to minimize the number of mines that have to be cleared, as efficiently as possible.

The input is a Boolean matrix $F$ describing the locations of the mines in the minefield, and two integers $f$ and $g$. $F\left\lbrack i,j\right\rbrack$ is true if there is a mine in position $\left(i,j\right)$. $f$ denotes the width of the front of the house (in number of columns of the matrix) and $g$ denotes the width of the side of the house (in number of rows of the matrix), see example below.  The house should be built so that the front is facing downwards in the matrix, i.e., towards higher row numbers. The road to the house must run from the bottom boundary of the mine field straight up to either the left or the right corner of the front of the house.  The width of the road is one matrix column.

Input: Boolean matrix $F\lbrack1..n,1..n]$ (where $n>1$) and integers $f$ and $g$ satisfying $2\le f\le n$ och $2\le g\le n$.

Output: $\left(x,y\right)$ giving the row number and column number in the matrix for the lower left corner of the optimal placement of the building.  The building covers a rectangular shape of $f$ columns and $g$ rows, and the objective is to minimize the total number of mines under this rectangular shape and the road leading to the house.  If there is more than one optimal solution, any one of them should be returned.

If the building borders the bottom boundary of the mine field (i.e., if $x=n$) then no road needs to be built to the house.

The example below shows an optimal placement of the house when the input is $n=8$, $f=4$, $g=3$ and $F$ is true in the position marked by M in the figure. In the optimal placement, which has $(x,y)=(4,4)$, the road runs to the lower left front corner of the house, and the total number of mines that need to be cleared is 3.

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. 

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 Download Example solutions for Mastery Test 1 will be published in the Swedish version of this page when all oral presentations have been conducted (27 October). Until then, it is not allowed to discuss the problems with anyone else.