2024 fall

알고리즘 / Algorithms (3분반)

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

Instruction

Course Staff
Time & Location
  • 월/목요일 10:30 - 11:45, 공학 6호관 609호
Office Hours
  • 화요일 13:00 - 15:00
  • 주의 사항
    • 수업 및 과제 관련 내용은 면담 대신 e루리 질의 응답 게시판에 올려서 모든 학생이 공유할 수 있도록 할 것
    • 수업 및 과제 관련 내용을 제외한 면담이 필요시 미리 이메일로 연락하여 일정을 잡을 것
Textbook
  • [Ri 17] 알고리즘 기초, 5th Ed., Richard E. Neapolitan (도경구 역), 홍릉과학출판사
Prerequisite
  • (선택) 자료구조, 이산수학
Grading Policy
  • 중간시험: 45%
  • 기말시험: 45%
  • 출석: 10%
    • 지각 3회 = 결석 1회
    • 결석 1회에 출석 점수 1% 차감
    • 총 수업 일의 1/3 (10회) 초과 결석 시 F
      • 즉, 11회 이상 결석 시 F
    • 별도의 사유(예. 예비군 훈련 등)가 있을 시 수업 시간 전에 교수 및 조교에게 이메일 송부
      • 단, 급하게 벌어진 사유(예. 급병, 친족상 등)는 소명 자료를 제출

Schedule

W01: Overview / Efficiency, Analysis, Order
September 02: Course Overview & Logistics
September 05: Algorithm Description / Sequential Search vs. Binary Search
  • Lecture
  • Reference
    • [Ri 17] Chap. 1
W02: Efficiency, Analysis, Order
September 09: Fibonacci Numbers / Algorithm Analysis
  • Lecture
  • Reference
    • [Ri 17] Chap. 1
September 12: Order
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
W03: Divide & Conquer
September 16: Chuseok Holiday
  • No Class
September 19: Divide & Conquer? / Binary Search / Merge Sort
  • Lecture
  • Reference
    • [Ri 17] Appendix B
W04: Divide & Conquer
September 23: Solution of Recurrence Relation
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
September 26: Quick Sort
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
W05: Divide & Conquer
September 30: Matrix Multiplication / Asymptotic Complexity of Recurrence Relation / Considerations on Divide & Conquer
  • Lecture
  • Reference
    • [Ri 17] Chap. 2
October 03: National Foundation Day
  • No Class
W06: Dynamic Programming
October 07: Dynamic Programming Basics / Binomial Coefficient
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
October 10: Longest Common Subsequence / Matrix-Chain Multiplication
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
W07: Dynamic Programming
October 14: Minimum Edit Distance Problem / All-Pairs Shortest Path Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
October 17: Traveling Salesman Problem / Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 3
W08: Midterm Exam
October 21
  • No Class
October 24: Midterm Exam
W09: Greedy Algorithm
October 28: Midterm Exam Recitation
October 31: Greedy Algorithm Basics / Single-Source Shortest Path Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
W10: Greedy Algorithm
November 04: Prim's Minimum Spanning Tree
  • Lecture
  • Reference
  • [Ri 17] Chap. 4
November 07: Kruskal's Minimum Spanning Tree
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
W11: Greedy Algorithm / Backtracking
November 11: Huffman Code
  • Lecture
  • Reference
    • [Ri 17] Chap. 4
November 14: Backtracking Basics / n-Queen Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
W12: Backtracking
November 18: Monte Carlo Method / Graph Coloring
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
November 21: Knapsack Problem / Traveling Salesman Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 5
W13: Branch-and-Bound
November 25: Branch-and-Bound Basics / Knapsack Problem
  • Lecture
  • Reference
    • [Ri 17] Chap. 6
November 28: Traveling Salesman Problem / Abductive Inference
  • Lecture
  • Reference
    • [Ri 17] Chap. 6
W14: NP-Theory
December 02: NP Theory Basics
  • Lecture
  • Reference
    • [Ri 17] Chap. 9
December 05: NP Problems
  • Lecture
  • Reference
    • [Ri 17] Chap. 9
W15: Evolutionary Computation
December 09: Evolutionary Computation
  • Lecture
  • Reference
    • [Ri 17] Chap. 10
December 12: No Class
W16: Final Term Exam
December 16: Final Term Exam
December 19: Final Term Exam Recitation