Discrete Mathematics 2008 Project #1

 


 

  • 제출 마감일 : 5/12
  • 사용 언어: 제한 없음. (C,C++,JAVA ) 윈도우 XP상에서 단독으로 실행 가능한 실행파일을 제공해야  .
  • 제출 방법: e-mail 소스코드와 실행파일, 리포트를 묶어서 제출. 파일 이름은 학번_이름.zip. (:200412345_길동.zip). 이메일 제목에도 이름과 학번 표기
  • 소스코드의 부분에 대한 구현 설명 테스트 결과를 리포트에 첨부 (필수)

  • Project #1-1: zebra puzzle
  • Goals

1. zebra puzzle (연습문제 1.2.65) 풀기 위한 Boolean table 디자인한다.

2. 주어진 조건으로부터 Boolean table 업데이트하는 알고리즘을 구현한다. (: The Spaniard owns a dog)

3. 주어진 조건으로부터 Boolean table 대한 constraint 체크하는 알고리즘을 구현한다. (: The green house is immediately to the right of the white one)

4. 주어진 조건으로부터 자동적으로 zebra puzzle 푸는 algorithm 구현한다.

 

  • Project #1-2: deferred acceptance algorithm
  • Goals

1. 남자/여자의 s, 선호 리스트 Mi, Wi 입력받아 최종적으로 matched pair 출력하는 deferred acceptance algorithm 구현한다. (연습문제 3.1.59 참고)

2. 1 추가로 실행시의 time complexity 출력한다.

3. 남자/여자의 s, 시행 회수 n 입력받은 랜덤하게 Mi,Wi 정해 n번의 반복 시행 동안 Worst-case time complexity Average time complexity 계산해 출력한다.

4. 남자들의 선호 리스트 Mi 동일할 경우에 대해 3 구현한다.

5. 다양한 s 대해 3,4 실험해 보고 경우에 대해 실험적인 Worst-case time complexity, Average-case time complexity 비교 분석한다.

 


Bulletin Board