Kozi ya Data Structures na Algorithms

Somo 1 • Majedwali ya Heshimu na Misingi ya Heshimu

Inatanguliza uhifadhi wa ufunguo-thamani kupitia utendaji wa hash na safu za ndoo. Inawaandaa wanafunzi kwa ushughulikiaji wa migongano na uchambuzi wa utendaji wa wastani.

Somo 2 • Safu na Safu Zinazobadilika

Inatanguliza uhifadhi wa kumbukumbu inayoendelea na ufikiaji wa msingi wa faharasa. Inaunganisha safu tuli na mikakati ya kubadilisha saizi inayotumika katika utekelezaji halisi.

Somo 3 • Orodha Zilizounganishwa na Mnyororo wa Viashiria

Inafundisha uhifadhi wa msingi wa nodi kwa kutumia viashiria au marejeleo. Inalinganisha orodha zilizounganishwa na safu ili kufafanua ubadilishanaji katika uwekaji na upitishaji.

Somo 4 • Kumbukumbu, Vigezo, na Aina za Data

Inashughulikia jinsi data inavyohifadhiwa kwenye kumbukumbu na jinsi aina za primitivi zinavyotofautiana. Inaanzisha mfano wa akili unaohitajika kwa uchambuzi wote wa miundo inayofuata.

Somo 1 • Mbinu za Kipimo cha Kiwango cha Rejea

Inaunganisha uchambuzi wa nadharia na majaribio ya muda yaliyopimwa. Wanafunzi wanabuni vipimo vilivyodhibitiwa ili kuthibitisha au kupinga utabiri wa nadharia.

Somo 2 • Utata wa Nafasi na Ubadilishanaji

Inachambua matumizi ya nafasi msaidizi pamoja na gharama za muda. Inaangazia ubadilishanaji wa muda na nafasi wa kawaida unaoongoza uteuzi wa algorithm kwa vitendo.

Somo 3 • Mahusiano ya Kujirudia

Inatanguliza mahusiano ya kujirudia kama zana ya kuchambua algorithm za urejeshaji. Inashughulikia Nadharia Mkuu na mbinu za ubadilishaji kwa kutatua.

Somo 4 • Big-O, Big-Theta, na Big-Omega

Inafafanua nukuu za asymptotiki na maana yao ya hisabati. Inatoa msamiati unaotumika katika kozi nzima kwa kulinganisha utendaji wa algorithm.

Somo 1 • Mpangilio wa Msingi wa Ulinganisho

Inashughulikia mpangilio wa viputo, uteuzi, na uwekaji na uchambuzi kamili wa utata. Inaanzisha hisia ya msingi kabla ya kuanzisha mbinu bora zaidi.

Somo 2 • Mpangilio wa Gawanya na Tawala

Inafundisha mpangilio unganisha na mpangilio wa haraka kwa kutumia mtengano wa urejeshaji. Inaunganisha uchambuzi wa uhusiano wa kujirudia kutoka Sura ya 2 na utendaji halisi wa kupanga.

Somo 3 • Uteuzi wa Algorithm ya Kupanga

Inaunganisha maarifa yote ya kupanga katika mfumo wa uamuzi. Wanafunzi wanaolinganisha chaguo la algorithm na saizi ya ingizo, usambazaji wa data, na vikwazo vya kumbukumbu.

Somo 4 • Algorithm za Kupanga kwa Muda wa Mstari

Inawasilisha mpangilio wa kuhesabu, mpangilio wa radikisi, na mpangilio wa ndoo kama mbinu zisizo za ulinganisho. Inafafanua masharti ambayo muda wa mstari unaweza kupatikana.

Somo 1 • Kukariri na DP ya Juu-Chini

Inapanua urejeshaji kwa kuhifadhi matokeo ili kuondoa hesabu isiyo ya lazima. Inatumika kama daraja kwa sura kamili ya upangaji programu inayofuata.

Somo 2 • Utafutaji wa Mstari na Binary

Inalinganisha utafutaji wa mfuatano na utafutaji wa kugawanya kwenye data iliyopangwa na isiyopangwa. Inaanzisha masharti ya awali na dhamana za utata za kila mbinu.

Somo 3 • Mkakati wa Gawanya na Tawala

Inarasimisha dhana ya gawanya-tawala-unganisha zaidi ya kupanga. Wanafunzi wanaitumia kwa shida kama safu ndogo ya juu na jozi ya pointi zilizo karibu zaidi.

Somo 4 • Mbinu za Kurejea Nyuma

Inatanguliza utafutaji wa kimfumo na upogoaji kupitia kurejea nyuma. Inaunganisha miti ya simu za urejeshaji na kuridhika kwa vikwazo na matatizo ya mchanganyiko.

Somo 1 • Misingi ya Mti Binary

