Works Applications Written Test 2014
28 Sep 2014Just 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
 Persistent Data Structures
!more
Dynamic Programming with State Compression
First of all, it’s about looking for the shortest distance in a graph with obstacles  routing. You have to know something first:
 The concept of graph: here adjacent list will better describe it.
 The basic algorithms to work out the shortest distance between pairs of points: BFS, Dijkstra, and A Star
With the knowledge above, we are able to solve some problem like this:
######
#S...#
####.#
#G...#
######
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 17 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 14 and 56 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 tradeoff between space and time.
Now we still have two things to complete the DP algorithm:
 How to represent subset of checkpoints in program?
 What is the recursive formulation on subsets?
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 multiphase 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
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)
Q1


a > b > c


Q2
/
\ /
\/
Q1


a > b > c > d
 \/
 /\
Q3
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 selfexplaining, I won’t make further explaination here. My code for exam 2