# Category: alg

The thought processes involved in(i) formulating a problem and(ii) expressing its solutions in such a way that a computer --human or machine- can...

어떻게 하면 주어진 복잡한 문제를 이진수 형태의 낮은 수준의 명령어만 이해하는 ‘단순한’ 컴퓨터 상에서 효율적으로 해결할 수 있을까?

for given two functions f(n) and g(n) ,

최대 부분 수열의 합 Maximum Subsequence Sum

= max sum submatrix

[Priority Queue 1: Max(Min) Heap]

ref. [Horowitz 5.6.2] [Neapolitan 7.6]

Representation

Problem

A sorting algorithm is said to be stable if two items with equal keys appear in the same order in sorted output as they appear in the input array to...

Problem: Sort n keys in nondecreasing sequence.

Pivot strategy

Insertion Sort: Example 1

T(n) = O(n^2)

image

Selection

Problem - Find both the maximum and the minimum elements of a set containing n elements (assume n = 2m

ref. [A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1974. 3.6]

Theorem

[Neapolitan 2.8]

[J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005. 5.4]

Divide-and-Conquer Techniques and Sorting Techniques

NOW

T(i,j) = T(i-1,j) + T(i, j-1) + C \cdot (2i + j) for i,j \geq 1

Top-down → Bottom-up

C_{ij} = the cost of the shortest path from (0,0) to (i,j)

[T. Cormen et al., Introduction to Algorithms (3rd ed.), The MIT Press, 2009. 16.3]

Problem

Problem

Problem

Data compression

Divide-and-Conquer Method

No codeword can be a prefix of any other code.

Idea

Problem

Problem

Let J = {1, 2, ..., n} be a set of jobs to be served by a single processor.

Let J = \{1, 2, ..., n\} be a set of jobs to be served.

ref

Definitions and representations

Cycle detection

In general, the cost(weight) may be negative, but there must not exist a negative cycle in the graph.

Tree

ref. Courtesy of T. Cormen et al.

dijstra@datascience