Kursong Data Structures and Algorithms

Aralin 1 • Mga Hash Table at mga Pangunahing Kaalaman sa Hashing

Ipinapakilala ang key-value storage sa pamamagitan ng mga hash function at bucket array. Inihahanda ang mga mag-aaral para sa paghawak ng collision at pagsusuri ng average-case na performance.

Aralin 2 • Mga Array at Dynamic Array

Ipinapakilala ang magkakadikit na imbakan ng memorya at access na batay sa index. Ikinokonekta ang mga static na array sa mga estratehiya ng dynamic resizing na ginagamit sa mga tunay na implementasyon.

Aralin 3 • Mga Linked List at Pointer Chain

Itinuturo ang imbakan na batay sa node gamit ang mga pointer o reference. Ikinukumpara ang mga linked list sa mga array para linawin ang mga trade-off sa insertion at traversal.

Aralin 4 • Memorya, Variables, at mga Uri ng Datos

Sinasaklaw kung paano iniimbak ang datos sa memorya at kung paano nagkakaiba ang mga primitive type. Itinatag ang mental model na kailangan para sa lahat ng kasunod na pagsusuri ng istraktura.

Aralin 1 • Mga Teknik ng Empirical Benchmarking

Ini-uugnay ang teoretikal na pagsusuri sa sinukat na mga eksperimento sa runtime. Ang mga mag-aaral ay nagdidisenyo ng kontroladong mga benchmark para patunayan o hamunin ang mga teoretikal na prediksyon.

Aralin 2 • Kompleksidad ng Espasyo at mga Trade-off

Sinusuri ang paggamit ng auxiliary space kasama ng mga gastos sa oras. Itinatampok ang mga klasikong trade-off sa oras-espasyo na gumagabay sa praktikal na pagpili ng algorithm.

Aralin 3 • Mga Recurrence Relation

Ipinapakilala ang mga recurrence bilang isang tool sa pagsusuri ng mga recursive algorithm. Sinasaklaw ang Master Theorem at mga pamamaraan ng substitution sa paglutas ng mga ito.

Aralin 4 • Big-O, Big-Theta, at Big-Omega

Tinutukoy ang mga asymptotic notation at ang kanilang matematikal na kahulugan. Nagbibigay ng bokabularyo na ginagamit sa buong kurso sa pagkukumpara ng performance ng algorithm.

Aralin 1 • Mga Elementary Comparison Sort

Sinasaklaw ang bubble, selection, at insertion sort na may kumpletong pagsusuri ng kompleksidad. Itinatag ang baseline na intuwisyon bago ipakilala ang mas mahuhusay na pamamaraan.

Aralin 2 • Mga Divide-and-Conquer Sort

Itinuturo ang merge sort at quicksort gamit ang recursive decomposition. Ikinokonekta ang pagsusuri ng recurrence mula sa Kabanata 2 sa tunay na performance ng pag-aayos.

Aralin 3 • Pagpili ng Algorithm ng Pag-aayos

Pinagsasama ang lahat ng kaalaman sa pag-aayos sa isang balangkas ng desisyon. Itinatapat ng mga mag-aaral ang pagpili ng algorithm sa laki ng input, distribusyon ng datos, at mga limitasyon ng memorya.

Aralin 4 • Mga Algorithm ng Pag-aayos sa Linear-Time

Ipinapakita ang counting sort, radix sort, at bucket sort bilang mga pamamaraang hindi nagkokompara. Nililinaw ang mga kondisyon kung saan ang linear time ay makakamit.

Aralin 1 • Memoisasyon at Top-Down DP

Pinapalawak ang recursion gamit ang pagkakatala ng resulta upang alisin ang kalabisan ng komputasyon. Nagsisilbing tulay patungo sa susunod na kabanata tungkol sa buong dynamic programming.

Aralin 2 • Linear at Binary Search

Ikinukumpara ang sequential at divide-based na paghahanap sa nakaayos at hindi nakaayos na datos. Itinatag ang mga paunang kondisyon at garantiya sa kompleksidad ng bawat pamamaraan.

Aralin 3 • Estratehiya ng Divide and Conquer

Pina-pormal ang paradigm ng divide-conquer-combine nang higit pa sa pag-aayos. Inilalapat ito ng mga mag-aaral sa mga problema tulad ng maximum subarray at closest pair of points.

Aralin 4 • Mga Teknik ng Backtracking

Ipinapakilala ang sistematikong paghahanap na may pruning sa pamamagitan ng backtracking. Ikinokonekta ang mga recursive call tree sa constraint satisfaction at mga problemang kombinatorial.

Aralin 1 • Mga Pundamental ng Binary Tree

