Notat Exhaustive mbi Algoritmet, Strukturat e Të Dhënave dhe Analizën e Performancës

Hyrje në Algoritme dhe Konceptet Bazë

• Përkufizimi i Algoritmit

  • Algoritmet janë hapat e rregullt, të qartë dhe të mirëpërcaktuar që përdoren për të zgjidhur një problem të caktuar ose për të përpunuar të dhëna.
  • Përbëjnë bazën e çdo programi kompjuterik dhe mundësojnë ndarjen e një problemi kompleks në pjesë më të thjeshta, të zbatueshme dhe të verifikueshme.

• Rëndësia e Studimit të Algoritmeve

  • Përdoren në fusha të shumta të teknologjisë dhe shkencës:
    • Internet: Motorë kërkimi, rrjete sociale.
    • Biologji: Analiza e sekuencave gjenetike dhe modelimi.
    • Kompjuterikë: Kompajlerë, sisteme skedari (file systems).
    • Grafikë Kompjuterike: Lojëra, filma, realitet virtual.
    • Siguri: Kriptografi, pagesa online.
  • Zhvillojnë aftësitë intelektuale dhe logjike duke stimuluar një mënyrë të menduari të saktë, strukturueshme dhe të organizuar.

• Kriteret e Vlerësimit të Algoritmeve

  • Korrektësia (Correctness):
    • Një algoritëm është i saktë nëse jep gjithmonë rezultatin e duhur për çdo input të mundshëm dhe të vlefshëm.
    • Provohet përmes rasteve të testimit (test cases), provave matematikore ose argumenteve logjike për çdo hap.
  • Efikasiteti (Efficiency):
    • Efikasiteti Kohor (Time Complexity): Tregon kohën e nevojshme për përfundimin e ekzekutimit në varësi të madhësisë së inputit $n$. Shprehet me notacionin Big $O$, si për shembull $O(n)$, $O(n^2)$, $O(\tan(n))$, $O(\text{log}(n))$.
    • Efikasiteti Hapësinor (Space Complexity): Tregon sasinë e memories RAM që kërkohet për përpunimin e inputit dhe ruajtjen e të dhënave të ndërmjetme (variablat, matricat, listat, stekat).

• Reprezentimi Vizual dhe Tekstual i Algoritmeve

  • Flowchart: Mënyrë vizuale grafike për të treguar hapat e algoritmit përmes simboleve standarde:
    • Ovali / Formë e rrumbullakosur: Përdoret për fillimin dhe fundin e një algoritmi.
    • Paralelogrami: Përdoret për leximin/futjen e variablave dhe shtypjen e vlerave të nxjerra.
    • Drejtkëndëshi: Përdoret për llogaritje të vlerave dhe veprime procesuese.
    • Rombi: Përdoret për vendimmarrje dhe pyetje Po/Jo që përcaktojnë degëzimin e veprimeve të mëtejme.
    • Shigjetat: Tregojnë drejtimin dhe rrjedhën e ekzekutimit.
  • Pseudokodi: Version tekstual i afërt me kodin real, por pa sintaksë strikte të ndonjë gjuhe programimi; lehtëson analizimin e logjikës.
  • Kodi Real: Implementimi konkret në një gjuhë programimi (Java, Python, C++), i përdorur për testim me të dhëna reale dhe matje të kohës së ekzekutimit.

Strukturat e Të Dhënave: Array, Stack dhe Queue

• Roli i Strukturave të Të Dhënave

  • Programet ekzekutohen në CPU, por të dhënat e nevojshme tërheqen nga memoria RAM.
  • Strukturat e të dhënave përcaktojnë mënyrën se si ruhen, qasen dhe modifikohen informacionet në RAM.
  • Kërkimi (searching) dhe renditja (sorting) janë dy operacione thelbësore: fillimisht bëhet sortimi i të dhënave në një rend logjik që kërkimi i mëvonshëm të jetë maksimalisht efikas.

• Tipet Abstrakte të Të Dhënave (ADT - Abstract Data Types)

  • Përfaqësojnë koncepte logjike se si manipulohen të dhënat dhe përcaktohen përmes API-ve (Application Programming Interface).
  • Nuk ekzistojnë si struktura fizike fikse në RAM, por implementohen përmes strukturave konkrete.

• 1. Array (Vargu)

  • Koleksion elementesh të llojit të njëjtë të të dhënave me madhësi statike (përcaktohet gjatë krijimit dhe nuk ndryshon).
  • Qasja në elemente bëhet drejtpërdrejt përmes indeksit (numër i plotë integer), duke e bërë operacionin primitive dhe jashtëzakonisht të shpejtë.
  • Iterimi mbi elemente realizohet përmes cikleve (loops).

