SM3 New Generation 2006년식 리모컨키 배터리

우리집 서민 3호 리모컨키가 요즘 맛이 가고 있다. 배터리가 거의 닳은 듯하다.

인터넷 찾아보니 리모컨키 배터리가 CR1620 이라는 것이 다수설인듯. 대부분 배터리 교체 시기까지 폐차하지 않고 타는 경우가 없어서 다들 모르는 건가?

2006년식 SM3  New Generation 리모컨 키 배터리는 CR2032 를 사용하면 된다. 분해해서 확인했다. 아래는 증거 사진.

CR1620 아니에요... 마트갔다가 괜히 헛걸음만 했잖아... 쓸데없이 라면만 사오구... 살만 찌구...

CLRS Exercise 12.2-3

12.2-3
Write the TREE-PREDECESSOR procedure.

If a node x has a left child, its predecessor is the rightmost node of left sub-tree. Otherwise, the predecessor is the lowest ancestor of x whose right child is an ancestor of x.

TREE-PREDECESSOR(x)
        if x.left != NIL
                return TREE-MAXIMUM(x->left)
        p = x.p
        while p != NIL and x != p.right
                x = p
                p = p.p
        return p

CLRS Exercise 12.2-2

12.2-2
Write recursive versions of TREE-MINIMUM and TREE-MAXIMUM.

Recursive version of TREE-MINIMUM:

TREE-MINIMUM-RECURSIVE(x)
        if x.left == NIL
                return x
        return TREE-MINIMUM-RECURSIVE(x.left)

Recursive version of TREE-MAXIMUM:

TREE-MAXIMUM-RECURSIVE(x)
        if x.right == NIL
                return x
        return TREE-MAXIMUM-RECURSIVE(x.right)

CLRS Exercise 12.1-4

12.1-4
Give recursive algorithms that perform preorder and postorder tree walks in $\Theta(n)$ time on a tree of $n$ nodes.

Preorder traversal:

PREORDER-TREE-WALK(x)
        if (x != NIL)
                print x.key
                PREORDER-TREE-WALK(x.left)
                PREORDER-TREE-WALK(x.right)

Postorder traversal:

POSTORDER-TREE-WALK(x)
        if (x != NIL)
                PREORDER-TREE-WALK(x.left)
                PREORDER-TREE-WALK(x.right)
                print x.key

CLRS Exercise 12.1-3

12.1-3
Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)

Following code snippet is implementing the inorder traversal in recursive manner:

void inorder_tree_walk(struct node *t)
{
        if (t != NULL) {
                inorder_tree_walk(t->left);
                process(t);
                inorder_tree_walk(t->right);
        }
}

There are two recursive calls to inorder_tree_walk() and both can be eliminated. First, we can remove the second one at line 6 by using tail call elimination technique as following:

void inorder_tree_walk(struct node *t)
{
start:  if (t == NULL) goto end;
        inorder_tree_walk(t->left);
        process(t);
        t = t->right; goto start;
end:
}

The first call also can be removed by introducing a stack for storing the current context.

void inorder_tree_walk(struct node *t)
{
        stack<struct node *> s;
start:  if (t == NULL) goto pop;
        s.push(t); t = t.left; goto start;
pop:    if (s.empty()) goto end;
        t = s.pop();
        process(t);
        t = t->right; goto start;
end:
}

Now that the recursive calls are removed, code can be further simplified by removing dirty goto statements. The code between the first if statement and the first goto start is nothing more than a while loop. The label end can also be removed.

void inorder_tree_walk(struct node *t)
{
        stack<struct node *> s;
start:  while (t != NULL) {
                s.push(t);
                t = t.left;
        }
        if (!s.empty()) {
                t = s.pop();
                process(t);
                t = t->right;
                goto start;
        }
}

Looking at the overall flow of the program, the remaining goto statement can be converted into an outer while loop. Therefore, we finally get the following code:

void inorder_tree_walk(struct node *t)
{
        stack<struct node *> s;
        while (1) {
                while (t != NULL) {
                        s.push(t);
                        t = t.left;
                }

                if (s.empty()) break;

                t = s.pop();
                process(t);
                t = t->right;
        }
}

