Problem 1: https://blog.yexca.net/archives/198
Problem 2: https://blog.yexca.net/archives/201
Problem 3: This Article
Problem 4: https://blog.yexca.net/archives/202
Problem 5: https://blog.yexca.net/archives/203

Introduction

This problem set focuses on algorithms. Initially, it felt like a ‘give up’ moment. But after a walkthrough, the difficulty isn’t actually that high. It just needs a solid understanding of existing algorithms. My ’not too high’ assessment might be skewed by my initial fears of having to design some crazy new algorithm. (To be clear, I still wouldn’t call it easy.)

Problem copyright belongs to Tokyo University of Science. Quoted for convenience, non-profit use only.

1

We implemented two C functions to sort an integer array a with n elements in ascending order, each using a different algorithm. For Programs 3.1 and 3.2, pick the best algorithm name for captions A and B from the choices below, then give the corresponding symbol.

Choices

A. Selection Sort

B. Bubble Sort

C. Quick Sort

D. Insertion Sort

• Program 3.1: A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void sort_a(int a[], int n)
{
    int i, j, tmp;
    for(i=0; i<n-1; ++i){
        for(j=n-1; i<j; --j){
            if(a[j]<a[j-1]){
                tmp=a[j];
                a[j]=a[j-1];
                a[j-1]=tmp;
            }
        }
    }
}

• Program 3.2: B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void sort_b(int a[], int n)
{
    int i, j, tmp;
    for(j=1; j<n; ++j){
        tmp=a[j];
        i=j-1;
        while(0<=i && tmp<a[i]){
            a[i+1]=a[i];
            --i;
        }
        a[i+1]=tmp;
    }
}

Solution

This problem’s straightforward: identify the sorting algorithms from the code. Program A is Bubble Sort (B. バブルソート), and Program B is Insertion Sort (D. 挿入ソート).

2

Answer these questions about Heap Sort. Assume n is a positive integer.

a) For a binary heap, what condition must any non-root node’s value meet? (Either max-heap or min-heap condition is fine.)

b) If a binary heap holds n elements, what’s its height in terms of n? (Height is max path length from root to a leaf.)

c) For Heap Sort with n elements, pick the best asymptotic evaluation for both its average and worst-case time complexity from these options.

A. $O(1)$

B. $O(\log n)$

C. $O(n)$

D. $O(n\log n)$

E. $O(n^2)$

This one’s all about heap sort. Part one: what condition must non-root nodes satisfy in a binary heap (max-heap or min-heap, pick one). Part two: give the height of the heap’s binary tree. Part three: select the average and worst-case time complexities.

Solution

a

• Max-heap condition: Any non-root node’s value must be less than or equal to its parent’s value.
• Min-heap condition: Any non-root node’s value must be greater than or equal to its parent’s value.

b

c

Average and worst-case time complexity: D. $O(n\log n)$

3

Consider $A=\{ A[0], A[1], \cdots, A[n-1] \}$, an array of $n$ distinct integers. For non-negative integers $i,j < n$, if $i\lt j$ and $A[i]\gt A[j]$, we call $(i,j)$ an inversion of $A$. The total number of such inversions is $A$’s inversion count. For instance, in $\{ 5,7,4,6 \}$, inversions are $(0,2),(1,2),(1,3)$, so the inversion count is 3. Answer these questions.

a) What’s the inversion count for $\{ 1,0,4,3,2, \}$?

b) Given the set $\{ 1,2,\cdots,n \}$, what arrangement of its $n$ elements yields the maximum inversion count? Express this max count in terms of $n$.

c) Take any array B (of $n$ elements) from the set $\{ 1,2,\cdots,n \}$ and sort it ascending with Bubble Sort. We know ‘X in Bubble Sort equals array B’s inversion count’. What’s X, and why is this true? Keep it concise.

This problem kicks off with ‘inversions’ (Professor Song Hao’s Linear Algebra course covers this: video ). Part one: find the inversion count. Part two: find the maximum inversion count. Part three: identify what in Bubble Sort equals the inversion count, then explain why.

Solution

• a

Inversion count is 4: (1,0), (4,3), (4,2), (3,2).

• b

The maximum inversion count occurs when the permutation is

For n, there are n-1 inversions. For n-1, n-2 inversions. And so on. The total inversion count is their sum.

• c

X: Number of swaps

Reason: Each swap fixes exactly one inversion.

Bubble sort compares adjacent elements. If they’re out of order, it swaps them. Each swap eliminates one inversion.

4

Program 3.3 shows a C implementation of Merge Sort to sort an integer array ascending. Answer these questions.

• Program 3.3: Merge Sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int mergesort(int a[], int begin, int end, int w[]){
    int mid = (begin+end)/2;
    int i = begin, j = mid+1, k, c=0;
    
    printf("(%d, %d)\n", begin, end);
    if(begin<end){
        mergesort(a, begin, mid, w);
        mergesort(a, mid+1, end, w);
        
        for(k=begin; k<=end; ++k){
            if(mid<1){
                A
            }else if(end<j){
                B
            }else{
                /* ++c */
                if(a[i]<a[j]){
                    C
                }else{
                    D
                }
            }
        }
        for(k=begin; k<=end; ++k){
            E
        }
    }
    return 0;
}

a) Fill in blanks A, B, C, D, E with the correct code from the options to complete the program. a is the array to sort, w is the temp working array. mergesort is called like this:

1
2

int a[5] = {3, 5, 1, 4, 2}, w[5];
mergesort(a, 0, 4, w);

• Choices

b) With the mergesort call from (a), (0,4) prints on stdout’s first line. What prints on lines 3, 5, and 7, respectively?

c) We want to count total element comparisons (line 18 in Program 3.3) for mergesort to sort its range. We uncommented line 17 and changed it to ++c;, but that’s not enough. How do we modify Program 3.3 to store the comparison count in count using these two lines?

1
2

int a[5] = {3, 5, 1, 4, 2}, w[5];
int count = mergesort(a, 0, 4, w);

No global or static variables. Besides the line 17 change, you’re limited to 3 line replacements. A ‘replacement’ means swapping a line’s code with new code (60 chars max, no spaces). Your answer should follow the ‘Example Answer Format’ below: show the line number and the new code. Assume line 17 is already uncommented; detail other needed changes.

• “Example Answer Format”

6行目：printf("hello\n");

30行目：c= end - begin + 1;

Solution

a

• A: w[k] = a[j++]; i.e., セ
• B: w[k] = a[i++]; i.e., サ
• C: w[k] = a[i++]; i.e., サ
• D: w[k] = a[j++]; i.e., セ
• E: a[k] = w[k]; i.e., キ

b

• Line 3: (0,1)

• Line 5: (1,1)

• Line 7: (3,4)

c

• Line 8: c += mergesort(a, begin, mid, w);

• Line 9: c += mergesort(a, mid + 1, end, w);

• Line 31: return c;

This problem looked scary at first, but after a closer read, the concepts aren’t too bad. If you get merge sort, it’s pretty solvable. BTW, I’d mostly forgotten my algorithms, usually picking them up via animations (super intuitive). So, I was glad to stumble upon a cool animated algorithm site while tackling this.