• 2. Stack (Masa / Stiva - LIFO)

  • Funksionon sipas parimit LIFO (Last In First Out) — elementi i fundit që hyn është i pari që del.
  • Operacionet Bazë:
    • $\text{push}(item)$: Shton një element në krye të stack-ut.
    • $\text{pop}()$: Heq dhe kthen elementin më të fundit nga maja.
    • $\text{isEmpty}()$: Kontrollon nëse stack-u është bosh për të shmangur gabimet.
    • $\text{size}()$: Kthen numrin e elementeve ekzistuese.
  • Mënyrat e Implementimit të Stack:
    • Përmes Linked List:
      • Çdo element (node) ruan të dhënat dhe një referencë / pointer (variabla e rezervuar $\text{next}$) drejt elementit pasardhës.
      • Ka madhësi dinamike; lejon shtimin dhe heqjen e elementeve pa kufizim paraprak.
      • Nëse referenca e një node bëhet null dhe shkëputet pa u fshirë saktë, shkaktohet loitering (kujtesa mbetet e zënë në RAM por e paarritshme).
      • Llojet e Linked List: Singly Linked List (një referencë $\text{next}$), Doubly Linked List (dy referenca: $\text{next}$ dhe $\text{previous}$), Circular Linked List (node-i i fundit lidhet me të parin).
      • Maja e stack-ut ($\text{top of the stack}$) përfaqëson pikën ku kryhen $\text{push}$ dhe $\text{pop}$.
    • Përmes Array me Kapacitet të Fiksuar (Resizing Array):
      • Përdor një array $s[]$ për të ruajtur $N$ objekte.
      • $\text{push}()$ vendos elementin e ri në $s[N]$.
      • $\text{pop}()$ kthen elementin nga $s[N-1]$.
      • Overflow: Ndodh kur tentohet të shtohet element në një stack të mbushur. Zgjidhet duke dyfishuar madhësinë e array-t ($2 \times$) automatikisht.
      • Underflow: Ndodh kur tentohet të hiqet element nga një stack bosh. Për të optimizuar hapësirën, kur stiva mbetet vetëm $\frac{1}{4}$ ($25\%$) e mbushur, madhësia përgjysmohet ($\frac{1}{2}$).
  • Përdorimet Reale të Stack:
    • Mekanizmi Undo/Redo në dokumente.
    • Butoni "Back" në shfletuesit e internetit (web browsers).
    • Menaxhimi i thirrjeve të funksioneve në kompajlerë (Call Stack).
    • Llogaritjet e shprehjeve aritmetike (p.sh., algoritmi i Dijkstra-s me dy stiva).

• 3. Queue (Rreshti - FIFO)

  • Funksionon sipas parimit FIFO (First In First Out) — elementi i parë që hyn është i pari që del.
  • Operacionet Kryesore:
    • $\text{enqueue}(item)$: Shton një element në fund të rreshtit.
    • $\text{dequeue}()$: Heq elementin nga fillimi i rreshtit.
    • $\text{isEmpty}()$: Verifikon nëse rreshti është bosh.
    • $\text{size}()$: Kthen numrin e elementeve.
  • Mënyrat e Implementimit të Queue:
    • Përmes Linked List: Përdor dy pointera — $\text{first}$ për fillimin dhe $\text{last}$ për fundin. ${\text{enqueue}()}$ shton te $\text{last}$, ndërsa ${\text{dequeue}()}$ heq nga $\text{first}$. Të dyja operacionet ekzekutohen në kohë konstante $O(1)$.
    • Përmes Array Resizable: Përdor dy indekse, $\text{head}$ dhe $\text{tail}$. Dyfishohet kur mbushet plotësisht dhe përgjysmohet kur bie në $25\%$ të kapacitetit.

• Implementimi në Java dhe Generics

  • Përdoren Generics (p.sh., $\text{Stack}<\text{Apple}>$) për të garantuar sigurinë e tipeve në kohë përkthimi dhe për të shmangur gabimet në kohë ekzekutimi (run-time errors).
  • Implementimet përdorin ndërfaqet $\text{Iterable}$ dhe $\text{Iterator}$ me metodat $\text{hasNext}()$ dhe $\text{next}()$, duke mundësuar iterimin e thjeshtë me cikle $\text{foreach}$.

• Krahasimi i Performancës dhe Memories

  • Implementimi i Stack/Queue me Linked List konsumon rreth $40\,\text{bytes}$ për çdo node (pa përfshirë objektin që referohet).
  • Operacionet $\text{push}()$, $\text{pop}()$, $\text{enqueue}()$, dhe $\text{dequeue}()$ kanë kohë konstante $O(1)$ në rastin më të keq.

Analiza e Performancës së Algoritmeve

• Arsyet e Analizës së Algoritmeve

  • Krahasimi i zgjidhjeve të ndryshme për të përzgjedhur më efikasen.
  • Shmangia e gabimeve të performancës ("performance bugs") ku kodi është korekt matematikisht, por shumë i ngadaltë për përdorim praktik.
  • Parashikimi i sjelljes së programit me input-e të mëdha (Sipas Donald Knuth).

• Metoda Shkencore në Analizë

  • Vëzhgimi (Observation): Identifikimi dhe matja e sjelljes së programit.
  • Hipoteza (Hypothesis): Ndërtimi i një modeli matematik që shpjegon vëzhgimet.
  • Parashikimi (Prediction): Përdorimi i modelit për të parashikuar kohën për input-e të reja.
  • Verifikimi (Verification): Kryerja e eksperimenteve të reja për testim.
  • Validimi (Validation): Përsëritja e procesit deri në përputhshmëri të plotë.
  • Eksperimentet duhet të jenë të riprodhueshme dhe hipotezat të mund të rrëzohen (falsifiability).

