2018년 2학기 알고리즘 과제 #1

■ 과제내용 및 명세

▲ 문제 : Sorting Algorithm 구현 및 성능 분석

◦ 해당 알고리즘 : 8가지 (Insertion sort, Selection sort, Bubble sort, Quick sort(sequential

ver., recursive ver.), Merge sort(sequential ver., recursive ver.), Heap sort)

◦ 구현 : 해당 알고리즘들을 직접 구현 (「명세」부분에서 설명)

- 사용가능 언어 : C, C++

◦ 성능 분석 : 임의의 입력 data에 대한 해당 알고리즘들의 성능에 대한 가설을 수립한 후,

실험을 통해 가설을 검증 (「명세」부분에서 설명)

▲ 명세(Specification)

◦ 입력 : integer나 character의 배열이 기록되어 있는 real data 및 random data 파일 명

- real data : 실세계에 존재하는 data (예 : DNA나 protein, text, 전화번호부 등등)

- random data : 임의로 직접 작성한 data

- 예 : 입력 파일의 형태

◦ 출력 : 해당 입력이 오름차순으로 정렬된 결과를 별도의 파일에 출력

- 예 : 출력 파일의 형태

◦ 가설과 검증

- 가설 : 특정 data에 대한 알고리즘들의 성능에 대한 가설을 세우고 그 근거를 설명

․ 작성 예 :

◦ 가설 1 : 특정 data A에 대해서는 나머지 알고리즘들에 비해 알고리즘 B, C, D가

뛰어난 성능을 보일 것이다.

- data A와 알고리즘들의 특성 등에 기반을 두어 가설에 대한 근거를 기술

- 기타 기술

◦ 입력 data 1 : 특정 data A에 대한 기술

- data A의 획득 방법 기술 (real data : 출처 등, random data : 생성 방법 등)

- data A의 특성 기술 (data의 크기, 문자 집합의 크기, 기타 등등)

- 기타 기술

- 검증 : data에 대한 알고리즘들의 실제 성능 비교를 통한 가설의 평가

․ 성능 비교 방법 : sorting에 소요되는 수행 시간 측정 및 비교

․ 작성 예 :

◦ 검증 1 : 입력 data 1에 대해 알고리즘들의 실제 성능을 비교한 결과

- 실험 결과를 기술

- 가설 1과의 일치 여부 기술

․ 불일치의 경우에는 그 이유에 대한 추정이나 분석 등을 함께 기술

- 기타 기술

◦ 평가기준

평가항목	평가내용	설명
1	구현	◦ 8가지 알고리즘을 모두 구현해야 합니다. ◦「명세」의 입력과 출력을 준수해야 합니다.
2	data의 선별	◦ 가설과 검증에 사용될 data를 직접 선택해야 합니다. - random data보다 real data를 선택한 경우에 높은 점수를 줍니다. - 선택한 data의 크기가 클수록 높은 점수를 줍니다. - 선택한 data에 대한 특성을 명확하게 기술할 경우, 좋은 점수를 줍니다.
3	가설과 검증의 타당성	◦ 3가지 data에 대한 3가지 가설과 검증을 각각 수행해야 합니다. - 가설이 항상 검증과 일치할 필요는 없습니다. (다시 말해, 검증 후 가설을 수정하실 필요는 없습니다.) - 가설과 검증의 수행이 단순히 trivial한 것이 아니라 의미나 가치가 있는 경우, 높은 점수를 줍니다. ◦ 검증에 사용된 실험 결과를 보여야 합니다.

■ 과제제출

▲ 제출기한 : 2018년 10월 31일 (수)

※ 2018년 10월 31일(수) 자정까지 수신된 메일만 인정합니다.

▲ 제출해야 하는 결과물 : source, document, data

1. source :「명세」를 만족하는 8가지 알고리즘들의 source code 및 기초적 수행결과

2. document : data의 선별 과정과 3가지 가설, 실험을 통한 검증 결과 등을 상세하게 기술

3. data : 가설과 검증에 사용된 3가지 data

※ data의 크기 문제로 제출이 불가능하다고 판단될 경우, 별도의 공간에 upload한 뒤

document에 해당 data의 address를 표시해 주시기 바랍니다.

▲ 제출방법 :

1. 자신의 학번으로 새 폴더를 생성

2. source와 document, data를 폴더에 넣은 후, 폴더 자체를 압축 (virus check 권장)

3. e-mail 과제 제출

· 메일 주소 : algo.hyu@gmail.com

· 메일 제목 : 2014002572_홍길동_1차과제

■ 주의사항

▲「명세」의 입․출력 형식을 반드시 준수하시기 바랍니다.

▲ 해당 source를 구현한 환경을 명시해주시기 바랍니다, windows visual studio 2015 이상      추천합니다.

▲ 알고리즘들의 구현 중 참조한 source가 있을 경우 document에 그 출처와 참조 정도를

반드시 언급해 주시기 바랍니다.

담당조교 : FTC 1107호 임베디드보안연구실 심호재 (algo.hyu@gmail.com)

문의사항은 조교 메일로 보내주시기 바랍니다.