Övning 3


​Mål:

  • Binära sökträd
  • Bli säker på att praktiskt genomföra algoritmer för binära sökträd.
  • Använda enkla krypteringsmetoder, och förklara principerna för asymmetrisk kryptering (inför nästa KS)

Ta en titt på Labb 3

Binära sökträd

Mål: Bli säker på att praktiskt genomföra algoritmer för binära sökträd.


Trädbyggen

  • Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6 3 7 5 i denna ordning?
  • Och hur ser det ut om man sätter in dom i omvänd ordning, alltså 5 7 3 6 1 4 2?
  • Är båda träden binära sökträd?
  • Är de balanserade?

Postorderträd

  • Skriv ut något av träden i inordning och bygg upp ett nytt träd från denna talföljd.
  • Skriv sedan ut dom i preordning och bygg upp nya träd från dessa talföljder.
  • Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder.

lösning

Rekursiv trädsumma

Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar.

Rekursiv trädhöjd

Ge en rekursiv tanke för höjden av ett träd. Höjden är den maximala nivån som nån av trädets noder befinner sig på. Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1.

lösning


Kryptering


 

Enkel kryptering på fyra sätt

a) Kryptera SIMSALABIM med rot13

b) Visa med ett exempel hur man går till väga för att dechiffrera transpositionschiffer. T ex ADGJBEHKCFIL lösning

c) Kryptera ett eget meddelande med bokchiffer. Använd boken Minnet och dess pedagogiska problem Links to an external site. av Axel Herrlin (1932).

d) Meddelandet 0b1100010 är krypterat med one-time pad med nyckeln 0b0110011. Dekryptera!

lösning, annan indata i b) och c)


Asymmetrisk kryptering

Lura NSA med RSA Aliententan 2015-03-20, uppgift 1 (betyg E)

Rymdvarelser har uppmärksammat jordens existens och vill ta kontakt med en tildastudent på KTH. Rymdvarelserna är oroliga för att NSA ska avlyssna eller på annat sätt blanda sig i kommunikationen, men har läst att RSA-konceptet med publika och privata nycklar kan lösa kommunikationsproblematiken. Förklara vilka problem som kan lösas med hjälp av asymmetrisk kryptering med publika och privata nycklar, och berätta för rymdvarelserna hur det ska gå till.

lösning