DD772 알고리듬

2017년 봄학기
경기대학교 컴퓨터과학과

수업시간

  • Class A (1647): 목요일 123 (09:00-12:00)
  • Class B (1648): 금요일 123 (09:00-12:00)

강의실

  • Class A (1647): 종합 408호
  • Class B (1648): 종합 403호

평가

  • 출석: 20%
  • 중간고사: 30%
  • 기말고사: 30%
  • 과제물, 참여도 및 기타: 20%

담당교수

  • 배상원
  • 연구실: 8309
  • 전화: 9677
  • 홈페이지: 링크
  • 이메일:
  • 상담 환영

공지사항

  • (6/12) 기말고사에 대한 이의신청: 6/15일까지 이메일로 제목에 [학번, 이름, 문제번호]를 적을 것.
    확인 후 이메일로 답장 드립니다. 재검 후에 오히려 감점될 가능성도 있습니다.
  • (6/12) 기말고사 결과 공개
  • (5/29) 기말고사는 6월 8일(목) 17시부터 6405호(6강의동 4층)에서 실시합니다.
  • (5/29) 교과목 학기말 설문조사 실시 6월 10일까지. KUTIS에서...
    설문하지 않은 학생은 감점합니다.
  • (5/12) 안전교육이수를 반드시 하시고 이수증을 다음 수업시간까지 가지고 오세요. 성적에 반영합니다.
  • (5/12) 5월 18일 예비군 여러분들을 위한 보강은 종합강의동 406호에서 합니다.
  • (5/4) 금요일반(1648) 예비군 가시는 분들 보강은 5월 18일(목) 17시에 합니다. 장소는 추후 공지합니다.
  • (5/1) 금요일반(1648)은 5월 5일 수업 대신 5월 4일 (목) 17시 부터 수업합니다. 장소는 8001호입니다.
  • (5/1) 중간고사 결과 공개
공지사항은 수시로 확인해주세요.

과제물

  • Homework #0 : [2주] 까지

  • Homework #1 ([4주] 까지)
    다음을 해결하는 함수를 자신이 좋아하는 프로그래밍 언어로 반복문(while, for 등)을 사용하지 말고 작성하시오.
      1. n개의 수(정수 혹은 실수)의 총합을 계산하기
      2. insertion sort
      3. selection sort

  • Homework#2: [6주] 까지

  • Homework#3: [12주] 까지

  • Homework #4: [14주] 까지
    아래 문제에 대해 원하는 언어로 프로그램을 작성하고, 본인의 프로그램이 1초 안에(CPU time 기준) 답을 내는 입력 크기의 최댓값을 분석하시오.
      1. 숙제문제 2-2
      2. 숙제문제 2-3
      3. 숙제문제 3-1
      4. 숙제문제 3-2
      5. 0-1 Knapsack 문제
      6. LCS 문제
      7. Minimum Spanning Tree 문제

참고자료


일정

강의 문제/알고리듬/키워드 관련자료
1주 (3/2-3) 강의소개
2주 (3/9-10) Algorithm Analysis: Time Complexity Homework #0
Sorting Algorithms
[JM]의 Chapter 4
[CLRS]의 Chapter 2, 3
3주 (3/16-17) Big-Oh Notation
Recursion
Homework #1
4주 (3/23-24) Divide-and-Conquer Homework#2 [JM]의 Chapter 7
[CLRS]의 Chapter 4
[PoA]의 Chapter 7
5주 (3/30-31) Divide-and-Conquer Master Theorem
Karatsuba Algorithm
Strassen Algorithm
[JM]의 Chapter 7
[CLRS]의 Chapter 4
[PoA]의 Chapter 7
6주 (4/6-7) 문제풀이 Homework#2
7주 (4/13-14) 문제풀이 Homework#2
8주 (4/20-21) Algorithm Analysis: Correctness Proof Mathematical Induction [JM]의 Chapter 5
[CLRS]의 Chapter 2
[PoA]의 Chapter 2와 5
중간고사 (4/21 17:00~) 중간고사 (장소: 8509 5층 세미나실)
9주 (4/27-28) 휴강
10주 (5/4) 중간고사 리뷰
Dynamic Programming
0/1-Knapsack Problem
Homework#3
[JM]의 Chapter 8-9
[CLRS]의 Chapter 15
[PC]의 Chapter 11
[PoA]의 Chapter 8
강의노트 1, 강의노트 2
11주 (5/11-12) Dynamic Programming Matrix Product Chain
Longest Common Subsequence
[JM]의 Chapter 8-9
[CLRS]의 Chapter 15
[PC]의 Chapter 11
[PoA]의 Chapter 8
강의노트 3
12주 (5/18-19) 문제풀이 Homework#3
13주 (5/25-26) Greedy Method Coin Change
Activity Selection Problem
[JM]의 Chapter 10
[CLRS]의 Chapter 16
[PoA]의 Chapter 9
14주 (6/1-2) Graph Algorithms Minimum Spanning Tree
Kruskal's/Prim's Algorithm
Shortest Paths
[CLRS]의 Chapter 22-25
강의노트
15주 (6/8(목) 17:00~) 기말고사

일정은 변동될 수 있으며 변동될 경우 사전에 공지합니다.




Managed by Sang Won Bae
Associate Professor
Dept. Computer Science, Kyonggi University
Suwon, Korea.