프로그래밍 숙제3을 진행하는 데 필요한 내용과 수강생들의 메일 질문에 대한 답변을 이 게시판에 업데이트 할 것 입니다.

 

자주 확인하셔야 불이익을 받지 않을 수 있습니다.

 

  • 채점 환경

Visual Studio 2017

  • 속도 최적화 컨테스트 시간 측정

-  실험 데이터: 조교는 2^25개의 원소를 가지는 배열을 실험 데이터로 사용할 것이다. 

  이 배열에 대해 세 번 시간 측정한 후 평균 값을 사용할 예정이다. (배열 데이터  2^25*2^5 = 1GB 상당의 메모리 소요)

- 실험 측정 PC는 최소 4GB의 RAM이 있다고 가정 (정확히  4GB일 수도 있음)

- QUICKSORT_OPT() 함수 구현 시 반드시 QUICKSORT에 기반을 두어야 함 (RADIX SORT와 같은 다른 방법은 허용 안함)
- 속도 향상을 위하여 key 값에 대한 (인덱스) 배열의 사용은 허용하나 최종적으로 입력 배열의 각 원소는 올바르게 정렬이 되어 있어야 함. 즉 모든 필드에 대하여 데이터 이동이 있어야 함

  • 제출 양식

HW3_S201*****(학번 8자리) 폴더 안에 프로젝트 폴더와 보고서를 넣은 후 zip으로 압축한다.

(프로젝트 폴더에서 Debug폴더와 Data Base File은 삭제한다.)

- 소스코드 파일명(총 6개): selection_rec.cpp / qsort.cpp / insertion_sort.cpp / heat_sort.cpp / quick_sort.cpp / quick_sort_opt.cpp

- 솔루션 파일명: HW3_S201***** 

- 데이터 파일명: (문제의 크기 n)_(random 또는 descending 또는 swaps)

                      n이 4096이고 Entirely random 특성을 가지고 있을 때, 파일명은 '4096_random'이다.

- 보고서 파일명: HW3_S201*****.{hwp, doc, txt}

- 최종 제출 파일: HW3_S201*****.zip

- 메일 제목: HW3_S201*****

- 제출 메일: 2017algorithm@gmail.com

  최종 제출 파일은 HW3_S201*****.zip입니다. 보고서를 따로 보내지 말아주세요.

 

  • 프로그램 데이터 파일의 위치

HW3_201*****.vcxproj가 있는 경로에 이름이 Data인 폴더 안에 데이터 파일들을 넣는다.  (입력 파일 최소 5개 이상)

 

  • 제출 기한

2017년 11월 26일 일요일 오후 11시 정각

- late 처리: 27일 월요일 오후 11시 정각 => 30% 감점

               28일 화요일 오후 11시 정각 => 70% 감점

               이후                               => 0점 처리

 

----------------------------------------------------------------------------------------------------------------------------------------

공지 업데이트

  • 11월 20일

int SELECTION_REC(ELEMENT data[], int left, int right, int k, int *index) 함수에서 k는 인덱스가 1부터 시작한다고 가정합니다.

HW3 프로젝트 파일(MAIN_SAMPLE)의 test_data_config.h을 보시면 테스트 데이터 배열에 오류가 있는데 다음과 같이 정정합니다.

int test_data_indices_selected[3] = { 16, 127, 923456 };  => int test_data_indices_selected[3] = { 15, 132, 575038 };

SELECTION_REC()함수가 제대로 작동하는지 여부도 채점 기준에 포함됩니다.

 

  • 11월 24일

각 함수들은 정상적으로 원하는 계산이 완료되었으면 1 값을 아니면 그 외의 값을 리턴해주어야 한다.

 

  • 11월 25일

원소 값을 이동시켜야 할 경우 반드시 memcpy()함수를 이용하여야 한다. 다른 방법 사용시 감점 대상이 됨.

 

 

프로젝트 관련 질문은 wxiz49@sogang.ac.kr로 메일 보내주시길 바랍니다.

댓글 0

번호 제목 글쓴이 날짜 조회 수
공지 알고리즘 설계와 분석 - 프로그래밍 숙제 4 (수정) grmanet 2017.12.16 298
» 알고리즘 설계와 분석 - 프로그래밍 숙제 3 (수정) grmanet 2017.11.10 484
공지 알고리즘 설계와 분석 - 프로그래밍 숙제 1 인풋 데이터 생성 (수정) grmanet 2017.10.10 282
공지 알고리즘 설계와 분석 - 프로그래밍 숙제 1 (수정) grmanet 2017.09.29 855
공지 2017년 2학기 알고리즘설계와분석 게시판입니다. grmanet 2017.08.28 358