## About me

**Best TA award**in Department of Computer Science at Dartmouth College in 2013.

## Education

- Ph.D. in Computer Science, Dartmouth College
- M.S. in Computer Science, National Tsing Hua University

Joined Computational Systems Biology and Bio-Medicine Laboratory, leaded by Professor Chuan Yi Tang - B.S. in Computer Science, National Cheng-Chi University

Joined Intelligent Media Laboratory, leaded by Professor Tsai-Yen Li

## Experience

- Research Assistant, The Institute of Information Science, Academia Sinica
- Research Assistant, The Genomics Research Center, Academia Sinica

### Optimal trajectories for kinematic planar rigid bodies

**rigid body**in the Euclidean plane with

**no obstacles**. The model of robot motion is only

**kinematic**; that is,

**no dynamics**, and

**no drift**. How can we efficiently find a time-optimal trajectory connecting two given configurations?

Dubins CCC curve | Dubins LSR curve | Reeds-Shepp C|C|C curve | Reeds-Shepp LRSLR curve |

Reeds-Shepp LRLR curve | Differential drive TGT curve | Differential drive turn-drive-turn curve | Omnidirectional vehicle ROLL curve |

Omnidirectional vehicle SHUFFLE curve |

### Complete search for optimal trajectories

### Diversity and survival of expendable robots

## Software

### Optimal trajectories for differential Drive, Dubins car, and Reeds-Shepp car

## Publication

### Journal Papers

**Yu-Han Lyu**, Yining Chen, Devin Balkcom, k-survivability: Diversity and survival of expendable robots,*submitted to IEEE Robotics and Automation Letters (RA-L).***Yu-Han Lyu**, Devin Balkcom, Optimal Trajectories for Kinematic Planar Rigid Bodies with Switching Costs,*International Journal of Robotics Research*, to appear.- Shin-Cheng Mu,
**Yu-Han Lyu**, and Akimasa Morihata, Approximate by Thinning: Deriving Fully Polynomial-Time Approximation Schemes,*Science of Computer Programming*, Volume 98, Part 4, 1 February 2015, Pages 484–515.

### Conference Papers

- Devin Balkcom, Ajay Kannan,
**Yu-Han Lyu**, Weifu Wang, Yinan Zhang, Metric cells: towards complete search for optimal trajectories, in*Proceeding of IEEE/RSJ International Conference on Intelligent Robots and Systems*, September 2015 **Yu-Han Lyu**, Devin Balkcom, Optimal Trajectories for Planar Rigid Bodies with Switching Costs, in*Proceeding of the Eleventh International Workshop on the Algorithmic Foundations of Robotics*, İstanbul, Turkey, August 2014**Yu-Han Lyu**, Andrei Furtuna, Weifu Wang, Devin Balkcom, The Bench Mover's Problem: Minimum-Time Trajectories, with Cost for Switching between Controls, in*Proceeding of 2014 IEEE International Conference on Robotics and Automation*, Hong Kong, June 2014- Andrei Furtuna, Weifu Wang,
**Yu-Han Lyu**, Devin Balkcom, Structure and geometry of minimum-time trajectories for planar rigid bodies, in*Proceeding of the Annual Allerton Conference on Communication, Control, and Computing*, Monticello, Illinois, October 2013 - Lisa Fleischer,
**Yu-Han Lyu**, Approximately Optimal Auctions for Selling Privacy when Costs are Correlated with data, in*Proceeding of the 13th ACM Conference on Electronic Commerce*, Valencia, Spain, June 2012 - Shin-Cheng Mu,
**Yu-Han Lyu**, Akimasa Morihata, Constructing Datatype-Generic Fully Polynomial-Time Approximation Schemes Using Generalised Thinning, in*Proceeding of the 6th Workshop on Generic Programming*, Baltimore, September 2010 **Yu-Han Lyu**, and Chuan Yi Tang, Random Generation of 2-Connected Graphs, in*Proceedings of the 24th Workshop on Combinatorial Mathematics and Computation Theory*, Taiwan, April 2007**Yu-Han Lyu**, and Tsai-Yen Li, Using Hierarchical Virtual Force to Simulate Crowd Motions, in*Proceedings of the Tenth Conference on Artificial Intelligence and Applications*, Taiwan, November 2005

### Master's thesis

**Yu-Han Lyu**, and Chuan Yi Tang, Random Generation of k-Connected graphs,*master thesis.*

## Links

## Fun Links