• Modeli Matematikor i Kohës së Ekzekutimit (Running Time)

  • Koha totale = $\sum (\text{çmimi i operacionit} \times \text{frekuenca e ekzekutimit})$.
  • Çmimi i operacionit varet nga hardware-i dhe kompajlleri; frekuenca varet nga algoritmi dhe madhësia e inputit $N$.

• Kostoja e Operacioneve Themelore (Matjet në MacBook Pro 2.2GHz)

  • Deklarim variable (int a): $c_1$
  • Udhëzim caktimi (a = b): $c_2$
  • Krahasim numrash të plotë (a < b): $c_3$
  • Qasje në element vargu (a[i]): $c_4$
  • Gjatësia e vargut (a.length): $c_5$
  • Alokim i vargut 1D (new int[N]): $c_6 N$
  • Alokim i vargut 2D (new int[N][N]): $c_7 N^2$
  • Mbledhje numrash të plotë (a + b): $2.1\,\text{ns}$
  • Shumëzim numrash të plotë (a * b): $2.4\,\text{ns}$
  • Pjesëtim numrash të plotë (a / b): $5.4\,\text{ns}$
  • Mbledhje me pikë të lëvizshme (a + b): $4.6\,\text{ns}$
  • Shumëzim me pikë të lëvizshme (a * b): $4.2\,\text{ns}$
  • Pjesëtim me pikë të lëvizshme (a / b): $13.5\,\text{ns}$
  • Llogaritja e Sines (Math.sin(theta)): $91.3\,\text{ns}$
  • Llogaritja e Arktangjentit (Math.atan2(y,x)): $129.0\,\text{ns}$

• Shembuj të Llogaritjes së Kompleksitetit

  • 1-SUM: Kontrollon dhe numëron elementet zero në varg; rritet në mënyrë lineare $O(N)$.
  • 2-SUM: Kontrollon çifte elementesh me dy cikle të mbivendosura; kompleksitet kuadratik $O(N^2)$.
  • 3-SUM: Kontrollon treshe elementesh me tre cikle të mbivendosura; kompleksitet kubik $O(N^3)$.

• Shkalla e Rritjes (Order of Growth)

  • $1$ — Konstant (p.sh., mbledhja e dy numrave: a = b + c;)
  • $\text{log}(N)$ — Logaritmik (p.sh., kërkimi binar / binary search: while(N>1) {N=N/2;})
  • $N$ — Linear (p.sh., gjetja e maksimumit me një cikël: for(int i=0; i<N; i++))
  • $N \text{log}(N)$ — Linearitmik (p.sh., Mergesort me teknikën divide and conquer)
  • $N^2$ — Kuadratik (p.sh., kontrolli i çifteve me cikël të dyfishtë)
  • $N^3$ — Kubik (p.sh., kontrolli i tresheve me cikël të trefishtë)
  • $2^N$ — Eksponencial (p.sh., kërkim kombinatorik / kontroll i të gjitha nënbashkësive)

• Notacionet Asimptotike

  • Big O ($O(f(N))$): Përfaqëson kufirin e sipërm (rastin më të keq / worst case).
  • Big Omega ($\Omega(f(N))$): Përfaqëson kufirin e poshtëm (rastin më të mirë / best case).
  • Big Theta ($\Theta(f(N))$): Përfaqëson kufirin e saktë asimptotik (rastin mesatar / average case).

• Binary Search (Kërkimi Binar)

  • Përdoret vetëm në vargje të renditura.
  • Krahason vlerën e kërkuar me elementin e mesit: nëse është më e vogël kërkon në gjysmën e majtë, nëse është më e madhe kërkon në të djathtën.
  • Kompleksiteti kohor është $\text{log}(N)$, dukshëm më i shpejtë se kërkimi linear $O(N)$.

• Përdorimi i Memories në Java

  • Tipet Primitive:
    • byte, boolean: $1\,\text{byte}$
    • char: $2\,\text{bytes}$
    • int: $4\,\text{bytes}$
    • double: $8\,\text{bytes}$
  • Objektet:
    • Overhead-i bazë i çdo objekti: $16\,\text{bytes}$.
    • Çdo referencë objekti (pointer): $8\,\text{bytes}$.
    • Padding: Rrumbullakos madhësinë e objektit në shumëfishin më të afërt të $8\,\text{bytes}$.
    • Shembull: Një objekt $\text{Date}$ me tre variabla int përdor $32\,\text{bytes}$ ($16\,\text{overhead} + 3 \times 4\,\text{bytes} = 28 \rightarrow \text{padihet në } 32$).
  • Vargjet (Arrays):
    • Kërkojnë $24\,\text{bytes}$ overhead shtesë për strukturën e tyre.
    • Një varg 2D int[N][N] përdor afërsisht $N^2 \times 4\,\text{bytes}$.
    • Formula e memories totale për disa struktura: afërsisht $8N + 88\,\text{bytes}$.

Algoritmet Elementare të Sortimit

