2024 fall

Algorithms (3 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
  • 월/목요일 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: Traveling Salesman Problem / Knapsack 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