2019 년 가을 -ITCS-8114-Algods
이 저장소에는 "ITCS 6114/8114 : 알고리즘 및 데이터 구조" 의 프로젝트 및 할당이 포함되어 있습니다. 이 과정은 UNC Charlotte의 박사 학위의 일환으로 2019 년 가을 학기에 수강되었습니다.
프로젝트 목록
- 프로젝트 1 : 비교 기반 분류 알고리즘
- 프로젝트 2 : 그래프 알고리즘 (싱글 소스 최단 경로 및 최소 스패닝 트리)
- 프로젝트 3 : 패턴 일치 알고리즘
아래에는 프로젝트의 설명과 요구 사항이 있습니다. 세부 사항을 얻으려면 해당 프로젝트 디렉토리로 이동하십시오.
프로젝트 1 : 비교 기반 분류 알고리즘
다음 정렬 알고리즘을 구현하고 비교하십시오. 모든 프로그래밍 언어 (예 : C/C ++, Java, Python, C#)를 사용할 수 있습니다. 이 프로젝트에서는 혼자 또는 두 팀으로 일할 수 있습니다.
- 삽입 정렬
- 정렬을 병합하십시오
- Heapsort [벡터 기반 및 한 번에 하나의 항목을 삽입]]
- 내부 QuickSort (임의의 항목 또는 입력의 첫 번째 또는 마지막 항목은 피벗 될 수 있음).
- 수정 된 QuickSort
- 중앙값을 피벗으로 사용하십시오.
- 크기 <= 10의 작은 하위 문제의 경우 삽입 정렬을 사용하십시오.
실행 지침 :
- 이 알고리즘을 다양한 입력 크기로 실행하십시오 (예 : N = 1000, 2000, 4000, 5000, 10000 .. 40000, 50000). 입력 배열의 숫자를 무작위로 생성합니다. 실행 시간을 기록하고 (클래스에서 논의 된대로 평균을 취해야 함) 입력 크기에 대해 단일 그래프로 모두 표시하십시오. 동일한 데이터 세트의 이러한 정렬 알고리즘을 비교합니다.
- 또한 다음 두 가지 특별한 경우의 성능을 관찰하고 현재 성능을 관찰하십시오.
- 입력 배열은 이미 정렬되었습니다.
- 입력 배열은 역방향 정렬됩니다.
채점 계획 :
제출 지침 :
- 캔버스 업로드
- 선택된 데이터 구조, 복잡성 분석, 결과 및 코드를 다루는 잘 구성된 보고서.
- 실행을위한 프로그램 코드를 업로드하십시오. ta에 readme를 제공하십시오.
- 또한, 수업에서 나에게 코드가없는 보고서의 하드 카피.
프로젝트 2 : 그래프 알고리즘 (싱글 소스 최단 경로 및 최소 스패닝 트리)
이 프로젝트에서는 아래에 언급 된 두 개의 그래프 알고리즘을 구현합니다. 참고 : 혼자 또는 두 개의 최대 팀에서 일할 수 있습니다.
문제 1 : 주어진 소스 정점에 대한 방향 및 방향으로 가중치가 가중치로 가장 짧은 경로 트리를 찾으십시오. 그래프에 부정적인 가장자리가 없다고 가정하십시오. 주어진 소스의 각 경로 및 경로 비용을 인쇄합니다.
문제 2 : 연결된 무게가 가중 된 그래프가 주어지면 총 중량을 최소화하는 가장자리를 사용하여 스패닝 트리를 찾으십니까? (?) = ∑ (u, v) ∈ T ? (?,?). Kruskal 알고리즘을 사용하여 최소 스패닝 트리 (MST)를 찾으십시오. 당신은 나무의 가장자리와 답변의 총 비용을 인쇄합니다.
입력 형식 : 각 문제에 대해 텍스트 파일에서 입력됩니다. 다음의 변환 된 그래프에서 알고리즘을 실행하고 싶다고 가정 해 봅시다. 해당 파일 형식은 다음과 같습니다.
6 10 U
A B 1
A C 2
B C 1
B D 3
B E 2
C D 1
C E 2
D E 4
D F 3
E F 3
A
여기서 처음 두 숫자는 정점과 가장자리의 수를 나타냅니다. 문자 U는 방향이없는 그래프를 나타냅니다 (D 지시에 대한 D). 두 번째 줄에서 모든 가장자리와 무게 (예 : ???? (?)) 를 언급하고 무게는 1입니다. 마지막 줄은 선택 사항입니다. 주어진 경우 소스 노드를 나타냅니다.
제출 지침 :
- 각 알고리즘에 대한 간단한 설명, 선택한 데이터 구조, 코드 런타임, 샘플 입력/출력, 프로그램을 쉽게 실행하도록 지시하는 잘 알려진 보고서.
- 각 문제에 대해 선택한 네 가지 다른 그래프를 위해 프로그램을 실행하십시오. 당신의 판단을 사용하여 흥미롭고 합리적이라고 생각하는 테스트 그래프를 정의하십시오. 예를 들어:
- 방향 그래프 : 최소 7 개의 노드와 12 개의 모서리
- 지시 된 그래프 : 최소 7 개의 노드와 15 개의 모서리
- TA가 실행할 수있는 클린 코드.
- 모든 프로그래밍 언어 (예 : C/C ++, Java, Python 등)를 사용할 수 있습니다.
- 팀에서 일한 경우 두 멤버 모두 모든 것을 별도로 제출해야합니다.
- 저에게 직접 보고서의 하드 카피; 팀당 하나의 사본.
채점 계획 :
프로젝트 3 : 패턴 일치 알고리즘
참고 : 혼자 또는 Three Max 팀에서 일할 수 있습니다.
이 과제의 경우 아래 목록에서 선택한 3 가지 패턴 일치 알고리즘 만 구현합니다.
- Brute-Force 알고리즘
- Boyer-Mooore-Horspool 알고리즘
- Knuth-Morris-Pratt 알고리즘
- 보이어-무어 알고리즘
- 패턴 매칭을위한 유한 자동화
실험:
- 여러 입력 텍스트와 패턴에 대한 세 가지 알고리즘을 비교하십시오. 최소 10 개의 다른 사례
- 각 케이스에 대한 테이블에 필요한 비교 수를 언급하십시오. 각 알고리즘에 대해
제출:
- 각 알고리즘에 대한 간단한 설명, 사용 된 데이터 구조, 코드 런타임, 샘플 입력/출력, 프로그램을 쉽게 실행하도록 지시하는 잘 알려진 보고서.
- TA가 실행할 수있는 클린 코드.
- 모든 프로그래밍 언어 (예 : C/C ++, Java, Python 등)를 사용할 수 있습니다.
- 팀에서 일한 경우, 여전히 두 멤버 모두 별도로 모든 것을 제출해야합니다.
- 귀하의 보고서의 직접적으로 직접; 팀당 하나의 사본.
채점 계획 :
- 3 x 15 = 45 포인트 : 3 개의 알고리즘 구현
- 20 포인트 : 실험 용
- 10 점 : 보고서