• Koncepti i Sortimit

  • Process i rirregullimit të një vargu me $N$ elemente sipas një rendi të caktuar (zakonisht nga më i vogli tek më i madhi).
  • Ndërfaqja Comparable në Java:
    • Implementohet metoda $\text{compareTo}(w)$.
    • Kthen $0$ nëse objektet janë të barabarta.
    • Kthen $-1$ nëse objekti aktual $v$ është më i vogël se $w$.
    • Kthen $+1$ nëse $v$ është më i madh se $w$.
    • Metoda $\text{equals}()$ kthen vetëm true ose false.

• 1. Selection Sort (Sortimi me Përzgjedhje)

  • Skanon vargun nga e majta në të djathtë.
  • Në çdo hap $i$, kërkon elementin minimal në pjesën e pabarazuar (nga $i$ deri në $N-1$) dhe e shkëmben (swap) me elementin në pozicionin $i$
  • Karakteristikat:
    • Kërkon gjithmonë $\frac{1}{2}N^2$ krahasime, pavarësisht nëse vargu është i sortuar apo jo.
    • Bën vetëm $N$ shkëmbime (swaps / exch()).
    • Kompleksiteti kohor është gjithmonë $\Theta(N^2)$.
    • Nuk është algoritëm i qëndrueshëm (unstable) dhe nuk është efikas për lista të mëdha.

• 2. Insertion Sort (Sortimi me Futje)

  • Merr çdo element me radhë dhe e fut në pozicionin e duhur në pjesën e majtë që është e sortuar, duke e lëvizur majtas përmes shkëmbimeve të njëpasnjëshme.
  • Karakteristikat:
    • Rasti më i mirë (varg pothuajse i sortuar): $N-1$ krahasime dhe $0$ shkëmbime ($O(N)$).
    • Rasti më i keq (varg në rend zbritës): $\frac{1}{2}N^2$ krahasime dhe $\frac{1}{2}N^2$ shkëmbime.
    • Rasti mesatar: $\frac{1}{4}N^2$ krahasime dhe $\frac{1}{4}N^2$ shkëmbime.
    • Më praktik se Selection Sort; algoritëm i qëndrueshëm (stable).

• 3. Shell Sort (h-Sort)

  • Version i përmirësuar i Insertion Sort që lejon shkëmbimin e elementeve me distancë të madhe $h$ ($h\text{-distance}$).
  • Zgjidhet një sekuencë zvogëluese e $h$ (p.sh., përmes formulës $3x + 1$: $1, 4, 13, 40, 121, \dots$).
  • Kryhet $h\text{-sort}$ për çdo $h$, dhe në fund bëhet një Insertion Sort final me $h = 1$
  • Kompleksiteti kohor varet nga sekuenca e $h$: rasti më i mirë $N \text{log}_3(N)$, ndërsa rasti më i keq është nënkuadratik $O(N^{3/2})$.

Algoritmet e Avancuara të Sortimit: Merge Sort dhe Quick Sort

• Merge Sort (Sortimi me Bashkim)

  • Bazohet në parimin Divide and Conquer (Pjesëto dhe Stërvit):
    1. Ndaj vargun në dy gjysma.
    2. Sorto secilën gjysmë në mënyrë rekursive.
    3. Bashko (merge) dy gjysmat e sortuara në një varg të vetëm të renditur.
  • Rol i Indekseve gjatë Merge:
    • $lo$: Indeksi i fillimit të nënvargut të majtë.
    • $mid$: Pika e mesit (fundi i nënvargut të majtë: $a[lo \dots mid]$).
    • $hi$: Indeksi i fundit i nënvargut të djathtë ($a[mid+1 \dots hi]$).
  • Kompleksiteti Kohor dhe Hapësinor:
    • Rasti më i keq: $\Theta(N \text{log}(N))$
    • Rasti më i mirë: $\Theta(N \text{log}(N))$
    • Rasti mesatar: $\Theta(N \text{log}(N))$
    • Hapësira shtesë: $\Theta(N)$ (kërkon varg ndihmës, prandaj nuk është in-place).
  • Optimizimet Praktike në Java:
    • Testimi nëse vargu është i sortuar: if (!less(a[mid+1], a[mid])) return; pëlqen ndërprerjen e merge.
    • Cutoff te Insertion Sort për nënvargje të vogla (zakonisht me gjatësi $< 7$ elemente).
  • Varianted e Merge Sort:
    • Bottom-Up Mergesort: Version jo-rekursiv. Kryen bashkime të nënvargjeve me madhësi $1, 2, 4, 8, \dots$ Punon $\sim 10\%$ më ngadalë se Top-Down, por është i thjeshtë.
    • Natyral Mergesort: Identifikon sekuencat natyrale të sortuara ("runs") dhe i bashkon ato. Ka kompleksitet linear $O(N)$ për vargje pjesërisht të sortuara.
    • Timsort: Kombinim i Natyral Mergesort, Binary Insertion Sort dhe optimizimeve të tjera. Përdoret si algoritëm standard në Python, Java 7+ (Arrays.sort()), dhe Android.