Inafafanua istilahi za mti, mahusiano ya nodi, na sifa za muundo. Inaweka msingi wa algoriti zote za miti katika msamiati wa pamoja na mfano wa akili.

Somo 2 • Miti Nyekundu-Nyeusi na Miti-B

Inashughulikia sheria za kupaka rangi nyekundu-nyeusi na muundo wa mti wa B wenye njia nyingi. Inaunganisha hizi na uorodheshaji wa hifadhidata na matumizi ya mfumo wa faili.

Somo 3 • Miti ya AVL na Mizunguko

Inatanguliza miti ya AVL iliyosawazishwa kwa urefu na kesi nne za mzunguko. Wanafunzi wanatekeleza kusawazisha kwa kujitegemea ili kuhakikisha utendaji wa O(log n).

Somo 4 • Algoriti za Upitishaji wa Mti

Inashughulikia upitishaji wa ndani, kabla, baada, na kiwango cha mpangilio. Inaunganisha chaguo la upitishaji na mahitaji maalum ya matokeo na algoriti za mwisho.

Somo 1 • Utafutaji wa Kina-Kwanza

Inatekeleza DFS kwa urejeshaji na kurudia na nyakati za ugunduzi na kumaliza. Inaunganisha DFS na ugunduzi wa mzunguko, mpangilio wa topolojia, na vipengele vilivyounganishwa.

Somo 2 • Mpangilio wa Topolojia

Hupata mpangilio wa topolojia kutoka kwa nyakati za kumaliza za DFS na algoriti ya Kahn. Inatumia mpangilio katika utatuzi wa utegemezi na shida za kupanga kazi.

Somo 3 • Istilahi za Grafu na Uwakilishi

Inafafanua wima, kingo, zilizoelekezwa dhidi ya zisizoelekezwa, na grafu zenye uzito. Inalinganisha uwakilishi wa matrix ya ukaribu na orodha ya ukaribu kwa gharama ya nafasi na ufikiaji.

Somo 4 • Utafutaji wa Upana-Kwanza

Inatekeleza BFS kwa kutumia foleni na kuchambua utata wake O(V+E). Inatumia BFS kupata njia fupi zaidi katika grafu zisizo na uzito.

Somo 1 • Miti Inayojumuisha ya Kiwango cha Chini: Kruskal

Inajenga MST kwa kuongeza kingo za uzito wa chini kwa uchoyo kwa kutumia Muungano-Tafuta. Inachambua usahihi kupitia sifa ya kukata na sifa ya mzunguko wa MST.

Somo 2 • Algoriti ya Njia Fupi ya Dijkstra

Inatekeleza Dijkstra kwa kutumia foleni ya kipaumbele ya rundo la chini na utata O((V+E) log V). Inashughulikia uthibitisho wa usahihi kupitia kigezo cha kustarehesha kwa uchoyo.

Somo 3 • Njia Fupi za Jozi Zote

Inasuluhisha njia fupi kati ya kila jozi ya wima kwa kutumia Floyd-Warshall. Inachambua uundaji wa upangaji programu wa O(V³) na uundaji upya wa njia.

Somo 4 • Miti Inayojumuisha ya Kiwango cha Chini: Prim

Inakua MST kutoka kwa wima mbegu kwa kutumia foleni ya kipaumbele katika algoriti ya Prim. Inalinganisha Prim na Kruskal kwa msongamano wa grafu na utata wa utekelezaji.

Somo 1 • Matatizo ya Kawaida ya DP 1D

Inasuluhisha Fibonacci, kupanda ngazi, na kubadilisha sarafu kwa kutumia majedwali ya DP 1D. Inajenga hisia ya kujaza jedwali kabla ya kuendelea na uundaji wa 2D.

Somo 2 • DP kwenye Miti na Grafu

Inatumia DP kwenye miundo ya miti na DAG kwa matatizo ya juu ya uboreshaji. Inashughulikia DP ya mti kwa kipenyo, seti huru, na DP kwenye njia za DAG.

Somo 3 • Matatizo ya Mkoba na Vikundi

Inasuluhisha mkoba 0/1, mkoba usio na kikomo, na jumla ya vikundi kwa majedwali ya DP. Inaunganisha hizi na shida za ugawaji wa rasilimali na maamuzi ya uwezekano.

Somo 4 • Matatizo ya Kawaida ya DP 2D

Inapanua DP hadi majedwali yenye vipimo viwili kwa matatizo ya mfuatano na gridi. Inashughulikia mfuatano mrefu zaidi wa kawaida, umbali wa uhariri, na kuhesabu njia za gridi kwa matokeo kamili ya uhusiano wa kujirudia.

Somo 5 • Uboreshaji wa Nafasi katika DP

Inapunguza nafasi ya jedwali la DP kutoka O(n²) hadi O(n) au O(1) kwa kutumia safu zinazozunguka. Inatumia uboreshaji wa nafasi kwa mkoba, LCS, na umbali wa uhariri.