Jan Fan     About     Archive     Feed     中文博客

Works Applications Written Test 2014

Just submit the code for the test of WAP. There are two problems in the test, not so easy(at least for me :(), but I have learnt quite a lot during the test. Now let me show them here for you.


Dynamic Programming with State Compression

Exam 1 Specification

First of all, it’s about looking for the shortest distance in a graph with obstacles - routing. You have to know something first:

With the knowledge above, we are able to solve some problem like this:


But the exam requires to pass through multiple checkpoints along the way from S to G. If we solving it using Brute Force, the complexity it \(18!\) (maximum number of checkpoints - 18), which is too costly. We need to figure another way out.

Full permutation of 1-7 is 7!

    |       1,2,3,4,5,6,7      |
    |                          |
    |  ||  ||  ||  ||  ||  ||  |

When the S has passed a sub set of all checkpoints, {@}, the shortest distance along the subset can lead to the final shortest distance along all checkpoints. This is the optimization of subproblems.

      shortest d1   shortest d2
        ,-----.      ,-----.
       /       \    /       \
  S   ( 1,2,3,4 )  (  5,6,7  )  G
      \\       /    \       //
       \`-----'      `-----'/
        \                  /
         shortest d = d1+d2
Consider in this case, whether the permutation of 1-4 and 5-6 are calculated repeatedly?

    |    1,2,3,4   |  5,6  |
    |              |       |
    |  ||  ||  ||  ||  ||  ||7 |

Here we reveal our another weapon - Dynamic Programming - to “cache” the shortest distance along subset of checkpoints, as a trade-off between space and time.

Now we still have two things to complete the DP algorithm:

For 18 checkpoints, we get \(2^{18}\) possible subsets. To represent them, we can use a technique called State Compression. Using an integer for a state, each bit of which stands for the existence of one checkpoint.

As for the recursive formulation:

                                     /( 1 ) + dist(1,2)
                                    /  `-'
                               = min\  ,-.
                               |     \( 2 ) + dist(2,1)
                               |       `-'
                            ( 1,2 ) + min(dist(1,3),dist(2,3)
                         /   `---'
         ,-----.        /
        /       \      /     ,---.
       (  1,2,3  ) =min     ( 1,3 ) + min(dist(1,2),dist(3,2)
        \       /      \     `---'
         `-----'        \
                         \   ,---.
                            ( 2,3 ) + min(dist(2,1),dist(3,1)

What is quite pity is that since computer can not know what checkpoints exist in a state in advance, it has to traverse the state, i.e., to check the bit in the integer(state) one by one, which increase the complexity.

Therefore, the total complexity of DP is \(O(18*18*(2^{18}))\).

In program, we can fill the DP matrix starting from state \(0\)(no checkpoints), to state \(2^{18}-1\)(all checkpoints), in the step of 1.

So far the problem is almost done. the final result is attained through multi-phase optimal intermediates, separated by checkpoints.

The code .. may not be very readable, since I take it as a practice on C++11 features. Sorry about that :-(. My code for exam 1

Persistent Data Structures

Exam 2 Specification

Problem 2 is about Immutable Object. An Immutable Object is like the String type in Java, whose content can’t be changed after creation.

First we will introduce a technique called Copy on Write, which is also used on the system call - fork. If you would like to modify an immutable object, since it can not be changed, it will return a new copy with according modifications performed.

But this seems to imply that any changes to the data structure require the entire object to be copied into the new, modified object. However, that's not the case. You can Reuse some part of the original object to save space. When doing this, it’s called an Effective Immutable Object.

Therefore up to now, we can work out the target of problem 2 - to write an effective immutable queue that runs as fast as possible, i.e., to create new copy elements as least as possible or to reuse elements as much as possible.

If we make this queue based on Linked List, generally it requires \(O(1)\) on dequeue, but \(O(n)\) on enqueue, which is not fast enough.

Q1 = {a,b,c}
Q2 = Q1.dequeue()
Q3 = Q1.enqueue(d)
          a -> b -> c
                     \  /
          a -> b -> c -> d
          |           \/
          |           /\

I have taken tree structure \(O(logn)\) into consideration, but sorted elements would be more suitable, instead of a queue.

I’m pretty confused until I find this implementation. It uses two linked list for enqueue and dequeue respectively, making the cost \(O(1)\) for both operations, apart from the case that the list for dequeue becomes empty, and \(O(n)\) is needed to rotate the other list for dequeue.

However, this is the most effective structure I can think of. If you’ve got a better idea, just share it with me :).

This code is very readable, I promise! :-P. Since the code is quite self-explaining, I won’t make further explaination here. My code for exam 2


comments powered by Disqus