*algorithmic puzzles*. A good algorithmic puzzle should have a simple and clear statement so that anyone can understand the problem easily. Moreover, a good algorithmic puzzle should possess multiple solutions: one easy solution that any CS student can construct, and one clever solution that a good programmer can figure out. I personally prefer puzzles with academic values, since theoretically computer scientist may use some heavy-duty techniques that I cannot imagine to solve problems.

- algorithm textbooks: most problems in textbooks have some academic values. I bought 20+ algorithm textbooks and tried hard to solve all algorithm design problems in the textbooks to find fun problems.
- programing interview questions: a good interview question usually have a simple statement and a
*tricky*solution. - programming competitions: A good competition problem usually have a clever solution.

## Given a number \(x\) and an \(n \times m\) matrix \(A\) in which each row and column are in non-decreasing order, \(m \leq n\), design an algorithm to determine whether \(x \in A\).

**saddleback search**.

**A better solution**: First, do binary search in the middle column \(A_{*, mid}\) to find \(y_{mid}\). Since the submatrix in the top-left of \(A_{x_{mid}, mid}\) and the submatrix in the bottom-right of \(A_{x_{mid+1}, mid}\) can not contain \(x\), we recursively search for \(x\) in the remaining two submatrices. The complexity is \(O(m \lg (n / m))\).

## Given a number \(x\) and an \(n \times m\) matrix \(A\) in which each row and column are in non-decreasing order, design an algorithm to find the rank of \(x\) in \(A\).

**A better solution**: Use exponential search in the first column to find \(i = y_1\). Then, apply exponential search on the \(i\)-th row to find the largest index \(j\) such that \(A_{i, j} < x\). Since each row and column are sorted, we can ignore the first \(j\) columns and the last \(n - i\) rows and solve the remaining problem in the same way. It can be shown that this algorithm takes \(O(\sqrt{k})\), where \(k\) is the rank of \(x\).

## Given a positive integer \(k\) and an \(n \times m\) matrix \(A\) in which each row and column are in non-decreasing order, design an algorithm to find the \(k\)-th smallest number in \(A\).

**A better solution**: The idea is as follows: we iteratively eliminate some elements that cannot be the answer. Repeat this process until only one element remains.

## Let \(c\) be a fixed constant. Given a positive integer \(k\) and \(c\) sorted arrays of the same length \(n\), design an algorithm to find the \(k\)-th smallest number in these \(c\) sorted arrays.

**A better solution**: The idea is as follows: we iteratively eliminate some elements that cannot be the answer. Repeat this process until only one element remains.

## Given two sorted arrays \(A\) and \(B\) of \(m\) and \(n\) integers respectively, \(n > m\), design an algorithm to find the intersection of these two arrays.

**A better solution**: Use the median of \(B\) to divide \(A\) into two subarrays and then recursively solve the sub-problems. The time complexity is \(O(m \lg (n/m))\).

## Given a read-only array \(A\) of \(n\) integers, where \(A[i] \in [1 \dots n - 1]\) for all \(1 \leq i \leq n\), design an algorithm to find one duplicated element.

**Solution**: Since each element is in \([1, n-1]\), we conceptually consider each element as a node in a linked list, that is, element \(i\) points to an element \(A[i]\). Since no node can point to node \(n\), we consider node \(n\) as the head of this linked list. If node \(i\) is pointed by more than one element, then \(i\) is a duplicate value in the array. Thus, we can use classical cycle detection algorithm to find the head of the cycle, which is a duplicate element. The algorithn runs in linear time with \(O(1)\) additional variables.

## Given a read-only array \(A\) of \(n - k\) distinct integers, where \(A[i] \in [1 \dots n]\) for all \(1 \leq i \leq n - k\), design an algorithm to find all integers in \([1 \dots n] \setminus A\).

*xor*operations in linear time with \(O(1)\) additional variables without modifing \(A\).

**General solution**: Let \(x_1, \dots, x_k\) be the missing numbers. We can construct a system of equations \(\sum_{j = 1}^k x_j^i = b_i = \sum_{j=1}^n j^i- \sum_{j=1}^{n-k} A[j]^i\). Solve this system of polynomial equations and then get \(x_1, \dots, x_k\). Since solving a system of polynomial equations takes exponential time in the worst case, we need a different approach.

## Given a \(w\)-bit integer \(x\), design an algorithm to determine the position of the most significant set bit of \(x\). That is, find \(\lfloor \lg x \rfloor\). Assume that bitwise operations (and, or, not, xor) and integer arithmetics (+, -, *, /) on \(w\)-bit integers can be done in \(O(1)\) time.

