Algorithms and Practice (Spring Semester, 2020 – CPA341)

“Student-teacher relationships are based on trust. Acts, which violate this trust, undermine the educational process. Your classmates and the instructor will not tolerate violations of academic integrity.”

1. Course Schedule & Lecture Notes

• March 16 (Monday) – Introduction to Course
  • Course Guide
  • Practice
    • Java Programming with CLI
  • 대학보유 실험실 안전교육 콘텐츠 활용
    • 컴퓨터안전 및 생활안전
  • 온라인 컨텐츠 학습(1차시): 알고리즘의 정의와 필요성

• March 18 (Wednesday) – Algorithms: Efficiency, Analysis, and Order – I

  • 온라인 컨텐츠 학습(2차시): 알고리즘 설계와 분석의 기초
  • 온라인 컨텐츠 학습(3차시): 점화식과 점근적 복잡도 분석

• March 23 (Monday) – Algorithms: Efficiency, Analysis, and Order – II

  • 온라인 컨텐츠 학습(4차시): 수열 알고리즘
  • 온라인 컨텐츠 학습(5차시): 정렬 알고리즘의 개요 및 선택 정렬과 버블 정렬

  • Self Study 자료

    • Lecture Note_Ch01-1
    • Lecture Note_Ch01-2

  • Practice & HW-1

    • SearchMain.java
    • FibonacciMain.java
    • HW-1 (PDF) (Due Date: March 31 (Tuesday), 2020)

• March 25 (Wednesday) – Algorithms: Efficiency, Analysis, and Order – II

  • 온라인 컨텐츠 학습(6차시): 삽입 정렬, 병합 정렬, 셸 정렬
  • 온라인 컨텐츠 학습(7차시): 퀵 정렬, 힙 정렬, 트리 정렬

• March 30 (Monday) – Divide-and-Conquer – I

  • 온라인 컨텐츠 학습(8차시): 계수 정렬과 기수 정렬, 정렬 간 효율성 비교

  • Self Study 자료

    • Lecture Note_Ch01-3
    • Lecture Note_Ch02-1

• April 1 (Wednesday) – Divide-and-Conquer – II

  • 온라인 컨텐츠 학습: 병합(합병) 정렬, 퀵정렬 (EL에서 시청해야 출석 인정됩니다.)

    • MergeSort – Animation
    • QuickSort – Animation

  • Self Study 자료

    • Lecture Note_Ch02-2
    • Lecture Note_Ch02-3

  • Practice & HW-2

    • MergeSortMain.java
    • QuickAndMergeSortMain.java
    • HW-2 (PDF) (Due Date: April 12 (Sunday), 2020)

• April 6 (Monday) – Divide-and-Conquer – III

  • 온라인 컨텐츠 학습(9차시): 선택 알고리즘

• April 8 (Wednesday) – Divide-and-Conquer – IV

  • 온라인 컨텐츠 학습(10차시): 리스트, 스택, 큐

• April 13 (Monday) – Term Project 설명, Dynamic Programming – I

  • Lecture Note_Ch03-1
  • Practice
    • Binomial.java

• April 15 (Wednesday) – 21대 국회의원 선거

• April 20 (Monday) – Dynamic Programming – II

  • Lecture Note_Ch03-2
  • Practice
    • Floyd.java

• April 22 (Wednesday) – Dynamic Programming – III

  • Lecture Note_Ch03-3

• April 27 (Monday) – Dynamic Programming – IV

  • HW-1 & HW-2 채점 결과
  • 텀프로젝트 설명
  • HW-3 (Due Date: May 10, 2020)

• April 29 (Wednesday) – Dynamic Programming – V

  • Lecture Note_Ch03-4
  • 동적프로그래밍 TSP 참고 자료
    • 참고1
    • 참고2

• May 4 (Monday) – The Greedy Approach – I

  • Lecture Note_Ch04-1

• May 6 (Wednesday) – The Greedy Approach – II

• May 11 (Monday) – The Greedy Approach – III

• May 13 (Wednesday) – The Greedy Approach – IV

  • Lecture Note_Ch04-2
  • Practice
    • Dijkstra.java

• May 18 (Monday) – The Greedy Approach – V

  • Lecture Note_Ch04-3

• May 20 (Wednesday) – The Greedy Approach – VI

  • Lecture Note_Ch04-4
  • HW-4 (Due Date: May 31, 2020)

• May 25 (Monday) – The Greedy Approach – VII

• May 27 (Wednesday) – Backtracking – I

• June 1 (Monday) – Backtracking – II

• June 3 (Wednesday) – Branch-and-Bound – I

• June 8 (Monday) – Branch-and-Bound – II

• June 10 (Wednesday) – Branch-and-Bound – III

• June 15 (Monday) – Branch-and-Bound – IV

• June 17 (Wednesday) – Hash Algorithm

• June 22 (Monday) – 마지막 강의: Theory of P & NP (P.367~P.392)

• June 24 (Wednesday) – 기말고사 * 시험 장소 - 2공학관 312호, 313호

2. Reference

• 주교재: 도경구 역, Foundations of Algorithms Using Java Pseudocode, 사이텍미디어 (원저자: Richard Neapolitan and Kumarss Naimipour) Click
• 원서: Neapolitan, R. and Naimipour, K. (2004) Foundations of Algorithms using Java Pseudocode, Jones and Bartlett Publishers, Sudbury, Mass

3. Logistics

• Attendance – one class absence will result in the deduction of two points out of 100 points. Five absences will not result in ten points deduction, but “failure” (i.e., grade ‘F’) in this course.
• Exam – there will be midterm exam and final exam for the evaluation of the knowledge learned from the class.
• Homework – much intensive homework will be set. Any cheating (or copying) will result in grade ‘F’.

4. Evaluation

• Attendance (10%), Private Report(15%), Midterm exam (30%), Final exam (30%), Term Project (15%)