CS240 Algoritmikë dhe Struktura të Dhënash
Section outline
-
Qëllimi i kursit është studimi i teknikave themelore të algoritmeve dhe strukturat e të dhënave që janë më të përdorshme në fushën e programimit, analiza shkencore e efikasitetit të tyre, zbatimet praktike të tyre.
-
-
Kursin do ta fillojmë me një përsëritje të gjuhës Java dhe të elementeve themelorë të programimit. Po ashtu do të shqyrtojmë edhe disa algoritma dhe struktura të dhënash elementare si: çantat, rradhët dhe stivat. Do të diskutojmë rreth abstragimit të algoritmeve dhe strukturave (ndarjes së qartë ndërmjet ndërfaqes dhe implementimit).
-
-
Këtë javë do të shqyrtojmë kohën që i duhet një programi për tu ekzekutuar, pse disa algoritme janë më të shpejta se disa të tjera, dhe si mund ta përmirësojmë efikasitetin e algoritmeve. Do të shikojmë se ç'është rendi i vështirësisë së një algoritmi (order of complexity), dhe disa nga rendet e vështirësisë më të zakonshme. Gjithashtu do të studjojmë problemin gjej-bashko (union-find), disa algoritme të ndryshme për zgjidhjen e këtij problemi, dhe do të analizojmë efikasitetin e këtyre algoritmeve në situata të ndryshme.
-
-
Këtë javë do të mbarojmë diskutimin e algoritmeve Gjej-Bashko (që mbeti pa përfunduar javën e kaluar), do shikojmë algoritmin Bashkim-i-Shpejtë, si dhe variantet e përmirësuara të tij: Bashkim-i-Shpejtë i Barazpeshuar dhe Bashkim-i-Shpejtë me shkurtim Rruge.
Më pas do të shqyrtojmë strukturat: Çanta, Rradhë dhe Stiva, ndërfaqet e tyre të programimit, implementimet e tyre me lista të lidhura dhe me vektorë, dhe efikasitetin e algoritmeve përkatëse.
Po na doli koha do fillojmë edhe me algoritmet e thjeshta të renditjes: Renditja me Përzgjedhje (Selection Sort), Renditja me Ndërfutje (Insertion Sort), dhe Shellsort. Për secilin rast do studjojmë efikasitetin e tyre në rastet normale dhe situatat më të mira dhe më të këqija.
Në orën e praktikës do zgjidhim pjesën e parë të problemit të filtrimit (http://coursera.cs.princeton.edu/algs4/assignments/percolation.html). Pjesën e dytë e keni detyrë (afati i dorëzimit pas 2 javësh).
-
-
-
Students mustMark as done
Detyra3
-
-
-
Do fillojmë me algoritmet e thjeshta të renditjes (të cilat nuk patëm kohë ti fillonim javën e kaluar): Renditja me Përzgjedhje (Selection Sort), Renditja me Ndërfutje (Insertion Sort), dhe Shellsort. Për secilin rast do studjojmë efikasitetin e tyre në rastet normale dhe situatat më të mira dhe më të këqija. Po na doli koha mund të fillojmë edhe me Mergesort (Renditja me Ndërthurje).
-
-
-
-
Këtë javë do përfundojmë analizën e Reshpe (Quicksort), dhe do vazhdojmë me Rradhët me Përparësi (Priority Queues), Pirgjet Dyjare (Binary Heaps), Repirg (Heapsort), etj.
-
-
Këtë javë do përfundojmë Pirgjet Dyjare (Binary Heaps) dhe Repirg (Heapsort), dhe do fillojmë me Tabela të Thjeshta Simbolesh (Elementary Symbol Tables). Nëse na del koha do vazhdojmë me Pemët Dyjare të Kërkimit (Binary Search Trees).
-
-
Do përfundojmë Pemët Dyjare të Kërkimit (Binary Search Trees), veprimet e renditura, fshirja.
Do fillojmë me Pemët e Barazpeshuara të Kërkimit, pemët e kërkimit 2-3, pemët dyjare kuq-e-zi të kërkimit (red-black BSTs), pemët e barazpeshuara B-tree.
-
-
Fillimisht do shikojmë B-trees (që na mbetën nga java e kaluar), dhe më pas do shikojmë zbatime gjeometrike të BST-ve (Binary Search Trees -- Pemëve Dyjare të Kërkimit):
- kërkim në një hapësirë 1 dimensionale
- gjetja e pikëprerjeve të segmenteve
- kërkim në një hapësirë 2 dimensionale dhe K dimensionale
- gjetja e prerjes së intervaleve
- gjetja e prerjes së drejtkëndshave
- kërkim në një hapësirë 1 dimensionale
-
Do mbarojmë gjetjen e prerjes së segmenteve dhe të drejtkëndëshave me BST.
Do vazhdojmë me Tabelat Mishmash (Hash Tables): funksionet mishmash (hash functions), listat e veçuara (separate chaining), shqyrtimi me rradhë (linear probing), dhe variante të tyre.
Në orën e praktikës do shikojmë disa zbatime ku përdoren tabelat mishmash: bashkësitë (SET), fjaloret (Dictionary), treguesit (index), etj.
-
-
- Paraqitja e strukturës së grafeve.
- Kërkimi sipas thellësisë (depth-first search)
- Kërkimi sipas gjerësisë (breadth-first search)
- përbërësit e lidhur (connected components)
- Digrafet (directed graphs)
- Kërkimi në digraf
- Renditja topologjike (topological sort)
- përbërësit e lidhur në digraf
- Paraqitja e strukturës së grafeve.
-
Do përfundojmë grafet me drejtim, Renditjen Topologjike (Topological Sort), Përbërësit e Lidhur Fort (Strongly Connected Components), etj.
Do vazhdojmë me Pemët Përfshirëse Minimale (Minimal Spanning Trees), algoritmi lakmitar (greedy algorithm), grafet ku brinjët kanë peshë, algoritmi Kruskal për gjetjen e MST, algoritmi Prim, etj.
-
-
Do përfundojmë algoritmin e Kruskalit dhe algoritmin e Primit për gjetjen e MST (pemës gjithpërfshirëse minimale).
Do vazhdojmë me problemin e gjetjes së rrugës më të shkurtër në një graf me drejtim dhe me peshë. Algoritmi Dijkstra.
-
-
-