• Quick Sort (Sortimi i Shpejtë)

  • Considerohet si një nga 10 algoritmet më të rëndësishëm të shekullit XX.
  • Mënyra e Funksionimit:
    1. Kryen përzierjen e rastësishme (shuffle) të vargut për të shmangur rastin më të keq.
    2. Zgjedh një element si pivot (p.sh., $a[lo]$).
    3. Particionimi: Vendos të gjitha elementet më të vogla se pivoti në të majtë dhe elementet më të mëdha në të djathtë përmes dy pointerave $i$ dhe $j$.
    4. Sorton dy pjesët në mënyrë rekursive.
  • Logjika e Pointerave $i$ dhe $j$:
    • Inkrementohet $i$ përsa kohë $a[i] < a[lo]$.
    • Dekrementohet $j$ përsa kohë $a[j] > a[lo]$.
    • Kur kushtet ndalojnë, shkëmbehen $a[i]$ me $a[j]$. Procesi përfundon kur $i$ dhe $j$ kryqëzohen, dhe pivoti shkëmbehet me $a[j]$.
  • Karakteristikat e Quick Sort:
    • Është algoritëm In-Place (nuk kërkon memorie shtesë për vargje ndihmëse).
    • Nuk është i qëndrueshëm (unstable).
    • Rasti më i mirë: $O(N \text{log}(N))$ (pivoti ndan vargun përgjysmë).
    • Rasti mesatar: $2 N \text{ln}(N) \approx 1.39 N \text{log}(N)$.
    • Rasti më i keq: $\frac{1}{2}N^2$ (ndodh kur vargu është i sortuar dhe nuk është bërë shuffle).
  • Problemi i Çelësave të Dyfishtë dhe Particionimi 3-Kalimësh (Dijkstra 3-Way Partitioning):
    • Kur vargu përmban shumë elemente të përsëritura, Quick Sort klasik degradon.
    • Zgjidhja sipas Dijkstra-s ndan vargun në 3 pjesë përmes pointerave $lt$, $i$, dhe $gt$:
      • Elementet më të vogla se pivoti ($< v$).
      • Elementet e barabarta me pivotin ($= v$).
      • Elementet më të mëdha se pivoti ($> v$).
    • Rregullat e Lëvizjes:
      • Nëse $a[i] < v$: shkëmbe $a[lt]$ me $a[i]$; rrit $lt$ dhe $i$.
      • Nëse $a[i] > v$: shkëmbe $a[gt]$ me $a[i]$; zvogëlo $gt$.
      • Nëse $a[i] == v$: rrit $i$.

• Stabiliteti i Algoritmeve të Sortimit

  • Aftësia e algoritmit për të ruajtur renditjen relative fillestare të elementeve me çelësa të barabartë.
  • Algoritme Stable: Insertion Sort, Merge Sort, Timsort, Bubble Sort, Counting/Radix Sort.
  • Algoritme Unstable: Selection Sort, Shell Sort, Quick Sort, Heapsort.

• Tabela Përmbledhëse e Algoritmeve të Sortimit

    | Algoritmi | In-place? | Stable? | Rasti më i mirë | Rasti Mesatar | Rasti më i keq | Shënime / Vërejtje |     | :--- | :--- | :--- | :--- | :--- | :--- | :--- |     | Selection | Po | Jo | $\frac{1}{2} N^2$ | $\frac{1}{2} N^2$ | $\frac{1}{2} N^2$ | Kryen vetëm $N$ shkëmbime (exchanges). |     | Insertion | Po | Po | $N$ | $\frac{1}{4} N^2$ | $\frac{1}{2} N^2$ | Efikas për $N$ të vogël ose vargje pjesërisht të sortuara. |     | Shell | Po | Jo | $N \text{log}_3(N)$ | Ndryshon | $c N^{3/2}$ | Kod kompakt; kompleksitet nënkuadratik. |     | Merge | Jo | Po | $\frac{1}{2} N \text{log}_2(N)$ | $N \text{log}_2(N)$ | $N \text{log}_2(N)$ | Garanci $N \text{log}(N)$; kërkon hapësirë shtesë. |     | Timsort | Jo | Po | $N$ | $N \text{log}_2(N)$ | $N \text{log}_2(N)$ | Përmirëson Merge Sort kur ekziston renditje paraprake. |     | Quick | Po | Jo | $N \text{log}_2(N)$ | $2 N \text{ln}(N)$ | $\frac{1}{2} N^2$ | Garanci probabilistike; më i shpejti në praktikë. |     | 3-way Quick | Po | Jo | $N$ | $2 N \text{ln}(N)$ | $\frac{1}{2} N^2$ | Përmirëson Quick Sort kur ka shumë çelësa të dyfishtë. |

Radhët me Prioritet (Priority Queues) dhe Heap-i Binar

• Koncepti i Priority Queue (PQ)

  • Strukturë abstrakte të dhënash ku çdo element ka një prioritet të caktuar.
  • Mbështet dy operacione kryesore: shtimi i elementit ($\text{insert}$) dhe heqja e elementit me prioritetin maksimal ($\text{delete-max}$).
  • Elementet duhet të implementojnë ndërfaqen $\text{Comparable}$.
  • Përdorimet: Algoritmet e grafikëve (Dijkstra, Prim), simulime me ngjarje, balancim ngarkese, procesim statistikash, $\text{A}^*\text{ search}$ në IA, filttrim $\text{Spam}$.

