Master in Data Science/Informatics 2 검색 결과
7 개의 검색 결과가 있습니다.
Master in Data Science/Informatics 2

[Algorithm/알고리즘] Divide and Conquer, Recurrences(분할정복, 점화식)

Divide and Conquer Divide problem into a number of subproblems Conquer subproblems by solving them recursively Combine solutions of the subproblem into solution for the original problem Merge Sort Divide: divide the sequence into two n/2 element sequences Conquer: sort the two sequences recursively using merge sort Combine: merge the two sorted sequences to produce the solution n>1일 때, T(n) = 2T..

2023. 4. 3. 01:53
Master in Data Science/Informatics 2

[Algorithm/알고리즘] Exercise 3: Algorithm Analysis(알고리즘 분석)

Task 1 Consider an array A with n distinct integers that are sorted in an ascending order and an integer t. a) The C funtion linear search traverses the integers in A, one after another, from the beginning. If t is found in A linear search returns 1, otherwise 0. Complete the C funtion linear search(int A[], int n, int t) in task1.c file. int linear_search(int A[], int n, int t) { for (int i=0; ..

2023. 4. 1. 06:50
Master in Data Science/Informatics 2

[Algorithm/알고리즘] Algorithm Analysis(알고리즘 분석)

Efficiency ▶ Predicting the resources that the algorithm requires - Resources in terms of time: running time - Resources in terms of space: memory usage ▶ Efficiency depends on input size ▶ Various ways of determining the size of input data - Depends on the problem being studied - Number of items in the input (e.g. sorting) - Total number of bits (e.g. integer arithmetic) ▶ Must have a model of ..

2023. 3. 28. 22:41
Master in Data Science/Informatics 2

[Algorithm/알고리즘] Exercise 2: Recursion(재귀)

Task 1 1.1. Analyse the algorithm RecursiveAlgo in the program WhatdoIdo. Explain what the algorithm does and what it returns if it is executed. 주어진 racecar로 알고리즘을 분석해보자. 처음 RecursiveAlgo(str, 0, 6)을 실행하면 str[0] = r, str[6] = r이므로 RecursiveAlgo(str, 1, 5)를 호출하게 된다. RecursiveAlgo(str, 1, 5)을 실행하면 str[1] = a, str[5] = a이므로 RecursiveAlgo(str, 2, 4)를 호출하게 된다. RecursiveAlgo(str, 2, 4)을 실행하면 str[2] = ..

2023. 3. 28. 16:40
Master in Data Science/Informatics 2

[Algorithm/알고리즘] Exercise 1: Sorting(정렬)

Task 1.1 Consider the Hilbert curves of order 1, 2 and 3 in Figure 1. Assume the canvas that is used for drawing the Hilbert curve is a 5cm x 5cm square. What is the length of the Hilbert curve of order 15? 먼저 규칙을 찾아보자. 빨간색으로 표시한 부분처럼, 각 단계를 H(n)이라 한다면, H(2)는 H(1)의 1/2 축소형이 4개가 반복되는데 3개의 링크가 있는 구조이고 H(3)는 H(2)의 1/2 축소형이 4개가 반복되는데 3개의 링크가 있는 구조이다. 그리고 링크는 1/2씩 줄어든다. H(2)의 링크는 5/2^2이고, H(3)의 링크는 5..

2023. 3. 27. 01:30
Master in Data Science/Informatics 2

[Algorithm/알고리즘] 정렬(Sorting)과 재귀(Recursion)

Some Observations on Sorting - Efficient management of space: in-place sorting - Efficiency is generally measured in terms of number of comparisons and/or number of exchange operations Methods of Sorting (1) Simple methods - Bubble sort - Selection sort - Insertion sort - Roughly n^2 comparisons (2) Fast methods - Merge sort - Heap sort - Quick sort - Roughly nlogn comparisons Bubble Sort 버블정렬 데..

2023. 3. 21. 21:15