# Algorithm

2학년 1학기까지 습득한 C/C++ 프로그래밍 능력과 자료구조 이론의 이해 및 구현 능력을 바탕으로, 컴퓨터를 통한 추상적인 문제의 효과적인 해결에 기초가 되는 알고리즘의 설계/분석/구현 기법을 익힘을 목표로 한다.

이를 위하여,

① 문제 분석/풀이 기법 도출/풀이 기법의 비용 분석 ß 주요 내용 ② C/C++ 언어를 통한 자신의 풀이 기법의 최적의 구현,
③ 자신의 소프트웨어 구현물에 대한 분석 과정에 대하여 익히도록 한다

# 컴퓨터공학 전공자로서 본 수업을 통하여 습득하려는 능력

이러한 능력을 습득하기 위하여 상당한 시간에 걸쳐 반복적인 노력이 필요함

• Algorithm에 대한 정의와 complexity와 computability 개념에 대한 이해
• Asymptotic analysis of time/space complexity 개념에 대한 이해
  • Worst-case versus average-case
  • Recursion 개념의 활용
• (Mathematical induction을 통한) algorithm correctness 증명 능력
• Dynamic set의 표현 및 응용 능력
• Priority queue 구조
• Disjoint set 구조
• Divide-and-conquer 기법에 대한 이해 및 응용 능력
• Sorting 방법에 대한 이해 및 구현 기법 습득
• Dynamic programming 기법에 대한 이해 및 응용 능력
• Greedy approach에 대한 이해 및 응용 능력
• Graph 구조 표현 기법 구현 및 관련 알고리즘 응용 능력
• Intractable Problem과 근사 알고리즘에 대한 이해 (희망 사항)

# 예상 진도 (2020학년도 2학기)

• W1: 9/1, 9/3 Introduction to Design and Analysis of Algorithm
• W2: 9/8, 9/10 Priority Queues and Applications (Review)
• W3: 9/15, 9/17 Practice of Complexity Analysis through Example Problems
• W4: 9/22, 9/24 Divide-and-Conquer Techniques
• W5: 9/29, 10/1추석 Divide-and-Conquer Techniques and Sorting
• W6: 10/6, 10/8 Dynamic Programming Techniques
• W7: 10/13, 10/15 Dynamic Programming and Applications
• W8: 10/19 ~ 10/23 정확한 시험 시간은 추후 공지 예정 MIDTERM
• W9: 10/27, 10/29 Greedy Techniques
• W10: 11/3, 11/5 Greedy Techniques and Scheduling Algorithms
• W11: 11/10, 11/12 Introduction to Graph Data Structures
• W12: 11/17, 11/19 Graph Algorithms and Applications I
• W13: 11/24, 11/26 Graph Algorithms and Applications II
• W14: 12/1, 12/3 Introduction to NP-Completeness
• W15: 12/8, 12/10 Intractable Problems and Approximation Algorithms 또는 진도 보충

# 교재 및 참고 도서

1. Neapolitan, Foundations of Algorithms (5th ed.), Jones & Bartlett, 2015.
2. Cormen et al., Introduction to Algorithms (3rd ed.), The MIT Press, 2009.
3. Roughgarden, Algorithms Illuminated, Part 1~3, Soundlikeyourself Publishing, 2018.
4. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.
5. Sedgewick and K. Wayne, Algorithms (4th ed.), Addison-Wesley, 2011.
6. Dasgupta et al., Algorithms, McGraw-Hill Education, 2006.
7. Baase and A. Van Gelder, Computer Algorithms: Introduction to Design and Analysis, Addison Wesley, 2000.
8. Horowitz et al., Fundamentals of Data Structures in C, Computer Science Press, 1993.
9. Skiena, The Algorithm Design Manual (2nd ed.), Springer, 2008.
10. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1974.
11. Weiss, Data Structure and Algorithm Analysis in C (2nd ed.), Pearson, 1997.
12. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003.
13. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983.
14. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms/C++, Computer Science Press, 1997.
15. Sedgewick, Algorithms in C: Parts 1-4 (3rd ed), Addison-Wesley, 1998.
16. Sedgewick, Algorithms in C: Parts 5 (3rd ed), Addison-Wesley, 2002.

8 적절한 교재를 선택하여 관련된 내용을 자세하게 읽기를 권장함

# 강의 자료 순서

[주제 1] Introduction to Algorithms and Complexity

[주제 2] Heap-based Priority Queues and Heap Sort (Review)

[주제 3] Divide-and-Conquer Techniques and Sorting Techniques

[주제 4] Dynamic Programming

[주제 5] Greedy Methods

[주제 6] Graph Algorithms

[주제 7] Intractable Problems and Approximation Algorithms

[주제 8] More on Priority Queues and Hashing

# 목표