Python Data Structures and Algorithms-kurs

Lektion 1 • Funktioner och omfattning

Definierar återanvändningsbara funktioner, standardargument och regler för variabelräckvidd. Funktioner är den primära enheten för algoritmimplementering i denna kurs.

Lektion 2 • Översikt över inbyggda samlingar

Översikt över listor, tupler, ordböcker och mängder samt deras tidskomplexitet. Ger den praktiska container-kunskap som behövs innan anpassade datastrukturer byggs.

Lektion 3 • Moduler, bibliotek och I/O

Introducerar import av moduler, användning av standardbiblioteket och läsning av indata för problem i tävlingsstil. Förbereder studenterna för strukturerade arbetsflöden för problemlösning.

Lektion 1 • Big-O, Big-Theta och Big-Omega

Definierar de tre asymptotiska notationerna och deras matematiska innebörd. Studenterna tillämpar varje notation för att klassificera algoritmbeteende exakt.

Lektion 2 • Mäta algoritmprestanda

Introducerar begrepp kring körningstidsmätning och varför teoretisk analys överträffar enbart prestandatester. Etablerar det analytiska tankesättet för varje efterföljande kapitel.

Lektion 3 • Analysera loopar och rekursion

Lär ut systematisk analys av nästlade loopar och rekursiva anrop. Direkt tillämpbart på varje sorterings- och sökningsalgoritm i senare kapitel.

Lektion 1 • Tvåpekare och skjutbart fönster

Introducerar mönstren med tvåpekare och skjutbart fönster för O(n)-lösningar på sorterad eller sekventiell data. Minskar avsevärt brute-force-metoders O(n²)-tid.

Lektion 2 • Hashtabeller och kollisionhantering

Förklarar design av hashfunktioner, kollisionsupplösning och interna detaljer i Python-dicts. Studenterna implementerar anpassade hash maps och löser uppslagsproblem i O(1).

Lektion 3 • Arraymanipulationstekniker

Täcker operationer på plats, prefixsummor och differensarrayer för intervallförfrågningar. Dessa mönster förekommer i majoriteten av intervjuliknande problem.

Lektion 1 • Kö, deque och prioritetskö

Implementerar FIFO-köer, dubbeländade dequeer och heapbaserade prioritetsköer. Förbereder studenterna för BFS- och schemaläggningsalgoritmproblem.

Lektion 2 • Enkellänkade och dubbellänkade listor

Bygger nodbaserade länkade listklasser med insättning, borttagning och traversering. Etablerar pekarmanipuleringsfärdigheter som används i träd och grafer senare.

Lektion 3 • Stackimplementering och tillämpningar

Implementerar stackar med listor och länkade listor, och tillämpar dem sedan på parsnings- och evalueringsproblem. Stackar ligger till grund för rekursionssimulering och backtracking.

Lektion 1 • Rekursionsgrunder

Definierar basfall, rekursiva anrop och anropsstackens beteende med visuell spårning. Korrekt rekursionsdesign är en förutsättning för söndra-och-härska och backtracking.

Lektion 2 • Söndra-och-härska-sortering

Implementerar merge sort och quicksort med fullständig differensekvationsanalys. Studenterna förstår partitioneringsstrategier och stabilitetsavvägningar.

Lektion 3 • Sökningsalgoritmer

Implementerar binärsökning och dess varianter på sorterade arrayer och svarsrymder. Binärsökning på svaret är ett nyckelmönster för optimeringsproblem.

Lektion 1 • Problemmönster för träd

Täcker sökvägssumma, lägsta gemensamma förfader och diameterproblem med hjälp av rekursion. Dessa mönster förekommer ofta i tekniska intervjuer och systemdesign.

Lektion 2 • Tries och segmentträd

Bygger prefix-tries för strängsökning och segmentträd för intervallförfrågningar. Dessa specialiserade träd löser problem som BST och heaps inte hanterar effektivt.

Lektion 3 • Balanserade träd och heaps

Introducerar balanseringskoncept för AVL- och röd-svarta träd samt heap-struktur. Studenterna förstår när självbalanserande träd är nödvändiga för prestationsgarantier.

Lektion 4 • Binära trädgrunder

Definierar trädterminologi, nodstruktur och rekursiva traverseringsordningar. Traverseringsmönster är grunden för alla trädbaserade algoritmer.

Lektion 1 • Topologisk sortering och cykeldetektion

Tillämpar Kahns algoritm och DFS-baserad topologisk sortering på DAG:ar. Cykeldetektion och ordning är avgörande för problem med beroendeupplösning.

Lektion 2 • Minimala spännande träd och Union-Find

Implementerar Kruskals och Prims algoritmer tillsammans med Union-Find-strukturen. Dessa verktyg löser problem med nätverksanslutning och klustring effektivt.

Lektion 3 • Kortaste-vägen-algoritmer

Implementerar Dijkstra, Bellman-Ford och Floyd-Warshall för viktade grafer. Studenterna väljer rätt algoritm baserat på grafens egenskaper och begränsningar.

Lektion 4 • BFS- och DFS-traverseringar

Implementerar iterativ BFS och rekursiv DFS med besöksspårning. Dessa två traverseringar ligger till grund för nästan varje grafalgoritm i detta kapitel.

Lektion 1 • Klassiska DP-problemmönster

Löser knapsack, längsta delsekvens och myntväxlingsproblem som kanoniska DP-mallar. Att bemästra dessa mallar påskyndar lösning av nya DP-problem.

Lektion 2 • DP-grunder och memoisering

Definierar överlappande delproblem och optimal delstruktur som DP-förutsättningar. Top-down-memoisering omvandlar rekursiva lösningar till effektiva DP-lösningar.

Lektion 3 • Tabulering och utrymmesoptimering

Bygger bottom-up DP-tabeller och minskar utrymme med rullande arrayer. Utrymmesoptimerad DP är avgörande för stora indatabegränsningar i tävlingsproblem.

Lektion 4 • Intervall- och rutnäts-DP

Tillämpar DP på intervallsammanfogning och rutnätsvägsproblem med 2D-tillståndsrymder. Dessa mönster utökar DP-färdigheter till matris- och intervallbaserade problemtyper.