Pythonkurs med datastrukturer och algoritmer

Lektion 1 • Funktioner och omfattning

Definierar återanvändbara funktioner med parametrar, returvärden och räckviddsregler. Förbereder studenterna på att kapsla in DSA-logik i rena, testbara enheter.

Lektion 2 • Kontrollflöde och iteration

Lär ut if/elif/else-förgrening, for- och while-loopar samt loopkontrollsatser. Gör det möjligt för studenterna att uttrycka algoritmisk logik i Python.

Lektion 3 • Felhantering och felsökning

Introducerar undantag, try/except-block och felsökningsverktyg. Utrustar studenterna att skriva robust kod och diagnostisera fel i komplexa program.

Lektion 4 • Grundläggande datatyper och variabler

Täcker heltal, flyttal, strängar, booleska värden och typomvandling. Tillhandahåller de dataprimitiver som används i varje algoritmimplementation framöver.

Lektion 1 • Iteratorer, generatorer och lat evaluering

Förklarar iteratorprotokollet, generatorfunktioner och yield. Möjliggör minneseffektiv genomgång av stora datamängder i DSA-problem.

Lektion 2 • Listor och tupler på djupet

Utforskar indexering, slicing, mutation och tupelimmutabilitet. Dessa sekvenstyper ligger till grund för de arraybaserade datastrukturer som tas upp senare.

Lektion 3 • Lexikon och mängder

Täcker hashbaserad lagring, nyckel-värde-operationer och mängdalgebra. Stöder direkt implementationer av hashtabeller och grafgrannlistor.

Lektion 4 • List- och lexikonlistomfattningar

Lär ut koncis syntax för listomfattningar för att filtrera och transformera samlingar. Minskar mängden standardkod i algoritmimplementationer genom hela kursen.

Lektion 1 • Introduktion till algoritmanalys

Definierar algoritmers korrekthet, effektivitet och behovet av formell analys. Etablerar det analytiska tankesätt som tillämpas på varje datastruktur och algoritm framöver.

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

Formaliserar asymptotisk notation och vanliga komplexitetsklasser. Tillhandahåller den vokabulär som används för att beskriva varje algoritm i efterföljande kapitel.

Lektion 3 • Analysera loopar och rekursiva anrop

Lär ut stegräkning för loopar och rekursionsekvationer för rekursion. Förbereder direkt studenterna på att analysera sorterings- och trädalgoritmer.

Lektion 4 • Profilera Python-kod

Använder timeit, cProfile och memory_profiler för att mäta verklig prestanda. Kopplar samman teoretisk komplexitet med mätbart exekveringsbeteende i Python.

Lektion 1 • Komplexitetsjämförelse av linjära strukturer

Jämför tids- och rymdkomplexitet över alla studerade linjära strukturer. Möjliggör informerat strukturval för algoritmdesignproblem.

Lektion 2 • Enkellänkade och dubbellänkade listor

Bygger nodklasser och listoperationer inklusive insättning, borttagning och genomgång. Introducerar pekarbaserat tänkande som är nödvändigt för träd och grafer.

Lektion 3 • Stackar: implementation och tillämpningar

Implementerar stackar med hjälp av listor och länkade listor och tillämpar dem sedan på verkliga problem. Demonstrerar LIFO-semantik som används i rekursion, parsning och backtracking.

Lektion 4 • Köer, dequeuer och prioritetsköer

Täcker FIFO-köer, dubbelsidiga dequeuer och heap-backade prioritetsköer. Förbereder studenterna för BFS, schemaläggning och giriga algoritmproblem.

Lektion 1 • Kvadratiska sorteringsalgoritmer

Implementerar bubbelsortering, urvalssortering och insättningssortering med steg-för-steg-analys. Tillhandahåller O(n²)-baslinjen mot vilken snabbare sorteringar mäts.

Lektion 2 • Sökalgoritmer

Implementerar linjär sökning och binär sökning med komplexitetsbevis. Kopplar sökning till krav på sorterad data och verkliga intervjuproblem.

Lektion 3 • Grunderna i rekursion

Definierar basfall, rekursiva fall och anropsstacken. Bygger den mentala modell som krävs för trädgenomgång och söndra-och-härska-algoritmer.

Lektion 4 • Linjär tid och hybridsortering

Täcker räknesortering, radix-sortering och Timsort som används i Pythons inbyggda sortering. Utökar studenternas verktygslåda bortom jämförelsebaserad sortering.

Lektion 1 • Binära sökträd

Implementerar BST-insättning, sökning och borttagning med O(log n) analys i genomsnitt. Demonstrerar ordnad datalagring och hämtning med hjälp av trädstruktur.

Lektion 2 • Tries och prefixträd

Konstruerar ett trie för insättning av strängar, sökning och prefixmatchning. Möjliggör effektiva lösningar för autocomplete och ordbokssökning.

Lektion 3 • Binära träd och genomgångar

Definierar trädterminologi och implementerar in-order-, pre-order- och post-order-genomgångar. Etablerar det rekursiva genomgångsmönster som används i alla trädalgoritmer.

Lektion 4 • Heapar och heapoperationer

Bygg en max-heap och en min-heap, implementera heapify och heap sort. Stöder direkt implementationer av prioritetsköer och giriga algoritmer.

Lektion 1 • Avancerade grafproblem

Täcker starkt sammankopplade komponenter, bipartit kontroll och grunderna i nätverksflöde. Utökar graffärdigheter till komplexa verkliga problemkategorier.

Lektion 2 • Grafre presentationer och terminologi

Definierar riktade, oriktade, viktade och cykliska grafer med grannliste- och matrisrepresentationer. Etablerar grunden för alla grafalgoritmimplementationer.

Lektion 3 • Algoritmer för kortaste vägen

Implementerar Dijkstras och Bellman-Ford-algoritmer för viktade grafer. Utrustar studenterna att lösa routing- och kostnadsminimeringsproblem.

Lektion 4 • Minimala spännande träd

Implementerar Kruskals och Prims algoritmer med hjälp av union-find och prioritetsköer. Löser nätverksdesignproblem som kräver anslutning till minimal kostnad.

Lektion 1 • Giriga algoritmer och backtracking

Implementerar giriga strategier för intervallplanering och Huffman-kodning, plus backtracking för N-damer och delmängder. Kompletterar den grundläggande verktygslådan för algoritmdesign.

Lektion 2 • Tabulation och bottom-up DP

Bygger DP-tabeller iterativt för myntväxling, trappsteg och rutnätsvägar. Eliminerar rekursionsoverhead och förtydligar logiken för tillståndsövergångar.

Lektion 3 • Introduktion till dynamisk programmering

Definierar överlappande delproblem och optimal delstruktur som förutsättningar för DP. Kontrasterar DP med söndra-och-härska för att klargöra när var och en tillämpas.

Lektion 4 • Memoization och top-down DP

Konverterar naiv rekursion till memoiserade lösningar med ordböcker och functools.lru_cache. Demonstrerar dramatisk komplexitetsminskning för Fibonacci och liknande problem.