Tinutukoy ang terminolohiya ng puno, mga ugnayan ng node, at mga katangian ng istraktura. Ibinabatay ang lahat ng susunod na algorithm ng puno sa isang pinagsasaluhang bokabularyo at mental model.

Aralin 2 • Red-Black Trees at B-Trees

Sinasaklaw ang mga panuntunan ng red-black coloring at istraktura ng multi-way B-tree. Ikinokonekta ang mga ito sa mga use case ng database indexing at file system.

Aralin 3 • AVL Trees at Rotations

Ipinapakilala ang height-balanced AVL trees at ang apat na kaso ng rotation. Ang mga mag-aaral ay nag-iimplementa ng self-balancing para garantiyahan ang O(log n) na mga operasyon.

Aralin 4 • Mga Algorithm ng Tree Traversal

Sinasaklaw ang inorder, preorder, postorder, at level-order na mga traversal. Ikinokonekta ang pagpili ng traversal sa mga tiyak na kinakailangan ng output at mga downstream algorithm.

Aralin 1 • Paghahanap na Depth-First

Nag-iimplementa ng DFS nang recursive at iteratibo gamit ang discovery at finish time. Ikinokonekta ang DFS sa cycle detection, topological sort, at connected components.

Aralin 2 • Pag-uuri ayon sa Topolohikal

Kinukuha ang topological order mula sa DFS finish time at algorithm ni Kahn. Inilalapat ang pag-aayos sa mga problema ng dependency resolution at task scheduling.

Aralin 3 • Terminolohiya at mga Representasyon ng Graph

Tinutukoy ang mga vertex, edge, directed vs. undirected, at weighted na mga graph. Ikinukumpara ang mga representasyon ng adjacency matrix at adjacency list ayon sa espasyo at gastos ng access.

Aralin 4 • Paghahanap na Breadth-First

Nag-iimplementa ng BFS gamit ang isang queue at sinusuri ang O(V+E) nitong kompleksidad. Inilalapat ang BFS sa paghahanap ng shortest-path sa mga unweighted graph.

Aralin 1 • Mga Minimum na Spanning Tree: Kruskal

Bumubuo ng mga MST sa pamamagitan ng matakaw na pagdaragdag ng mga edge na may pinakamababang timbang gamit ang Union-Find. Sinusuri ang kawastuhan sa pamamagitan ng katangian ng cut at cycle ng mga MST.

Aralin 2 • Algorithm ng Shortest Path ni Dijkstra

Nag-iimplementa ng Dijkstra gamit ang isang min-heap priority queue na may O((V+E) log V) na kompleksidad. Sinasaklaw ang patunay ng kawastuhan sa pamamagitan ng invariant ng matakaw na relaxation.

Aralin 3 • Lahat ng Pares ng Pinakamaikling Landas

Nilulutas ang pinakamaikling landas sa pagitan ng bawat pares ng vertex gamit ang Floyd-Warshall. Sinusuri ang pormulasyon ng O(V³) dynamic programming at pagbabagong-tatag ng landas.

Aralin 4 • Mga Minimum na Spanning Tree: Prim

Pinalalago ang isang MST mula sa isang seed vertex gamit ang priority queue sa algorithm ni Prim. Ikinukumpara ang Prim sa Kruskal ayon sa densidad ng graph at kompleksidad ng implementasyon.

Aralin 1 • Mga Klasikong 1D DP na Problema

Nilulutas ang Fibonacci, climbing stairs, at coin change gamit ang mga 1D DP table. Binubuo ang intuwisyon sa pagpuno ng table bago sumulong sa 2D na mga pormulasyon.

Aralin 2 • DP sa mga Puno at Graph

Inilalapat ang DP sa mga istraktura ng puno at DAG para sa mga advanced na problema sa optimisasyon. Sinasaklaw ang tree DP para sa diameter, independent set, at DP sa mga landas ng DAG.

Aralin 3 • Mga Problema ng Knapsack at Subset

Nilulutas ang 0/1 knapsack, unbounded knapsack, at subset sum gamit ang mga DP table. Ikinokonekta ang mga ito sa mga problema ng paglalaan ng yaman at pagiging posible ng desisyon.

Aralin 4 • Mga Klasikong 2D DP na Problema

Pinapalawak ang DP sa mga table na may dalawang dimensyon para sa mga problema ng string at grid. Sinasaklaw ang edit distance, LCS, at pagbibilang ng landas ng grid na may kumpletong derivasyon ng recurrence.

Aralin 5 • Optimisasyon ng Espasyo sa DP

Binabawasan ang espasyo ng DP table mula O(n²) patungong O(n) o O(1) gamit ang mga rolling array. Inilalapat ang optimisasyon ng espasyo sa knapsack, LCS, at edit distance.