• Krahasimi i Implementimeve të Priority Queue

  • Array i Pasortuar: $\text{Insert} = O(1)$, $\text{delMax} = O(N)$, $\text{Max} = O(N)$.
  • Array i Sortuar: $\text{Insert} = O(N)$, $\text{delMax} = O(1)$, $\text{Max} = O(1)$.
  • Binary Heap: $\text{Insert} = O(\text{log}(N))$, $\text{delMax} = O(\text{log}(N))$, $\text{Max} = O(1)$.

• Struktura e Binary Heap (Heap-i Binar)

  • Përfaqësohet konceptualisht si një pemë binare e plotë (Complete Binary Tree), por ruhet fizikisht në një array (ku indeksi fillon nga $1$).
  • Rregulli i Plotësisë: Çdo nivel është plotësisht i mbushur, përveç mundësisht nivelit të fundit.
  • Heap Order Property: Vlera e prindit është gjithmonë më e madhe ose e barabartë me vlerën e fëmijëve të tij. Rrënja $a[1]$ përmban gjithmonë elementin maksimal.
  • Lartësia e një complete binary tree me $N$ nyje është $\text{lg}(N)$.

• Lidhjet Matematikore të Indekseve në Array

  • Për nyjen në pozicionin $k$:
    • Indeksi i prindit është $\lfloor k / 2 \rfloor$
    • Indeksi i fëmijës të majtë është $2k$
    • Indeksi i fëmijës të djathtë është $2k + 1$

• Operacionet Themelore në Heap

  • Swim (Noton lart):
    • Përdoret gjatë insertimit. Elementi i ri vendoset në fund të vargut ($a[N]$) dhe krahasohet me prindin ($k/2$).
    • Nëse është më i madh se prindi, shkëmbehen vendet. Procesi vazhdon lart derisa të vendoset rregulli i heap-it.
    • Kostoja maksimale: $1 + \text{lg}(N)$ krahasime.
  • Sink (Zhytet poshtë):
    • Përdoret gjatë $\text{delMax}()$. Rrënja $a[1]$ shkëmbehet me elementin e fundit $a[N]$, dhe elementi i fundit fshihet.
    • Elementi i ri në rrënjë zhytet poshtë duke u shkëmbyer me fëmijën më të madh nga të dy fëmijët ($2k$ ose $2k+1$).
    • Kostoja maksimale: $2 \text{lg}(N)$ krahasime.

• Immutability (Të Qenit i Pandryshueshëm) në Java

  • Tipat immutable nuk mund të modifikohen pas krijimit (p.sh., $\text{String}$, $\text{Integer}$, $\text{Double}$).
  • Tipat mutable mund të modifikohen (p.sh., vargjet, $\text{StringBuilder}$).
  • Në PQ, përdorimi i objekteve immutable garanton se çelësat nuk ndryshojnë vlerën gjatë qëndrimit në heap, duke parandaluar prishjen e renditjes.

• Heapsort

  • Algoritëm sortimi in-place që përdor strukturën e Heap-it me dy faza:
    1. Ndërtimi i Heap-it (Heap Construction): Shndërron vargun e paorjentuar në një max-heap duke përdorur teknikën bottom-up (thirrja e $\text{sink}()$ për nyjet jo-gjethe nga $N/2$ teposhtë). Kostoja: $O(N)$.
    2. Faza e Sortimit (Sortdown): Shkëmben vazhdimisht rrënjën (maksimumin) me elementin e fundit të vargut, zvogëlon madhësinë e heap-it dhe aplikon $\text{sink}()$ në rrënjë. Kostoja: $O(N \text{log}(N))$.

Tabelat Simbolike (Symbol Tables)

• Koncepti i Symbol Table (ST)

  • Strukturë abstrakte të dhënash e përbërë nga çifte çelës-vlerë (Key-Value pairs).
  • Gjeneralizon vargjet klasike ku çelësat mund të jenë çfarëdo lloj objekti (p.sh., $\text{String}$, $\text{Integer}$).
  • Shembull real: DNS (Domain Name System) ku çelësi është emri i domain-it dhe vlera është IP adresa.

• API e Symbol Table

  • $\text{put}(Key, Value)$: Fut çiftin e ri ose mbishkruan vlerën nëse çelësi ekziston.
  • $\text{get}(Key)$: Kthen vlerën për çelësin e dhënë, ose null nëse mungon.
  • $\text{delete}(Key)$: Fshin çelësin dhe vlerën (Lazy delete vendos $\text{put}(key, null)$).
  • $\text{contains}(Key)$: Kthen true nëse $\text{get}(key) \neq null$
  • $\text{isEmpty}()$, $\text{size}()$, $\text{keys}()$

• Konventat dhe Rregullat mbi Çelësat

  • Vlerat nuk mund të jenë null.
  • Çelësat duhet të jenë Immutable.
  • Metoda $\text{equals}()$ në Java duhet të plotësojë 4 vetitë:
    • Refleksive: x.equals(x) == true
    • Simetrike: x.equals(y) == y.equals(x)
    • Transitive: Nëse x.equals(y) dhe y.equals(z), atëherë x.equals(z)
    • Jo-null: x.equals(null) == false

