Queue: FIFO (First In First Out) ใช้ใน Graph Traversal (BFS) เป็นต้น ADT ซ่อนรายละเอียดการทำงานภายใน Queue ADT Operations isFull() – ตรวจสอบ Queue เต็ม isEmpty() – ตรวจสอบ Queue ว่าง enqueue(x) – ใส่ x ที่ท้าย Queue dequeue() – ลบจากหน้า Queue (Front) front() – ดูค่าหน้า Queue size() – จำนวนองค์ป

Step Count Method นับจำนวนครั้งที่แต่ละ Instruction ทำงาน เพื่อหา Time Complexity ตัวอย่าง: Sequential Search Algorithm Number of Times Cost seqSearch(arr, n, key)i := 0while i < n, do  if arr[i] = key, then    break  end ifdonereturn i 1n+1n0/11 c₁c₂

เงื่อนไขการคูณ เมทริกซ์ A (m×n) และ B (p×q) คูณได้ก็ต่อเมื่อ n = p ผลลัพธ์ C จะเป็น (m×q) อัลกอริทึม matrixMultiply(A, B): if n != p: exit define C(m, q) for i = 0 to m-1: for j = 0 to q-1: for k = 0 to p-1: C[i][j] += A[i][k] * B[k][j] ตัวอย่าง C++ #include <iostream&g

Amortized Analysis คืออะไร? ใช้เมื่อ การดำเนินการบางครั้งช้ามาก แต่ ส่วนใหญ่เร็ว ต้องการวิเคราะห์ต้นทุนเฉลี่ย ต้องใช้ใน Hash Tables, Disjoint Sets เป็นต้น Hash Table: Search/Insert ส่วนใหญ่ O(1) แต่เมื่อ Collision → O(n) สำหรับ Collision Resolution Aggregate Method หาต้นทุนรวม สำหรับ n การดำเนินก

5 การดำเนินการพื้นฐาน Traverse – สแกนทุกองค์ประกอบ Insertion – เพิ่มองค์ประกอบที่ตำแหน่งกำหนด Deletion – ลบองค์ประกอบ และอัปเดตตำแหน่ง Search – หาองค์ประกอบใน Array Update – อัปเดตค่าที่ตำแหน่งกำหนด ตัวอย่าง C++ (ใช้ Vector) #include <iostream> #include <vector> using namespace std;

2 วิธีการแทนค่า Array Representation Linked List Representation Array Representation เก็บข้อมูลแบบ Level Order (ทีละระดับ) ถ้าของขาดเว้นว่างไว้ 123456789101112131415 10516-81520-------23 Index 1 = Root, ลูกอยู่ Index 2, 3 สูตร: Child₁ = 2 × Parent Child₂ = 2 × Parent + 1 Parent = ⌊C

คุณสมบัติสำคัญของ Binary Tree จำนวนโหนดสูงสุดที่ระดับ l: $2^{l-1}$ (ระดับรูท = 1) จำนวนโหนดสูงสุดของต้นไม้ความสูง h: $2^{h} - 1$ (ความสูงของต้นไม้ 1 โหนด = 1) ความสูงต่ำสุดของ Binary Tree ที่มี n โหนด: $\log_{2}(n+1)$ (ถ้าความสูงใบ = 0 → $\log_{2}(n+1) - 1$) Binary Tree ที่มี L ใบ (Leaves): มีระ

สรุป 4 แบบ Traversal ใช้ BST ตัวอย่างเดียวกัน: Inorder (Left, Root, Right): 5 8 10 15 16 20 23 Preorder (Root, Left, Right): 10 5 8 16 15 20 23 Postorder (Left, Right, Root): 8 5 15 23 20 16 10 Level Order (BFS): 10 5 16 8 15 20 23 อัลกอริทึมทั้ง 4 แบบ inorderTraverse: left → root → right pr

Level-order Traversal (Breadth-First) เยี่ยมชมทีละระดับ (Level by Level) ใช้ Queue ลำดับ: 10, 5, 16, 8, 15, 20, 23 อัลกอริทึม levelOrderTraverse(root): define queue que insert root to que while que not empty: item := front of que print item value if left of item not null: inser

Post-order Traversal (Recursive) ลำดับ: Left → Right → Root ลำดับ: 8, 5, 15, 23, 20, 16, 10 อัลกอริทึม postorderTraverse(root): if root not empty: postorderTraversal(left of root) postorderTraversal(right of root) print root value โค้ด C++ และ Output // postorder_traversal: left →

