Programmeringsuppgifterna görs helst i par. Om du inte har möjlighet till detta så måste du kontakta kursledaren innan.

Instruktioner: Lämna in era programmeringsuppgifter i Lisam (inklusive alla filer som man behöver för att köra koden) i en enda zip-fil. Använd inget annat komprimeringsformat. Skriv era liu-id i en kodkommentar längst upp.

Format på filnamn: TDP015-2025 uppgiftskod ditt LiU-ID din partners LiU-ID. Detta gäller zip-filen och relevanta python-filer (ni behöver inte döpa om givna bibliotek eller dylikt, men det ska inte vara några p2-skeleton.py eller P2.py i inlämningarna). Detta underlättar för assistenten.

Exempel: TDP015-2025 P1 marjo123 erika456

Återkoppling: Varje uppgift har två inlämningsdatum (deadline och slutdatum). Se Lisam. Om ni lämnar in vid det första datumet (deadline) får ni mer utförligt skriftlig återkoppling på uppgiften och möjlighet till komplettering innan dess slutgiltiga bedömning i samband med slutdatumet.

I denna uppgift ska ni experimentera med rekursion. I det första problemet ska ni implementera en generator för nästlade par, som svarar mot korrekt balanserade klammeruttryck. I det andra problemet ska ni räkna antalet sådana par utan att generera dem. I det tredje problemet ska ni undersöka en teknik för att snabba upp rekursiva beräkningar genom memoisation, som är grunden till en kraftfull beräkningsteknik kallad dynamisk programmering.

• Skelettkod
• Wikipedia-artiklar Memoization och Dynamic Programming

I denna uppgift ska ni skriva olika funktioner för logiska satser, såsom en funktion som testar om en sats är satisfierbar, och en som testar om två satser är logiskt ekvivalenta. För att kunna skriva dessa funktioner behöver ni först implementera klasser för logiska satser. Till er hjälp med detta får ni fragmentarisk skelettkod. Börja med att läsa kommentarerna i denna skelettkod för att förstå hur klasserna är tänkta att användas. Lägg sedan till kod på de ställen som är markerade med ett todo. Skriv även några relevanta testfall.

• Skelettkod
• Dokumentation till Python-modulen itertools, som med fördel kan användas för en av funktionerna

I denna uppgift ska ni implementera en enkel version av RSA-algoritmen för kryptering och dekryptering. I uppgiftens centrala delar implementerar ni en generaliserad form av Euklides’ algoritm för att hitta den största gemensamma delaren till två tal och en funktion som genererar ett nyckelpar.

• Skelettkod
• Wikipedia-artiklar RSA (cryptosystem) och Extended Euclidean algorithm

I denna uppgift ska ni implementera en probabilistisk klassificerare som läser in en bild av en handskriven siffra och förutsäger vilken siffra det rör sig om. Klassificeraren bygger på Bayes’s regel. Ni tränar den genom att skatta sannolikheter utifrån data i MNIST-databasen, en stor datamängd med handskrivna siffror som manuellt taggats med korrekt siffra.

• Skelettkod och datafiler, bibliotek
• Wikipedia-artikel Naive Bayes

I forskningsprojektet Semantic Parsing for Text Analytics utvecklas algoritmer som parsar naturligt språk till semantiska representationer i form av riktade grafer. En önskvärd egenskap för dessa grafer är att de ska vara acykliska. Er uppgift är att implementera en funktion som testar om en riktad graf innehåller en cykel (t.ex. genom att försöka sortera grafen topologiskt), och att använda denna funktion för att hitta cykliska grafer i en av de datamängder som används i forskningsprojektet.

• Skelettkod och datafil
• Wikipedia-artikel Topological sorting

Er uppgift är att implementera Newtons metod för att approximera nollställen till en funktion för att sedan tillämpa denna metod till problemet att beräkna roten ur ett tal. Ni kommer också undersöka hur valet av startvärdet påverkar beteendet av Newtons metod när man har en funktion med flera olika nollställen.

• Skelettkod
• Wikipedia-artikel Newton’s method