• Implementimet Standarde të Symbol Table

  • Linked List e Pasortuar (Sequential Search):
    • Kërkimi ($\text{Search}$) kërkon skanimin e të gjithë listës: $O(N)$.
    • Futja ($\text{Insert}$) kërkon skanim për të verifikuar nëse ekziston: $O(N)$.
  • Array i Sortuar (Binary Search):
    • Kërkimi ($\text{Search}$) përdor kërkim binar: $O(\text{log}(N))$.
    • Futja ($\text{Insert}$) dhe fshirja ($\text{Delete}$) kërkojnë zhvendosjen e elementeve: $O(N)$.

• API për Symbol Table të Sortuar

  • Ofron metoda shtesë: $\text{min}()$, $\text{max}()$, $\text{floor}(k)$ (çelësi më i madh $\le k$), $\text{ceiling}(k)$ (çelësi më i vogël $\ge k$), $\text{rank}(k)$ (numri i çelësave shtesë $< k$), $\text{select}(i)$, $\text{deleteMin}()$, $\text{deleteMax}()$.

Pemët Binare të Kërkimit (Binary Search Tree - BST)

• Struktura e BST

  • Një pemë binare ku çdo nyje përmban një çelës, një vlerë, dy referenca (subtree $\text{left}$ dhe $\text{right}$), dhe një variabël $\text{count}$ (madhësia e nënpemës).
  • Rregulli i Renditjes Simetrike:
    • Çdo çelës në nënpemën e majtë ($\text{left}$) është strictly më i vogël se çelësi i nyjes.
    • Çdo çelës në nënpemën e djathtë ($\text{right}$) është strictly më i madh se çelësi i nyjes.

• Operacionet në BST

  • Search (get): Bën krahasim rekursiv me çelësin e nyjes aktuale. Nëse është më i vogël shkon majtas, nëse është më i madh shkon djathtas.
    • Rasti mesatar: $\sim 1.39 \text{log}(N)$ krahasime.
    • Rasti më i keq: $N$ krahasime (kur druri shndërrohet në listë linearish të lidhur).
  • Insert (put): Kërkon çelësin; nëse e gjen e përditëson, përndryshe shton nyjen e re në lidhjen null përkatëse dhe përditëson variablën $\text{count}$.
  • Min dhe Max: $\text{Min}$ gjendet duke ecur gjithmonë majtas deri te null link; $\text{Max}$ duke ecur gjithmonë djathtas.
  • Floor dhe Ceiling:
    • $\text{Floor}(k)$: Nëse $k == \text{key}$, floor është $k$. Nëse $k < \text{key}$, floor është në nënpemën e majtë. Nëse $k > \text{key}$, floor është në nënpemën e djathtë (nëse ekziston), përndryshe është vetë nyja.

• Traversimi i Pemës (Tree Traversal)

  • Inorder (LVR): Traversim majtas $\rightarrow$ nyja $\rightarrow$ djathtas. Kthen çelësat të renditur në mënyrë rritëse.
  • Preorder (VLR): Nyja $\rightarrow$ majtas $\rightarrow$ djathtas.
  • Postorder (LRV): Majtas $\rightarrow$ djathtas $\rightarrow$ nyja.

• Fshirja në BST (Delete Operations)

  • Lazy Delete: Vendos vlerën në null, por e lë çelësin si "tombstone". Përkeqëson performancën sepse nyjet e fshira nuk çlirohen kurrë.
  • DeleteMin: Shkon majtas deri te nyja pa fëmijë të majtë, e zëvendëson me fëmijën e djathtë dhe përditëson numëruesit.
  • Hibbard Delete (Fshirja e çfarëdo nyjeje):
    • Nëse nyja ska fëmijë ($0$ fëmijë): Fshihet lidhja me të.
    • Nëse nyja ka $1$ fëmijë: Zëvendësohet me fëmijën e saj.
    • Nëse nyja ka $2$ fëmijë: Zëvendësohet me pasardhësin e saj të drejtpërdrejtë (minimi i nënpemës së djathtë). Nyja e fshirë çlirohet për $\text{Garbage Collection}$.

Pemët e Balancuara të Kërkimit: 2–3 Tree dhe Red-Black BST

• 1. Pemët 2–3 (2–3 Trees)

  • Pemë kërkimi e balancuar në mënyrë perfekte.
  • Llojet e nyjeve:
    • 2-node: Përmban 1 çelës dhe ka 2 fëmijë.
    • 3-node: Përmban 2 çelësa dhe ka 3 fëmijë.
  • Balancimi Perfekt: Çdo rrugë nga rrënja ($\text{root}$) deri te një null link ka ekzaktësisht të njëjtën gjatësi.
  • Lartësia e drurit është $\Theta(\text{log}(N))$ në të gjitha rastet.
  • Insertimi: Nëse futet në një 2-node, shndërrohet në 3-node. Nëse futet në një 3-node, krijohet përkohësisht një 4-node e cila ndahet (split), duke ngritur çelësin e mesëm te prindi.