**A better solution**: we can avoid the comparison in the binary search, since comparsion may be expensive for some architectures. First, set all bits that are on the right of the most significant bit to one. Then, add one to get \(2^{\lfloor \lg x \rfloor + 1}\), which has only one set bit. Since the index of the set bit is \(\lfloor \lg x \rfloor + 1\), index minus one is the answer.

*bitwise parallel*technique. The idea is to double the consecutive ones from the most significant set bit. In the first iteration, we set \(x\) to be the bitwise or of \(x\) and \(x \gg 1\). After the first iteration, \(x\) must have at least two consecutive ones from the most significant set bit. In the \(i\)-th iteration, we set \(x\) to be the bitwise or of \(x\) and \(x \gg 2^i\). After the \(i\)-th iteration, \(x\) must have \(2^{i}\) consecutive ones from the most significant set bit. After \(O(\lg w)\) iterations, we successfully set all bits that are on the right of the most significant bit to one.

## Given a positive integer \(k\) and a binary min-heap \(Q\) with \(n\) elements, design an algorithm to find the \(k\)-th smallest element in \(Q\).

**A better solution**: Create a binary heap \(P\) with one element, which is the minimum element of \(P\). In each iteration, delete the minimum \(m\) of \(P\). Then, add \(m\)'s children in \(Q\) to \(P\). The element deleted in the \(k\)-th iteration is the answer. Since the number of elements in \(P\) is \(O(k)\), the complexity is \(O(k \lg k)\).

## In an undirected graph \(G = (V, E)\), four vertices of \(G\), \(u, v, x\), and \(y\) form a 4-cycle, if \((u, v)\), \((v, x)\), \((x, y)\) and \((y, u)\) are in \(E\). Given an undirected graph with \(n\) vertices, design an algorithm to determine whether \(G\) contains a 4-cycle.

**A better solution**: Construct an \(n \times n\) matrix \(A\) with all zeros. For each vertex \(u\), for each pair of \(u\)'s neighbors \(v\) and \(x\), we test the value of \(y = A[v][x]\). If \(y\) is zero, then we set \(A[v][x] = u\), which means that \(v\) and \(x\) has a common neighbor \(u\). If \(y\) is non-zero, then we found a 4-cycle \(u, v, y, x\). Since each time we either find a 4-cycle or change the value of some entry in \(A\), the complexity is \(O(n^2)\).

Raphael Yuster and Uri Zwick, “Finding Even Cycles Even Faster,” SIAM Journal on Discrete Mathematics, Volume 10 Issue 2, May 1997, Pages 209 - 222. [DOI]

The key to performance is elegance, not battalions of special cases.

Jon Bentley and Doug McIlroy

### Improve branch prediction

long binarysearch(int a[], long n, int x) { long low = 0; for (long high = n - 1; low <= high; ) { long mid = low + ((high - low) >> 1); if (a[mid] >= x) high = mid - 1; else low = mid + 1; } return low; }

long mid = low + ((high - low) >> 1);to

long mid = low + ((high - low) >> 2);Is modified binary search faster? We test on random sorted integer array. Modified binary search improves the performance by ~10%. [CODE]

## Improve cache performance

void eratosthenes(char prime[], int n) { memset(prime, 1, n + 1); prime[0] = prime[1] = 0; int bound = round(sqrt(n)); for (int i = 2; i <= bound; ++i) { if (prime[i]) { for (int j = i * i; j <= n; j += i) prime[j] = 0; } } }

for (int j = i * i; j <= n; j += i) prime[j] = 0;to

for (int k = n / i, j = i * k; k >= i; --k, j -= i) if (prime[k]) prime[j] = 0;Since the number of iterations in the inner loop does not change, this transformation seems useless. However, the modifed version only takes 1/3 time to execute. [CODE]

## Improve instruction level parallelism

double sum(double a[], int n) { double ans = 0.0; for (int i = 0; i < n; ++i) ans += a[i]; return ans; }Asymptotically, this is the optimal solution. However, we can unroll the loop to improve the instruction level parallelism.

double sum(double a[], int n) { double even = 0.0, odd = 0.0; for (int i = 0; i + 1 < n; i += 2) { even += a[i]; odd += a[i + 1]; } return even + odd + (n & 1 ? a[n - 1] : 0.0); }The modified version is ~10% faster than the ordinary method. [CODE]