2025 fall

Algorithms (2 Div.)

This courses introduces fundamental concepts and theories to design and analyze computer algorithms that are widely employed in computer science. Throughout the courses, we will cover divide-and-conquer, dynamic programming, greedy algorithms, backtracking, branch-and-bound, genetic algorithms, and NP theory.

Instruction

Course Staff
Time & Location
  • Mon./Thu. 10:30 - 11:45, #609, College of Engineering #6
Office Hours
  • Tue. 13:00 - 15:00
Textbook
  • [Ri 17] Foundations of Algorithms, 5th Ed., Richard E. Neapolitan (도경구 역), 홍릉과학출판사
Prerequisite
  • Data Structure
Grading Policy
Exam (70%)
  • Midterm Exam (30%)
  • Final Exam (40%)
Rank at the Online Judge (20%)
  • Baekjoon Online Judge
    • Silver 2 or higher: 20%
    • Silver 3: 18%
    • Silver 4: 16%
    • Silver 5: 14%
    • Bronze 1: 10%
    • Bronze 2: 8%
    • Bronze 3: 6%
    • Bronze 4: 4%
    • Bronze 5: 2%
    • Unrated or unregistered: 0%
Attendance (10%)
  • 1% of credit is deducted for each absence
  • 3-Lateness = 1-Absence
  • At least 11-Absence = F grade

Schedule

Week 01
September 01 — Course Overview & Logistics
September 04 — Efficiency, Analysis, Order: Algorithm Description & Sequential Search vs. Binary Search
  • Lecture
  • Reference
    • [Ri 17] Chap. 1
Week 02
September 08 — Efficiency, Analysis, Order: Fibonacci Numbers & Algorithm Analysis
  • Lecture
  • Reference
    • [Ri 17] Chap. 1
September 11 — Efficiency, Analysis, Order: Order
  • Lecture
  • Reference
    • [Ri 17] Chap. 1
Week 03
September 15 — Divide & Conquer: Binary Search & Merge Sort
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
September 18:
Week 04
September 22 — Divide & Conquer: Solution of Recurrence Relation
  • Lecture
  • Reference
    • [Ri 17] Appendix B
September 25 — Divide & Conquer: Quick Sort
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
Week 05
September 29 — Divide & Conquer: Matrix Multiplication & Asymptotic Complexity of Recurrence Relation
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
October 02 — Dynamic Programming: Binomial Coefficient
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
Week 06
October 06 — Chuseok Holiday
  • No Class
October 09 — Hangul day
  • No Class
Week 07
October 13 — Dynamic Programming: Longest Common Subsequence & Matrix-Chain Multiplication
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
October 16 — Dynamic Programming: Minimum Edit Distance Problem & All-Pairs Shortest Path Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
Week 08
October 20
  • No Class
October 23 — Midterm Exam
Week 09
October 27 — Midterm Exam Recitation
October 30 — Dynamic Programming: Traveling Salesman Problem & Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
Week 10
November 03 — Greedy Algorithm: Single-Source Shortest Path Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
November 06 — Greedy Algorithm: Prim's Minimum Spanning Tree
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
Week 11
November 10 — Greedy Algorithm: Kruskal's Minimum Spanning Tree
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
November 13 — Greedy Algorithm: Huffman Code
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
Week 12
November 17 — Backtracking: n-Queen Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
November 20 — Backtracking: Monte-Carlo Method & Graph Coloring
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
Week 13
November 24 — Backtracking: Traveling Salesman Problem & Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
November 27 — Branch-and-Bound: Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 6
Week 14
December 01 — Branch-and-Bound: Traveling Salesman Problem & Abductive Inference
  • Lecture
  • Reference
    • [Ri 17] Chap. 6
December 04 — NP Theory: Basics
  • Lecture
  • Reference
    • [Ri 17] Chap. 9
Week 15
December 08 — NP Theory: NP Problems
  • Lecture
  • Reference
    • [Ri 17] Chap. 9
December 11 — Evolutionary Computation
  • Lecture
  • Reference
    • [Ri 17] Chap. 10
Week 16
December 15 — Final Exam
December 18 — Final Exam Recitation & Final Remark