ThailandOI

Appearance

On this page

Last updated:

ค่าย ตุลา 65 ​

1. ลิงก์รวม ​

2. Proof techniques & running time analysis ​

คลิปจากผู้สอน ​

  1. Proof techniques https://www.youtube.com/watch?v=OuGm1WFaFFk
  2. Induction & Running time analysis https://www.youtube.com/watch?v=s5nRk6Na9JU

คลิปและเอกสารเพิ่มเติม ​

คลิปจากปี 2564 วิเคราะห์อัลกอริทึม: Part 1: Motivation https://www.youtube.com/watch?v=CYAOsuR73xc Part 2: นิยามของ big O และคุณสมบัติ https://www.youtube.com/watch?v=Qfeq096kB6I Part 3: ตัวอย่าง selection,insertion,bubble sorts/merge lists,แนวคิด "progress" https://www.youtube.com/watch?v=OFn-Ewi7EVA
Part 4: Binary search & lower bound for comparison-based sorting https://www.youtube.com/watch?v=ZN9L2QKD-cE
Part 5: Heapsort, Heaps, Priority queues https://www.youtube.com/watch?v=X2CxwUl6DHA
Part 6: Quicksort, Quickselect, Median, Linear-time sorting algorithm https://www.youtube.com/watch?v=LuYGgOaMSbY

เอกสารจากปี 2564: https://gitlab.com/jittat/ioi-training-notes/-/tree/master/64/running-times

3. Combinatorics ​

เอกสารและคลิปดูจากลิงก์รวม

4. Trees & Hash ​

คลิปของปี 2564 และอื่น ๆ (สอนไม่ค่อยเหมือนกัน ปีที่แล้วสั้นกว่า)

  • เรื่อง segment tree + fenwick tree ครับ https://www.youtube.com/playlist?list=PLW3DcQsnGanOVkucb-HNeZro6rG2_B6fV
  • เรื่อง Binary Tree กับ AVL Tree มันมีแบบยาว ๆ อยู่ครับ มี playlist ให้อีกอัน เลือกดูเฉพาะบางหัวข้อที่พิมพ์ไว้ให้ครับ ให้ดูจาก playlist https://www.youtube.com/playlist?list=PLW3DcQsnGanPGhY2Y0A9hc45KnfS55RZI โดยดูเฉพาะ video ต่อไปนี้พอครับ Data Structure 8-x: การเขียนคลาสแบบ Template Data Structure 15-x: Binary Tree Data Structure 16-x: Binary Search Tree (อันนี้ไม่ได้สอนในห้อง ไม่ต้องดูก็ได้ครับถ้าเข้าใจเรื่อง Binary Search Tree อยู่แล้ว) Data Structure 17-x: AVL Tree
  • เรื่อง Hash ไม่ได้สอนในห้อง ใครอยากดูก็ดูในนี้ครับ (อยู่ใน playlist เดียวกันกับข้างบนครับ) Data Structure 18-x: Hash Table

5. Graph algorithms ​

  1. ส่วนเนื้อหาพื้นฐาน (หลายส่วนถ้ารู้แล้วเรียนแบบผ่าน ๆ ได้): เอกสาร:

คลิป:

  1. ส่วนทฤษฎีกราฟ (ส่วนที่จำเป็นจะเน้นตัวหนาขีดเส้นใต้ - ส่วนอื่นกดข้ามได้)

#1 - Intro, degree, hand shaking lemma, intro graphic sequence | https://www.twitch.tv/videos/573404892?collection=N1qY26g1-xXe7w&filter=collections&sort=time

#2 - Graphic sequence proof #1 | https://www.twitch.tv/videos/573406519?collection=N1qY26g1-xXe7w&filter=collections&sort=time

#3 - พิสูจน์ graphic sequence | https://www.twitch.tv/videos/573406724?collection=N1qY26g1-xXe7w&filter=collections&sort=time

#4 - Connectivity, trees, DAG | https://www.twitch.tv/videos/573407328?collection=N1qY26g1-xXe7w&filter=collections&sort=time

