Archive for Algorithm

Interview questions

Posted in Algorithm with tags , , , on February 6, 2008 by wsjoung
  • what’s difference C++ and java
  • explain about java static
  • is java use call by reference or call by value
  • get the algorithm to fine nth value from the last element in single linked list, and write code

all questions look pretty easy though,

anyway, the last algorithm question. because it’s just one direction single linked list, we should trouble from the start node to the last node. then we can figure out how many elements in that linked list when we reached the last element. then we can simply travel again from the start node to (m-n)th element. complexity is O(n).
I was trying to bring up some other data structure like stack or hash table but, all those are not good in terms of space efficiency. we do not have to wast precious resource which doesn’t increase the performance that much.

Advertisements

Tomasulo’s Algorithm

Posted in Algorithm with tags , , on November 17, 2006 by wsjoung

An Efficient Algorithm for Exploiting Multiple Arithmetic Units, R. M. Tomasulo, IBM Journal, January 1967

instructions and it’s execution plan would be like this.

div Rg, Rb, Rc
add Rh, Rg, Rd (data hazard)
mul Rg, Re, Rf
add Ra, Rh, Rg (data hazard)

106670243_bb27bd269b.jpg

then, we should maintain RS(Reservation Station) for 2nd and 4th instructions because those instruction need to wait for previous result. and, RS may look like this. source operands of the 1st instruction are ready and the result would be tagged T1 for register Rg and then put this tag T1 and mark busy bit into register till the result comes out. but the first operand of 2nd instruction is not ready when this instruction decode. it need to wait for Rg which is tagged for T1 by previous instruction. by looking up the register, we can figure out. if busy bit is set, the register is not available. so, we should wait for this tagged result.

Ready Tag Contents Ready Tag Contents Register
Y Rb Y Rc T1
N T1 Y Rd T2
Y Re Y Rf T3
N T2 N T3 T4

RS and register will watch the result bus to get tagged result. for this example, we will get T1 first then 2nd instruction will be ready to go. when we got 2nd tagged result(T3), left operand of 4th instruction will be ready and the busy bit of the register Rg will be marked free(N).

busy Tab register
Y T4 Ra
Y T2 Rh
N T3 Rg

3D Rotation(and Align) about an arbitrary axis

Posted in Algorithm with tags , , on November 17, 2006 by wsjoung

we need several steps to do this job.
1. translate to origin
2. rotate Z
3. rotate Y

64819260_50a870c49c.jpg

Z-Axis Rotation
x’ = x*cos q – y*sin q
y’ = x*sin q + y*cos q
z’ = z

X-Axis Rotation
y’ = y*cos q – z*sin q
z’ = y*sin q + z*cos q
x’ = x

Y-Axis Rotation
z’ = z*cos q – x*sin q
x’ = z*sin q + x*cos q
y’ = y

Comparative Protein Modeling

Posted in Bioinformatics with tags , , on November 17, 2006 by wsjoung

Once we figure out the protein sequence, then how we can figure out its 3D structure?
There are two kinds of methods. Physical and empirical methods. The physical prediction methods are based on interactions between atoms and include molecular dynamics and energy minimization, whereas the empirical methods depend on the protein structures that have been already determined by experiments.
A comparative protein modeling method designed to find the most probable structure for a sequence given its alignment with related structures. 3D model is obtained by optimally satisfying spatial restraints derived from the alignment and expressed as probability density functions for the features restrained.

Evolution and Physics in comparative protein structure modeling.pdf
Comparative_Protein_Modeling.pdf

Error Detection and Correction:

Posted in Algorithm with tags , on November 17, 2006 by wsjoung

Everyone knows that it is easy to make mistakes when lots of numbers are involved – and I’m not talking about all those slip-ups that occur in exams. It is so easy to get a few digits of a bank account number mixed up, or for fingers to slip on a keyboard and enter the wrong numbers. Imagine the consequences of these errors: things might go your way, you might get access to Bill Gates’s bank account, for example, but the chances of that are relatively slim. Alternatively, if a bar code gets printed wrongly, you might end up paying the price of a bottle of champagne for your carton of apple juice or if the number on your airline ticket is wrong, who knows where you or your luggage might end up? Luckily, there are schemes in place to detect, and in some cases even correct, such errors almost immediately.

Error Detection and Correction