As mentioned in the problem statement, there exists another solution without using either stack or recursion. It is called as Morris inorder traversal, which uses the threaded binary tree.

void morris_inorder_walk_tree(struct node *t)
{
        while (t != NULL) {
                if (t->left == NULL) {
                        /* no more left child, process it and go right */
                        process(t);
                        t = t->right;
                } else {
                        /*
                         * before going to the left, make the right-most node
                         * of left child point to the current. Not only that,
                         * we should check if we already visited the left to
                         * prevent getting stuck in an infinite loop.
                         */
                        struct node *p = t->left;
                        while (p->right != NULL && p->right != t)
                                p = p->right;

                        if (p->right == NULL) {
                                p->right = t;
                                t = t->left;
                        } else {
                                /* restore the pointer back */
                                p->right = NULL;
                                process(t);
                                t = t->right;
                        }
                }
        }
}

CLRS Exercise 12.1-2

12.1-2
What is the difference between the binary-search-tree property and the min-heap property (see page 153)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in $O(n)$ time? Show how, or explain why not.

In the Min-Heap, both child nodes are less than or equal to their parents, while in the binary-search-tree, left child node cannot be greater than its parent and right child node cannot be less than. Thus, in-order traversal for BST gives nodes in sorted order with $\Theta(n)$ time complexity, but in the Min-Heap we need $n$ times of EXTRACT-MIN followed by HEAPIFY operations to get the same result, which takes $O(n\log{}n)$ time.

LN2410SBC

2004년쯤 거금을 들여 구입했으나, 서랍 구석 어딘가에서 먼지만 둘러 쓰고 있던 물건. 보드에 탑재된 S3C2410 가 아이들 장난감 수준의 물건으로 여겨질만큼 2012년 요즘 프로세서는 너무나 복잡해져버렸다. 덕분에, 어딘가 부족해 보이는 이 물건이 오히려 정겹다.

이 보드의 특징이라면 꽤 괜찮은 수준의 부트로더가 들어 있어서 특별한 장비 없이 USB로 손쉽게 바이너리를 올려보고 실행할 수 있었던 것으로 기억한다. 그래서, 조잡한 JTAG 동글로 flashing 하거나 느려터진 시리얼포트로 업로딩 해야했던 수고를 많이 덜 수 있다. 하지만, 회사에서 쓸 수 있던 TRACE32 에 비하면 여전히 불편했고, 또 집에까지와서 그걸 하고 앉아있어야 하겠느냐는 생각에 서랍 속으로 유배당할 수 밖에 없었던 물건. 그 사이 보드 제조사 (사이버랩 - 시랩시스) 는 우여곡절 끝에 아예 망해버려서 이제는 관련 자료 찾기도 어렵다. 하지만, 남아 있는 재고 물량을 도저히 떨이가격이라 볼 수 없는 수준의 가격으로 변치않는 자존심 자랑하시며 여전히 판매중인 물건 되시겠다. (차라리 beagleboard나 pandaboard 가 훨씬 나은 것 같다)

부트로더가 적혀있는 플래시의 data retention time 이 살짝 걱정되는 요즘에서야 다시 꺼내들었다. 무슨 바람이 불었는지, 얼마전 (약간 그 근본이 의심되는) TRACE32 를 중고로 구입하고 잉여력 발휘하여 JTAG 젠더까지 손수 만들어 붙이지 않았겠는가. 이게 얼마나 갈진 모르겠지만...

보드에 나와 있는 12핀 JTAG 포트의 pinout 은 TRACE32 의 그것과 많이 달라서, TRACE32 연결을 위해서는 별도로 변환 회로를 꾸며주어야 한다. 보드상에서 딱 기본적인 신호핀밖에 제공되지 않으므로 작업은 비교적 수월하다.

Lauterbach TRACE32 20핀 JTAG pinout

LN2410SBC JTAG pinout

연결해줄 신호는 TDI, TCK, TMS, TDO, nTRST, VTREF(=VCC3.3), GND 모두 7개. 보드쪽 10번은 TRST- 에 연결해준다. CPLD 신호와 HDD_nRESET은 걍 무시.