#5 - พิสูจน์ว่าใน DAG จะมีจุดยอดที่ indegree = 0, แนะนำ tournament | https://www.twitch.tv/videos/573407646?collection=N1qY26g1-xXe7w&filter=collections&sort=time

#6 - พิสูจน์ว่าใน tournament จะมี king | https://www.twitch.tv/videos/573407934?collection=N1qY26g1-xXe7w&filter=collections&sort=time

#7 - Strongly connected component (1) | https://www.twitch.tv/videos/574139539?collection=N1qY26g1-xXe7w&filter=collections&sort=time

#8 - SCC (2), DFS trees, Topological order with DFS, หา Stronly connected component | https://www.twitch.tv/videos/574139826?collection=N1qY26g1-xXe7w&filter=collections&sort=time

มีคลิปอื่น ๆ ในชุดอีก จะดูเล่นก็ได้

7. Dynamic Programming ​

video ทั้งหมดผมรวบรวมไว้ใน playlist นี้แล้วครับ https://www.youtube.com/watch?v=FD4ZD73lWJU&list=PLW3DcQsnGanO5hgRSPisCMuLUBpOkpbRv

ส่วนไฟล์ slide อยู่ที่ https://github.com/nattee/ioi-training-note

  • Algorithm Design 5-1: Intro to DP, Fibonacci Number
  • Algorithm Design 5-2: Fibonacci Number (bottom up)
  • Algorithm Design 5-3: Binomial Coefficient
  • Algorithm Design 5-4: Kadane's Algorithm
  • Algorithm Design 5-5: Matrix Chain Mulitiplication
  • Algorithm Design 5-6: Matrix Chain Mulitiplication (bottom up)
  • Algorithm Design 5-7: 01-Knapsack
  • Algorithm Design 5-8: 01-Knapsack (top down)
  • Algorithm Design 5-9: 01-Knapsack (bottom up)
  • Dynamic Programming 4: 2D DP: Largest Island Problem
  • Dynamic Programming 5: 2D DP: Longest Common Subsequence

8. Advanced Dynamic Programming ​

รวมโจทย์: https://docs.google.com/document/d/1np3frlJwnhaoyjKbgIYx07kT_fnAuM7DXxvesBBDMo8/edit?usp=sharing Slides: https://docs.google.com/presentation/u/1/d/1aqzU7uo3ii4kBRTrnt8DKyv7GhqyLHluzrAh_N9VrgY/edit

9. Shortest paths ​

คลิป: Playlist: https://www.youtube.com/watch?v=4dV3Pmksa_Q&list=PLii-CvAgf-8jsNIrv2sns761nT7z0awEV

มีเนื้อหาเพิ่มเติมสองชุดนะครับคือ คลิปเป็นภาษาอังกฤษ ลองฟังดูนะครับ ถ้าติดตรงไหนถามได้นะครับ วันจันทร์ถามได้ครับ ส่วนที่สองมีเนื้อหาด้านบนแล้วครับ

  1. เนื้อหา Floyd-Warshall:

ALL-PAIRS SHORTEST PATHS: Problem Definition https://www.youtube.com/watch?v=TENbWZPz3Ho&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=137

ALL-PAIRS SHORTEST PATHS: Optimal Substructure https://www.youtube.com/watch?v=ogcvCr02gqM&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=138

ALL-PAIRS SHORTEST PATHS: The Floyd Warshall Algorithm https://www.youtube.com/watch?v=3cBHwPjDZxg&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=139

  1. Johnson Algorithm (มีด้านบนแล้วด้วย)

ALL-PAIRS SHORTEST PATHS: A Reweighting Technique https://www.youtube.com/watch?v=DNRTlqPKK08&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=140

ALL-PAIRS SHORTEST PATHS: Johnson's Algorithm 1 https://www.youtube.com/watch?v=YJgISqFj9l8&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=141

ALL-PAIRS SHORTEST PATHS: Johnson's Algorithm 2 https://www.youtube.com/watch?v=47p0fWl166o&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=142