Desperate Undergraduate!Desperate Undergraduate!

알고리즘 앞반 퀴즈
A에서 J도시까지 최소비용경로 구하기.

알고리즘 뒷반 퀴즈
배낭채우기 문제.

Algorithm, Spring 2011

Course Description and Goals
본 과목은 컴퓨터공학에서 다루는 문제들을 해결하기 위한 가장 기본적이며 중요한 원칙들과 해결기법 및 전략에 대해서 강의한다. 컴퓨터공학부 3학년이 수강대상이며, 이에 준하는 수준에서 강의를 진행한다.

컴퓨터공학의 다양한 문제해결을 위한 전략을 설계하고 분석하는 것을 주요 강의 내용으로 다루며, 수강생들이 이를 효과적으로 습득하기 위해서 선수과목으로 프로그래밍 관련 과목과 데이터구조 분석/설계를 필히 이수하고 수강하여야 한다. 선수과목에서 다루어진 내용에 대해서는 강의를 생략할 예정이며, 선수과목을 미이수한 학생들은 수강신청 시 유의하여야 한다.

본 과목의 목표는 학생들이 한 학기 알고리즘을 수강한 후, 이후 직면할 수 있는 다양한 컴퓨터공학의 문제들을 효과적으로 해결할 수 있는 컴퓨터공학적 사고를 할수 있도록 하는 것이며, 주어진 문제에 대해서 가장 효과적인 접근방식 및 전략 (Approach and Strategy)를 설계하고, 제안한 알고리즘에 대한 수학적 분석을 통해 그 우월성을 입증할 수 있는 능력을 배양하게 된다.

본 과목에 대한 컴퓨터공학심화 프로그램 교과목 학습성과 구성은 다음과 같음: 학습성과-1(20%), 학습성과-2(30%), 학습성과-3(30%), 학습성과-4(20%)

Course Procedures and Evaluation
강의는 지도교수에 의한 이론강의를 중심으로 하며, 학생들의 수업참여도를 높이기 위한 질의응답, 토론을 적극 활용한다. 학생들은 제시된 교재의 심화된 내용을 반드시 스스로 학습하여 자신만의 알고리즘 설계 및 분석 능력을 습득할 수 있어야 한다.

또한, 학습한 내용에 대한 적극적인 습득을 위해 정기적인 숙제 및 퀴즈를 실시한다. 숙제는 워드프로세서를 사용하지 않고, 자신만의 유일한 예제를 만들고 연필을 이용하여 손으로 직접 풀어서 제출한다.

평가는 중간고사, 기말고사, PreTest, 퀴즈 및 숙제 점수를 반영하여 최종 성적을 산출함.
1. 중간고사는 30점 만점으로 실시함.
2. 기말고사는 30점 만점으로 실시함.
3. PreTest는 10점 만점으로 실시함 (2회:5점/회).
4. 퀴즈 및 숙제는 30점 만점으로 실시함 (퀴즈 2회:4점/회, 숙제 22회:1점/회)

Reference Textbooks
1. Foundations of Algorithms Using C++ Pseudocode by R. Neapolitan et al., Addison Wesley.
3. Introduction to Algorithms by T.H. Cormen et al., MIT Press.

Lecture Schedule and Homeworks
WEEK 1: Introduction and Design & Analysis of Algorithm
WEEK 2: Divide and Conquer (Binary Search and Merge Sort)
WEEK 3: Divide and Conquer (Quick Sort), Dynamic Programming (Binomial Coefficient)
WEEK 4: Dynamic Programming (Bionomial Coefficient, All-Pairs SP)
WEEK 5: Dynamic Programmin (All-Pairs SP, Chained Matrix Multiplication)
WEEK 6: Dynamic Programming (CMM) and Greedy (Minimum Spanning Trees)
WEEK 7: Greedy (Minimum Spanning Trees) and Pre-Test
WEEK 8: Mid-Term Exam
WEEK 9: Dynamic Programming vs Greedy (The Knapsack Problem)
WEEK 10: Backtracking (N-Queens/ Sum-of-Subsets/ Graph Coloring Problem)
WEEK 11: Backtracking (TSP Problem, 0/1 Knapsack Problem)
WEEK 12: Branch and Bound (0/1 Knapsack Problem), Best-First Search
WEEK 13: Theory of NP (Decision Problem, Optimization Problem)
WEEK 14: Theory of NP (NP-Complete Problem)
WEEK 15: Theory of NP (NP-Hard Problem, Approximation Algorithm) and Pre-Test
WEEK 16: Final Exam

#include <stdio.h>
#include <stdlib.h>

int minimum(int i, int k)
{
	if(i < k) return i;
	else return k;
}

int bin2(int n, int k)
{
	// Valable Decaltion
	int i = 0;
	int j = 0;
	int **B = NULL;

	int returnValue = 0;
	
	// Matrix Initialization
	B = (int**)malloc(sizeof(int*) * (n+1));

	for(i = 0; i < n+1; i++)
		B[i] = (int*)malloc(sizeof(int) * (k+1));

	for(i = 0; i < n+1; i++)
		for(j = 0; j < k+1; j++)
			B[i][j] = 0;

	// Binomial Coefficient
	for(i = 0; i <= n; i++)
		for(j = 0; j <= minimum(i,k); j++)
			if(j == 0 || j == i)
				B[i][j] = 1;
			else
				B[i][j] = B[i-1][j-1] + B[i-1][j];

	returnValue = B[n][k];
	
	// Matrix Uninitialization
	for(i = 0; i < n+1; i++)
		free(B[i]);
	
	free(B);

	return returnValue;
}

int main(int argc, char argv[])
{
	printf("B[4][2] = %d\n", bin2(4,2));

	return 0;
}