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 — Divide & Conquer: Solution of Recurrence Relation
  • Lecture
  • Reference
    • [Ri 17] Appendix B
Week 04
September 22 — Divide & Conquer: Quick Sort
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
September 25 — Divide & Conquer: Matrix Multiplication & Asymptotic Complexity of Recurrence Relation
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
Week 05
September 29 — Dynamic Programming: Binomial Coefficient
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
October 02 — Dynamic Programming: Longest Common Subsequence & Matrix-Chain Multiplication
  • 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: Minimum Edit Distance Problem & All-Pairs Shortest Path Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
October 16 — Dynamic Programming: Traveling Salesman Problem & Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
Week 08
October 20 — Preparing for Midterm Exam
  • Q & A Session in class
October 23 — Midterm Exam
Week 09
October 27 — Midterm Exam Recitation
October 30 — Greedy Algorithm: Single-Source Shortest Path Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
Week 10
November 03 — Greedy Algorithm: Prim's Minimum Spanning Tree
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
November 06 — Greedy Algorithm: Kruskal's Minimum Spanning Tree
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
Week 11
November 10 — Greedy Algorithm: Huffman Code
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
November 13 — Backtracking: n-Queen Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
Week 12
November 17 — Backtracking: Monte-Carlo Method & Graph Coloring
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
November 20 — Backtracking: Traveling Salesman Problem & Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
Week 13
November 24 — Branch-and-Bound: Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 6
November 27 — Branch-and-Bound: Traveling Salesman Problem & Abductive Inference
  • Lecture
  • Reference
    • [Ri 17] Chap. 6
Week 14
December 01 — NP Theory: Basics
  • Lecture
  • Reference
    • [Ri 17] Chap. 9
December 04 — NP Theory: NP Problems
  • Lecture
  • Reference
    • [Ri 17] Chap. 9
Week 15
December 08 — Evolutionary Computation
  • Lecture
  • Reference
    • [Ri 17] Chap. 10
December 11 — Preparing for Midterm Exam
  • Q & A Session in class
Week 16
December 15 — Final Exam
December 18 — Final Exam Recitation & Final Remark