Pre-order Traversal (Recursive) ลำดับ: Root → Left → Right ลำดับ: 10, 5, 8, 16, 15, 20, 23 อัลกอริทึม preorderTraverse(root): if root not empty: print root value preorderTraversal(left of root) preorderTraversal(right of root) โค้ด C++ และ Output // ใช้โครงสร้าง node, tree เดียวกั

คุณสมบัติของ BST ทุก BST เป็น Binary Tree Left Child มีค่า น้อยกว่า Root Right Child มีค่า มากกว่า Root BST ที่สมบูรณ์ไม่มีค่าซ้ำ ตัวอย่างต้นไม้ Inorder Traversal: 5, 8, 10, 15, 16, 20, 23 โค้ด C++ ตัวอย่าง #include <iostream> using namespace std; class node { public: int h_left, h_

กราฟ (Graph) โครงสร้างข้อมูลแบบ Non-linear ประกอบด้วย Nodes และ Edges ที่เชื่อมต่อ ขอบอาจเป็น Directed หรือ Undirected แทนได้เป็น G(V, E) เช่น G({A,B,C,D,E}, {(A,B), (B,D), (D,E), (B,C), (C,A)}) Breadth First Search (BFS) อัลกอริทึมเยี่ยมชมทุกโหนด เลือกโหนดหนึ่ง แล้วเยี่ยมเพื่อนบ้านทีละตัว จบเพื่

การประยุกต์ใช้ DFS (Depth First Search) ทำ DFS บน Unweighted Graph → สร้าง Minimum Spanning Tree และ All-Pairs Shortest Path Tree ตรวจจับ Cycle (Cycle Detection) – ถ้าเจอ Back-edge ระหว่าง DFS → มี Cycle หา Path ระหว่างสองโหนด u และ v Topological Sorting – จัดตารางงานจาก Dependency ใช้ DFS หา Stro

Spanning Tree Spanning Tree คือเซตย่อยของ Undirected Graph ที่มี ทุกโหนด (Vertices) เชื่อมต่อ โดยจำนวนขอบ (Edges) น้อยที่สุด ถ้าทุกโหนดในกราฟเชื่อมต่อกัน → มี Spanning Tree อย่างน้อย 1 ต้น ในกราฟหนึ่ง อาจมี Spanning Tree มากกว่า 1 ต้น Minimum Spanning Tree (MST) MST คือเซตย่อยของขอบใน Connected

นิยาม Bernoulli Distribution เป็น Discrete Distribution มี 2 ผลลัพธ์: x=0 (Failure), x=1 (Success) โอกาส Success = p, Failure = q = 1-p สูตร $$P(x) = \begin{cases} 1-p & \text{for } x = 0 \\ p & \text{for } x = 1 \end{cases}$$ หรือเขียนได้อีกแบบ: $$P(x) = p^{x} (1-p)^{1-x}$$ ตัวอย่าง C++ #include

นิยาม Binomial Distribution เป็น Discrete Probability Distribution Pₚ(n | N) ของการได้ n Success จาก N Bernoulli Trials (มี 2 ผลลัพธ์: x=0 Failure, x=1 Success โอกาส Success = p, Failure = q = 1-p) สูตร $$P_{p}(n|N) = \binom{N}{n} p^{n} (1-p)^{N-n}$$ ตัวอย่าง C++ #include <iostream> #includ

นิยาม Geometric Distribution เป็น Discrete Probability Distribution สำหรับ n = 0, 1, 2, ... มี Probability Density Function: $$P(n) = p(1-p)^{n}$$ Distribution Function: $$D(n) = \sum_{i=0}^{n} P(i) = 1 - q^{n+1}$$ ตัวอย่าง C++ #include <iostream> #include <random> using namespace s

นิยาม Negative Binomial Distribution เป็นการแจกแจงสุ่มที่สร้างจำนวนเต็มตาม Negative Binomial Discrete Distribution รู้จักในชื่อ Pascals Distribution สูตร $$P(i|k,p) = \binom{k+i-1}{i} p^{k} (1-p)^{i}$$ ตัวอย่าง C++ #include <iostream> #include <random> using namespace std; int main()

ปัญหา มีชุดจำนวนเต็มเรียงลำดับ และอาร์เรย์ freq (Frequency) ต้องสร้าง Binary Search Tree ที่ให้ ต้นทุนค้นหาต่ำสุด (Minimum Search Cost) วิธีแก้: Dynamic Programming สร้างอาร์เรย์ช่วย cost[n][n] เก็บคำตอบ Subproblems แบบ Bottom-up ตัวอย่าง Keys = {10, 12, 20} Frequency = {34, 8, 50} Output: Minim