• 2. Red–Black BST (Pemët e Kuqe-zi)

  • Implementim i logjikës së pemës 2–3 përmes një BST standarde me link-a të ngjyrosur (të kuq dhe të zi).
  • Rregullat e Red-Black BST:
    1. Link-at e kuq anojnë gjithmonë majtas (Left-Leaning).
    2. Asnjë nyje nuk mund të ketë dy link-a të kuq të njëpasnjëshëm (në seri).
    3. Çdo rrugë nga root te null link përmban numër të njëjtë link-ash të zi (Perfect Black Balance).
  • Performanca e Red–Black BST:
    • Pasqyrim $1\text{ me }1$ me pemët 2–3.
    • Lartësia e drurit është $\le 2 \text{log}(N)$ në rastin më të keq, dhe $\sim 1.0 \text{log}(N)$ në praktikë.
    • Operacionet $\text{search}$, $\text{insert}$, dhe $\text{delete}$ ekzekutohen gjithmonë në kohë logaritmike garantuar $O(\text{log}(N))$.

Tabelat Hash (Hash Tables)

• Konceptet Bazë të Hashing

  • Elementet ruhen në një varg të indeksuar ku indeksi llogaritet përmes një funksioni hash mbi çelësin.
  • Komponentët: Funksioni Hash, Testi i Barazisë ($\text{equals}$), Strategjia e Zgjidhjes së Kolizioneve.

• Hash Code në Java

  • Të gjitha klasat trashëgojnë metodën $\text{hashCode}()$, e cila kthen një numër të plotë $32\text{-bit}$.
  • Kërkesa kryesore: Nëse x.equals(y), atëherë detyrimisht x.hashCode() == y.hashCode().
  • Horner's Method për String Hashing:
    • $h = s[0] \cdot 31^{L-1} + \dots + s[L-3] \cdot 31^2 + s[L-2] \cdot 31^1 + s[L-1] \cdot 31^0$
  • Uniform Hashing Assumption: Çdo çelës ka gjasa të barabarta të mapohet në cilindo indeks nga $0$ deri në $M-1$
  • Birthday Problem: Tregon se kolizionet ndodhin shumë shpejt edhe në tabela të mëdha.

• Metodat e Zgjidhjes së Kolizioneve

  • 1. Closed Addressing (Separate Chaining - Zinxhirimi i Ndarë):
    • Çdo indeks i vargut kryesor përmban një listë të lidhur (linked list).
    • Kur dy çelësa kanë të njëjtin hash, shtohen në zinxhirin e atij indeksi.
    • Resizing: Dyfishohet $M$ kur raporti $N/M \ge 8$; përgjysmohet kur $N/M \le 2$
  • 2. Open Addressing (Adresimi i Hapur):
    • Të gjitha çiftet ruhen drejtpërdrejt në vargun kryesor ($M > N$).
    • Linear Probing: Nëse pozicioni është i zënë, provohet indeksi tjetër sekuencial ($i+1, i+2, \dots$). Shkakton problem Clustering (grumbullimi i blloqeve të zëna).
    • Quadratic Probing: Përdor formulën $h(x) = (f(x) + i + i^2) \pmod M$
    • Double Hashing: Përdor dy funksione hash: $h(x) = (h_1(x) + i \cdot h_2(x)) \pmod M$. Eliminon clustering-un.
    • Resizing në Open Addressing: Dyfishohet $M$ kur $N/M \ge 1/2$; përgjysmohet kur $N/M \le 1/8$
  • 3. Variante të Avancuara:
    • Two-Probe Hashing: Hashohet çelësi në dy pozicione të ndryshme dhe vendoset në listën më të shkurtër (reducion gjatësinë në $\text{log}(N)$).
    • Cuckoo Hashing: Përdor dy vende të mundshme; nëse janë të zëna, shpronëson (evicts) çelësin ekzistues. Garanton kërkim $O(1)$ në rastin më të keq.

• Sulmet me Kompleksitet Algoritmik (Algorithmic Complexity Attacks / DoS)

  • Sulmuesit targetojnë funksionin hash duke dërguar çelësa që prodhojnë të njëjtin vlerë hash, duke e degraduar tabelën nga $O(1)$ në $O(N)$.
  • Zgjidhje: Përdorimi i funksioneve hash kriptografike të sigurta njëkahëshe (SHA-256, MD5) me veti të efektit ortek (Avalanche effect).

• Krahasimi Përfundimtar: Hash Tables vs. Balanced Search Trees

    | Karakteristika | Hash Tables | Balanced Search Trees (Red-Black) |     | :--- | :--- | :--- |     | Koha e Kërkimit / Futjes | $O(1)$ mesatare | $O(\text{log}(N))$ garantuar |     | Renditja e Çelësave | Nuk mbështetet | Mbështetet (Inorder traversal) |     | Varësia | Varet nga funksioni Hash | Struktura është e balancuar vetvetiu |     | Përdorimi i Memories | Më pak memorie (pa pointera shtesë) | Më shumë memorie (përmban pointera) |     | Implementimi në Java | HashMap, HashSet, IdentityHashMap | TreeMap, TreeSet |