สอบข้อเขียน 5 วิชา
1. Probability and Randomized algorithm
มี vertex 1-n ให้มาทำ circle directed graph กราฟละกี่ vertex ก็ได้
ให้ pi เป็นฟังก์ชันสุ่มเลือกมา cycle นึง ถามว่าเฉลี่ยจะได้กราฟขนาดเท่าไร
2.Divide and conquer
มีฐานข้อมูล 2n จำนวน แบ่งเป็น 2 ชุด ชุดละ n ตัว ให้หา median ของข้อมูลขนาด 2n โดยกำหนดให้ query ฐานข้อมูลได้ โดยป้อนค่า k ลงไป จะคืนค่าเลขน้อยที่สุดลำดับ k มาให้ ให้เขียนอัลกอหา median โดยใช้ O(n) อีกข้อนึงให้เขียน O(nlogn)
3.Dynamic Programming
มีช้างตัวนึง กับกล้วยที่มีค่าไม่เท่ากัน ช้างต้องกระโดดกินกล้วยให้ได้มากที่สุด สมมติเก็บค่ากล้วยไว้ในอาร์เรย์ ช้างต้องชาร์จพลังก่อน1ช่อง ก่อนจะกระโดดไปกินกล้วยได้ กระโดดใช้เวลาช่องนึง ขาลงใช้เวลาอีกช่องนึง
|1.charge|2.jump|3.eat|4.down|
หมายความว่าช้างไม่สามารถกินกล้วยในช่อง 1–2 ได้ และทุกครั้งที่กระโดดลงมาจะกระโดดต่อเลยไม่ได้ต้องชาร์จก่อนอย่างน้อย 1 ช่อง
ซึ่งโจทย์ข้อนี้มีเงื่อนไขพิเศษว่าช้างสามารถอัดพลังพิเศษได้ โดดต่อได้เลย ต้องชาร์จไว้ก่อน ชาร์จไว้กี่ช่องก็สามารถกระโดดติดกันได้สูงสุดเท่านั้นช่อง แล้วค่าชาร์จก็ลดลงทุกครั้งที่กระโดดติดต่อกัน
ถามว่าจะกินกล้วยได้ค่ามากสุดเท่าไร
4.Machine Learning
- ให้ x1,x2,x3 มา ให้ Output มา ให้หา weight
- ให้ตาราง OR มา ให้เทรนค่า w0 w1 w2 ที่ให้มา 2 รอบที่เรต 0.5
- ให้หาจำนวน bit ที่เก็บเหตุการณ์ทั้งหมดที่ลูกเต๋าหน้า 1,3,5 มีโอกาสออกมากกว่าหน้า 2,4,6 เป็น 3 เท่า
5.Computational Theory
ให้ reduce SAT to Hamitonian Cycle
ps.เหมือนจะจำข้อ dynamic ตกไปข้อนึง นอกนั้นครบแล้ว
