DD772 알고리듬

2018년 봄학기
경기대학교 컴퓨터공학부

수업시간

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

강의실

  • Class A (1206): 종합 408호
  • Class B (1696): 종합 403호

평가

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

담당교수

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

공지사항

  • (6/5) 기말고사 결과 공개
  • (5/24) 쿠티스에서 교과목 설문조사 실시중입니다. 설문응답 여부는 참여도 점수에 반영됩니다. 6/7(목)까지 완료해주세요.
  • (5/24) 기말고사는 오픈북 형식으로 진행됩니다. 그리고 시험 중에 사용할 연습장(빈 종이)을 꼭 준비하세요.
  • (5/24) 기말고사는 6/4(월) 17:00 부터 8509호에서 실시합니다.
  • (5/24) Homework#4 게시. [14주]까지 제출
  • (4/26) Homework#3 게시. [11주]까지 제출
  • (4/17) 중간고사 결과 공개
  • (4/10) 중간고사는 오픈북 형식으로 진행됩니다. 그리고 시험 중에 사용할 연습장(빈 종이)을 꼭 준비하세요.
  • (4/4) 중간고사는 4/16(월) 17:00 부터 8509호에서 실시합니다.
  • (3/21) 쿠티스에서 교과목 설문조사 실시중입니다. 3/30(금)까지 완료해주세요.
  • (3/20) Homework #1은 [4주] 수업시간에 출력해서 제출해주세요.
  • (3/9) Homework #0은 제출하지 않으셔도 됩니다.
  • (2/26) 알고리듬 홈페이지가 개설되었습니다.
공지사항은 수시로 확인해주세요.

과제물

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

  • Homework#2: [6주] 까지
  • Homework#3: [11주] 까지
  • Homework #4: [14주] 까지
    아래 문제에 대해 적어도 두 가지 이상의 프로그래밍 언어로 프로그램을 작성하고, 각 프로그램이 1초 안에(CPU time 기준) 답을 내는 입력 크기의 최댓값을 분석하시오.
      1. 숙제문제 3-3
      2. 0/1-Knapsack 문제
      3. Longest Common Subsequence 문제
      4. Kruskal 알고리즘
      5. Prim 알고리즘

참고자료


일정

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

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




Managed by Sang Won Bae
Associate Professor
Division of Computer Science & Engineering, Kyonggi University
Suwon, Korea.