tag:blogger.com,1999:blog-58465887453673230772024-03-04T22:05:12.224-08:00BekoC: AlgorithmsBekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-5846588745367323077.post-24486799053975551622014-01-05T15:55:00.000-08:002014-01-05T16:24:18.285-08:00Comparison of iterative and recursive way of Fibonacci Sequence calculationThe Fibonacci numbers are the sequence of numbers<br />
<br />
$\{F_n\}_{n=1}^\infty$<br />
<br />
defined by the linear recurrence equation<br />
<br />
$$F_n = F_{n-1} + F_{n-2}$$<br />
<br />
with $F_1 = F_2 = 1$, and conventionally defining $F_0 = 0$.<br />
<br />
We can implement Fibonacci numbers by iteratively or by using recursion. These two functions are implemented in Matlab to compare the running time of the algorithms.<br />
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">function</span><span style="color: #bbbbbb;"> </span>[result] =<span style="color: #bbbbbb;"> </span><span style="color: #0066bb; font-weight: bold;">fibonacciRecursive</span>(n)<span style="color: #bbbbbb;"></span>
<span style="color: #888888;">%calculates the fibonacci output in recursive way</span>
<span style="color: #008800; font-weight: bold;">if</span> n<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">||</span> n<span style="color: #333333;">==</span><span style="color: #0000dd; font-weight: bold;">1</span>
result=<span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">else</span>
result=fibonacciRecursive(n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>)<span style="color: #333333;">+</span> fibonacciRecursive(n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">2</span>);
<span style="color: #008800; font-weight: bold;">end</span>
<span style="color: #008800; font-weight: bold;">end</span>
</pre>
</div>
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">function</span><span style="color: #bbbbbb;"> </span>[result] =<span style="color: #bbbbbb;"> </span><span style="color: #0066bb; font-weight: bold;">fibonacciIterative</span>( n )<span style="color: #bbbbbb;"></span>
<span style="color: #888888;">%calculates the fibonacci output in iterative way</span>
y1=<span style="color: #0000dd; font-weight: bold;">1</span>;
y2=<span style="color: #0000dd; font-weight: bold;">2</span>;
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #007020;">i</span>=<span style="color: #0000dd; font-weight: bold;">2</span>:n
result=y1<span style="color: #333333;">+</span>y2;
y2=y1;
y1=result;
<span style="color: #008800; font-weight: bold;">end</span>
<span style="color: #008800; font-weight: bold;">end</span></pre>
</div>
For testing:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">N=<span style="color: #0000dd; font-weight: bold;">10</span>;
fibonacciIter=<span style="color: #007020;">zeros</span>(N,<span style="color: #0000dd; font-weight: bold;">1</span>);
fibonacciRecur=<span style="color: #007020;">zeros</span>(N,<span style="color: #0000dd; font-weight: bold;">1</span>);
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #007020;">i</span>=<span style="color: #0000dd; font-weight: bold;">1</span>:N
tic
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #007020;">j</span>=<span style="color: #0000dd; font-weight: bold;">1</span>:<span style="color: #0000dd; font-weight: bold;">25</span>
fibonacciIterative(<span style="color: #007020;">i</span>);
<span style="color: #008800; font-weight: bold;">end</span>
fibonacciIter(<span style="color: #007020;">i</span>)=toc;
tic
<span style="color: #008800; font-weight: bold;">for</span> <span style="color: #007020;">j</span>=<span style="color: #0000dd; font-weight: bold;">1</span>:<span style="color: #0000dd; font-weight: bold;">25</span>
fibonacciRecursive(<span style="color: #007020;">i</span>);
<span style="color: #008800; font-weight: bold;">end</span>
fibonacciRecur(<span style="color: #007020;">i</span>)=toc;
<span style="color: #008800; font-weight: bold;">end</span>
X=<span style="color: #0000dd; font-weight: bold;">1</span>:N;
plot(X,fibonacciIter,X,fibonacciRecur);
legend(<span style="background-color: #fff0f0;">'Iterative'</span>, <span style="background-color: #fff0f0;">'Recursive'</span>)
xlabel(<span style="background-color: #fff0f0;">'input size'</span>);
ylabel(<span style="background-color: #fff0f0;">'time(seconds)'</span>);</pre>
</div>
The plot is:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnFTNm_aoqgQQkabrpUZkjxF9g9TWtmrrSaf5cjB0QYu1Hj8t4neYl6o0DRz8ynjTy8hqbCiaXZ8WUfgMIIYgoADxAjuIwGzaTmGfs7rSl32ifz9_y9hdBPS1_IKXyWooWdLJi0UjenEB1/s1600/plot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnFTNm_aoqgQQkabrpUZkjxF9g9TWtmrrSaf5cjB0QYu1Hj8t4neYl6o0DRz8ynjTy8hqbCiaXZ8WUfgMIIYgoADxAjuIwGzaTmGfs7rSl32ifz9_y9hdBPS1_IKXyWooWdLJi0UjenEB1/s1600/plot.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
As shown in plot recursive implementation is increasing exponentially in time with the given input size</div>
<br />
<br />BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-58830095277202769042013-12-11T03:48:00.004-08:002013-12-11T03:55:11.413-08:00Implementing Principle Component Analysis (PCA) in Python<div class="separator" style="background-color: white; clear: both; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">
i take a look at <a href="http://en.wikipedia.org/wiki/Principal_component_analysis" style="color: #cc0000; text-decoration: none;" target="_blank">PCA</a> (principle component analysis). i'm not sure this is implemented somewhere else but a quick review of my collage notes (reference needed) lead me the code below, and data is (reference needed):</div>
<div class="separator" style="background-color: white; clear: both; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">
</div>
<blockquote class="tr_bq" style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">
x y<br />
2.5 2.4<br />
0.5 0.7<br />
2.2 2.9<br />
1.9 2.2<br />
3.1 3.0<br />
2.3 2.7<br />
2 1.6<br />
1 1.1<br />
1.5 1.6<br />
1.1 0.9</blockquote>
<div class="separator" style="background-color: white; clear: both; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px; text-align: center;">
<br /></div>
<div style="background-color: white; border: dashed gray; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 16px;"><span style="color: #d04020;">'''</span>
<span style="color: #d04020;"> *@author beck </span>
<span style="color: #d04020;"> *@date Sep 14, 2012</span>
<span style="color: #d04020;"> *PCA with Python </span>
<span style="color: #d04020;"> *bekoc.blogspot.com </span>
<span style="color: #d04020;">'''</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">numpy</span> <span style="color: green; font-weight: bold;">as</span> <span style="color: #0e84b5; font-weight: bold;">np</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">matplotlib.pyplot</span> <span style="color: green; font-weight: bold;">as</span> <span style="color: #0e84b5; font-weight: bold;">plt</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">pylab</span>
xs<span style="color: #303030;">=</span> np<span style="color: #303030;">.</span>loadtxt(<span style="background-color: #fff0f0;">"pcaData"</span>,delimiter<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">" "</span>, skiprows<span style="color: #303030;">=</span><span style="color: #0000d0; font-weight: bold;">1</span>, usecols<span style="color: #303030;">=</span>(<span style="color: #0000d0; font-weight: bold;">0</span>,<span style="color: #0000d0; font-weight: bold;">1</span>)) <span style="color: grey;"># numpy array - similar to C array notation.</span>
<span style="color: grey;">#get mean</span>
meanx<span style="color: #303030;">=</span>np<span style="color: #303030;">.</span>average(xs[:,<span style="color: #0000d0; font-weight: bold;">0</span>])
meany<span style="color: #303030;">=</span>np<span style="color: #303030;">.</span>average(xs[:,<span style="color: #0000d0; font-weight: bold;">1</span>])
correctedX<span style="color: #303030;">=</span>[value<span style="color: #303030;">-</span>meanx <span style="color: green; font-weight: bold;">for</span> value <span style="font-weight: bold;">in</span> (xs[:,<span style="color: #0000d0; font-weight: bold;">0</span>])] <span style="color: grey;">#X data with the means subtracted</span>
correctedY<span style="color: #303030;">=</span>[value<span style="color: #303030;">-</span>meany <span style="color: green; font-weight: bold;">for</span> value <span style="font-weight: bold;">in</span> (xs[:,<span style="color: #0000d0; font-weight: bold;">1</span>])] <span style="color: grey;">#Y data with the means subtracted</span>
data<span style="color: #303030;">=</span> np<span style="color: #303030;">.</span>array([correctedX,correctedY])
<span style="color: green; font-weight: bold;">print</span> data<span style="color: #303030;">.</span>shape
covData<span style="color: #303030;">=</span>np<span style="color: #303030;">.</span>cov(data)<span style="color: grey;">#calculate covariance matrix</span>
eigenvalues, eigenvectors <span style="color: #303030;">=</span> np<span style="color: #303030;">.</span>linalg<span style="color: #303030;">.</span>eig(covData)
<span style="color: green; font-weight: bold;">print</span> eigenvectors
<span style="color: green; font-weight: bold;">print</span> eigenvectors[<span style="color: #0000d0; font-weight: bold;">0</span>][<span style="color: #0000d0; font-weight: bold;">0</span>] <span style="color: grey;">#eigenvectors are both unit eigenvectors</span>
<span style="color: green; font-weight: bold;">print</span> eigenvectors[<span style="color: #0000d0; font-weight: bold;">1</span>][<span style="color: #0000d0; font-weight: bold;">0</span>]
x<span style="color: #303030;">=</span> [n <span style="color: green; font-weight: bold;">for</span> n <span style="font-weight: bold;">in</span> <span style="color: #007020;">range</span> (<span style="color: #303030;">-</span><span style="color: #0000d0; font-weight: bold;">2</span>,<span style="color: #0000d0; font-weight: bold;">3</span>)]
y<span style="color: #303030;">=</span> [eigenvectors[<span style="color: #0000d0; font-weight: bold;">1</span>][<span style="color: #0000d0; font-weight: bold;">0</span>]<span style="color: #303030;">*</span>i<span style="color: #303030;">/</span>eigenvectors[<span style="color: #0000d0; font-weight: bold;">0</span>][<span style="color: #0000d0; font-weight: bold;">0</span>] <span style="color: green; font-weight: bold;">for</span> i <span style="font-weight: bold;">in</span> x ]
y1<span style="color: #303030;">=</span> [eigenvectors[<span style="color: #0000d0; font-weight: bold;">1</span>][<span style="color: #0000d0; font-weight: bold;">1</span>]<span style="color: #303030;">*</span>i<span style="color: #303030;">/</span>eigenvectors[<span style="color: #0000d0; font-weight: bold;">0</span>][<span style="color: #0000d0; font-weight: bold;">1</span>] <span style="color: green; font-weight: bold;">for</span> i <span style="font-weight: bold;">in</span> x ]
<span style="color: green; font-weight: bold;">print</span> x
<span style="color: green; font-weight: bold;">print</span> y
plt<span style="color: #303030;">.</span>plot(x, y,linestyle<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">'--'</span>, label<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">'eigenvector1'</span>)
plt<span style="color: #303030;">.</span>plot(x, y1, linestyle<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">'--'</span>, label<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">'eigenvector2'</span>)
plt<span style="color: #303030;">.</span>plot(data[<span style="color: #0000d0; font-weight: bold;">0</span>,:],data[<span style="color: #0000d0; font-weight: bold;">1</span>,:], marker<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">'+'</span>, linestyle<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">' '</span>, label<span style="color: #303030;">=</span> <span style="background-color: #fff0f0;">"Normalized data"</span> )
<span style="color: grey;">#plt.plot(xs[:,0],xs[:,1],marker='+',linestyle=' ')</span>
pylab<span style="color: #303030;">.</span>ylim([<span style="color: #303030;">-</span><span style="color: #0000d0; font-weight: bold;">2</span>,<span style="color: #0000d0; font-weight: bold;">2</span>])
pylab<span style="color: #303030;">.</span>xlim([<span style="color: #303030;">-</span><span style="color: #0000d0; font-weight: bold;">2</span>,<span style="color: #0000d0; font-weight: bold;">2</span>])
plt<span style="color: #303030;">.</span>title(<span style="background-color: #fff0f0;">'PCA example'</span>)
plt<span style="color: #303030;">.</span>legend()
plt<span style="color: #303030;">.</span>show()
</pre>
</div>
<div style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px; text-align: center;">
The code includes step 1 to 5</div>
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;"> PCA summary :</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">1- Given a dataset calculate normalized data (mean substructed data), let's say n dimension (feature) data</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">2-calculate covariance matrix of normalized data</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">3-calculate eigenvalues and eigenvectors of the covariance matrix</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">4-eigenvector with the largest eigenvalue is the principal component</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">5-choose p eigenvectors and multiply with your data</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">6-now your data is p dimension.</span><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="-webkit-box-shadow: rgba(0, 0, 0, 0.0980392) 1px 1px 5px; background-color: white; border: 1px solid rgb(255, 255, 255); box-shadow: rgba(0, 0, 0, 0.0980392) 1px 1px 5px; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px; margin-left: auto; margin-right: auto; padding: 5px; position: relative; text-align: center;"><tbody>
<tr><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguOps2MXoWI4ZWn4NY8GRdnPvaW4vwSvwsWwvUAxn56CNn7mWkS6Hlkv4WkF7cyzQl3nbF2AQiQQ_DFvC21xSndsmsO8V6nA5wm0N6AzMFbkEtCXV5qLDFvpCpkvNTrStvGZvH_wnG4E4k/s1600/pca.png" imageanchor="1" style="color: #33aaff; margin-left: auto; margin-right: auto;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguOps2MXoWI4ZWn4NY8GRdnPvaW4vwSvwsWwvUAxn56CNn7mWkS6Hlkv4WkF7cyzQl3nbF2AQiQQ_DFvC21xSndsmsO8V6nA5wm0N6AzMFbkEtCXV5qLDFvpCpkvNTrStvGZvH_wnG4E4k/s400/pca.png" style="-webkit-box-shadow: rgba(0, 0, 0, 0.0980392) 0px 0px 0px; background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: none; box-shadow: rgba(0, 0, 0, 0.0980392) 0px 0px 0px; padding: 0px; position: relative;" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 11px;">The green dotted plot of the eigenvector shows the most significant relation between dimensions<br />
<br />
<div style="text-align: left;">
Please refer to simple and consise tutorial at <a href="http://georgemdallas.wordpress.com/2013/10/30/principal-component-analysis-4-dummies-eigenvectors-eigenvalues-and-dimension-reduction/" target="_blank">georgemdallas blog </a></div>
</td></tr>
</tbody></table>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-4289574482296994842013-11-02T14:50:00.002-07:002013-11-02T15:57:09.831-07:00how to implement two stacks in one array<span style="color: #111111; font-family: Helvetica Neue, Arial, sans-serif;"><span style="font-size: 14px; line-height: 19.59375px;">My friend came up with a new question that he is asked in his interview,</span></span><br />
<span style="color: #111111; font-family: Helvetica Neue, Arial, sans-serif;"><span style="font-size: 14px; line-height: 19.59375px;"><br /></span></span>
<span style="color: #111111; font-family: Helvetica Neue, Arial, sans-serif;"><span style="font-size: 14px; line-height: 19.59375px;">Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.</span></span><br />
<span style="color: #111111; font-family: Helvetica Neue, Arial, sans-serif;"><span style="font-size: 14px; line-height: 19.59375px;"><br /></span></span>
<span style="color: #111111; font-family: Helvetica Neue, Arial, sans-serif;"><span style="font-size: 14px; line-height: 19.59375px;">The code is implemented in C++.</span></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjMeppiOBMBg2NiyZ_fAHcxuxtrIYxpsxYKBuFjnQACViP2tpiHZmd0n8PAknC0KhdVwD6gc6_a_fKvb0ztNmkQ3FdkS4aVUZsrRzXUsPuFBi_f8SyuZ3-_WKA0PMr18JQPm4rhvgyu0YJ/s1600/Capture.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="95" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjMeppiOBMBg2NiyZ_fAHcxuxtrIYxpsxYKBuFjnQACViP2tpiHZmd0n8PAknC0KhdVwD6gc6_a_fKvb0ztNmkQ3FdkS4aVUZsrRzXUsPuFBi_f8SyuZ3-_WKA0PMr18JQPm4rhvgyu0YJ/s400/Capture.PNG" width="400" /></a></div>
<span style="background-color: #fff9e3; color: #111111; font-family: 'Helvetica Neue', Arial, sans-serif; font-size: 14px; line-height: 19.59375px;"><br /></span>
<span style="background-color: #fff9e3; color: #111111; font-family: 'Helvetica Neue', Arial, sans-serif; font-size: 14px; line-height: 19.59375px;"><br /></span>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #888888;">/* </span>
<span style="color: #888888;"> * File: main.cpp</span>
<span style="color: #888888;"> * Author: bekoC</span>
<span style="color: #888888;"> */</span>
<span style="color: #557799;">#include <cstdlib></span>
<span style="color: #557799;">#include<stdio.h></span>
<span style="color: #557799;">#include <stdlib.h></span>
<span style="color: #557799;">#include<iostream></span>
<span style="color: #557799;">#define N 10 </span>
<span style="color: #008800; font-weight: bold;">struct</span> Stacks {
<span style="color: #333399; font-weight: bold;">char</span> charArray[N];
<span style="color: #333399; font-weight: bold;">int</span> top1, top2;
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">olustur</span>();
<span style="color: #333399; font-weight: bold;">bool</span> <span style="color: #0066bb; font-weight: bold;">Insert</span>(<span style="color: #333399; font-weight: bold;">int</span> stackNumber, <span style="color: #333399; font-weight: bold;">char</span> veri);
<span style="color: #333399; font-weight: bold;">char</span> <span style="color: #0066bb; font-weight: bold;">deleteFromStack</span>(<span style="color: #333399; font-weight: bold;">int</span> stackNumber);
<span style="color: #333399; font-weight: bold;">bool</span> <span style="color: #0066bb; font-weight: bold;">isEmpty</span>(<span style="color: #333399; font-weight: bold;">int</span> stackNumber);
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">printStack</span>(<span style="color: #333399; font-weight: bold;">int</span> stackNumber);
};
<span style="color: #333399; font-weight: bold;">bool</span> Stacks<span style="color: #333333;">::</span>Insert(<span style="color: #333399; font-weight: bold;">int</span> stackNumber, <span style="color: #333399; font-weight: bold;">char</span> newChar) {
<span style="color: #008800; font-weight: bold;">if</span> (top1 <span style="color: #333333;">==</span> top2)
{
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #007020;">false</span>;
}
<span style="color: #008800; font-weight: bold;">if</span> (stackNumber <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">1</span>)
charArray[top1<span style="color: #333333;">++</span>] <span style="color: #333333;">=</span> newChar;
<span style="color: #008800; font-weight: bold;">else</span>
charArray[top2<span style="color: #333333;">--</span>] <span style="color: #333333;">=</span> newChar;
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #007020;">true</span>;
}
<span style="color: #333399; font-weight: bold;">char</span> Stacks<span style="color: #333333;">::</span>deleteFromStack(<span style="color: #333399; font-weight: bold;">int</span> stackNumber) {
<span style="color: #008800; font-weight: bold;">if</span> (stackNumber <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">1</span>)
<span style="color: #008800; font-weight: bold;">return</span> charArray[<span style="color: #333333;">--</span>top1];
<span style="color: #008800; font-weight: bold;">else</span>
<span style="color: #008800; font-weight: bold;">return</span> charArray[<span style="color: #333333;">++</span>top2];
}
<span style="color: #333399; font-weight: bold;">bool</span> Stacks<span style="color: #333333;">::</span>isEmpty(<span style="color: #333399; font-weight: bold;">int</span> stackNumber) {
<span style="color: #008800; font-weight: bold;">if</span> (stackNumber <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">1</span>)
<span style="color: #008800; font-weight: bold;">return</span> (top1 <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">0</span>);
<span style="color: #008800; font-weight: bold;">else</span>
<span style="color: #0066bb; font-weight: bold;">return</span> (top2 <span style="color: #333333;">==</span> N <span style="color: #333333;">-</span> <span style="color: #0000dd; font-weight: bold;">1</span>);
}
<span style="color: #333399; font-weight: bold;">void</span> Stacks<span style="color: #333333;">::</span>create() {
top1 <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
top2 <span style="color: #333333;">=</span> N <span style="color: #333333;">-</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
}
<span style="color: #333399; font-weight: bold;">void</span> Stacks<span style="color: #333333;">::</span>printStack(<span style="color: #333399; font-weight: bold;">int</span> stackNumber) {
<span style="color: #008800; font-weight: bold;">if</span> (stackNumber <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">&&</span> <span style="color: #333333;">!</span>isEmpty(stackNumber)) {
{
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>; i <span style="color: #333333;"><=</span> top1; <span style="color: #333333;">++</span>i) {
printf(<span style="background-color: #fff0f0;">"%c"</span>, charArray[i]);
}
}
} <span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span> (isEmpty(stackNumber)) {
printf(<span style="background-color: #fff0f0;">"Stack 1 is empty"</span>);
}
<span style="color: #008800; font-weight: bold;">if</span> (stackNumber <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">2</span> <span style="color: #333333;">&&</span> <span style="color: #333333;">!</span>isEmpty(stackNumber)) {
<span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> N <span style="color: #333333;">-</span> <span style="color: #0000dd; font-weight: bold;">1</span>; i <span style="color: #333333;">>=</span> top2; i<span style="color: #333333;">--</span>) {
printf(<span style="background-color: #fff0f0;">"%c"</span>, charArray[i]);
}
} <span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span> (isEmpty(stackNumber)) {
printf(<span style="background-color: #fff0f0;">"Stack 2 is empty"</span>);
}
}
<span style="color: #333399; font-weight: bold;">int</span> main() {
Stacks myStack;
myStack.create();
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0044dd;">'A'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0044dd;">'B'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0044dd;">'C'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0044dd;">'D'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0044dd;">'E'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">1</span>, <span style="color: #0044dd;">'F'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">2</span>, <span style="color: #0044dd;">'W'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">2</span>, <span style="color: #0044dd;">'X'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">2</span>, <span style="color: #0044dd;">'Y'</span>);
myStack.Insert(<span style="color: #0000dd; font-weight: bold;">2</span>, <span style="color: #0044dd;">'Z'</span>);
myStack.printStack(<span style="color: #0000dd; font-weight: bold;">1</span>);
myStack.printStack(<span style="color: #0000dd; font-weight: bold;">2</span>);
<span style="color: #008800; font-weight: bold;">if</span> (<span style="color: #333333;">!</span>myStack.isEmpty(<span style="color: #0000dd; font-weight: bold;">1</span>))
myStack.deleteFromStack(<span style="color: #0000dd; font-weight: bold;">1</span>);
<span style="color: #008800; font-weight: bold;">if</span> (<span style="color: #333333;">!</span>myStack.isEmpty(<span style="color: #0000dd; font-weight: bold;">2</span>))
myStack.deleteFromStack(<span style="color: #0000dd; font-weight: bold;">2</span>);
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
</pre>
</div>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-39824532404939483072013-11-02T10:59:00.002-07:002013-11-02T12:40:07.418-07:00Linked List Interview QuestionRecently, my friend asked me to write a basic program in C to add a indicator (e.g. any number or char) between the two nodes of the given linked list. He is asked this question in one of the job interviews.<br />
The output of the program with the indicator of 99 is shown as below.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9q3lLWsdOn2ntmGV86ysa_jLqUZswAaezlw5ZmB9wnNYSPJ2ssea0TeXNq0uCYj1TWhg7hcZS-RSUVaJ0u6nvALKauZ_xPCCeDRQA6sI45XJOVIwmBYjivtUFtxZ0qsEwFSW3PsPLFla9/s1600/Capture.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="76" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9q3lLWsdOn2ntmGV86ysa_jLqUZswAaezlw5ZmB9wnNYSPJ2ssea0TeXNq0uCYj1TWhg7hcZS-RSUVaJ0u6nvALKauZ_xPCCeDRQA6sI45XJOVIwmBYjivtUFtxZ0qsEwFSW3PsPLFla9/s400/Capture.PNG" width="400" /></a></div>
<br />
<br />
The code
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #888888;">/* </span>
<span style="color: #888888;"> * File: main.cpp</span>
<span style="color: #888888;"> * Author: bekoC</span>
<span style="color: #888888;"> */</span>
<span style="color: #888888;">//Some notes about my compilation errors:</span>
<span style="color: #888888;">//There are many ways to get a segfault, </span>
<span style="color: #888888;">//at least in the lower-level languages such as C(++). </span>
<span style="color: #888888;">//A common way to get a segfault is to dereference a null pointer:</span>
<span style="color: #888888;">//int *p = NULL;</span>
<span style="color: #888888;">//*p = 1;</span>
<span style="color: #557799;">#include <cstdlib></span>
<span style="color: #557799;">#include <stdlib.h></span>
<span style="color: #557799;">#include <stdio.h></span>
using namespace std;
<span style="color: #008800; font-weight: bold;">struct</span> Node {
<span style="color: #333399; font-weight: bold;">int</span> data;
<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>next;
};
<span style="color: #008800; font-weight: bold;">struct</span> Node<span style="color: #333333;">*</span> <span style="color: #0066bb; font-weight: bold;">insert</span>(<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>head, <span style="color: #333399; font-weight: bold;">int</span> data) {
<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>temp <span style="color: #333333;">=</span> (<span style="color: #008800; font-weight: bold;">struct</span> Node<span style="color: #333333;">*</span>) malloc(<span style="color: #008800; font-weight: bold;">sizeof</span> (<span style="color: #008800; font-weight: bold;">struct</span> Node)); <span style="color: #888888;">// for the new node address is taken by malloc in heap</span>
temp<span style="color: #333333;">-></span>data <span style="color: #333333;">=</span> data;
temp<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
<span style="color: #008800; font-weight: bold;">if</span> (head <span style="color: #333333;">==</span> <span style="color: #007020;">NULL</span>) {
head <span style="color: #333333;">=</span> temp; <span style="color: #888888;">// first node give the head temp's address</span>
} <span style="color: #008800; font-weight: bold;">else</span> {
Node <span style="color: #333333;">*</span>temp1 <span style="color: #333333;">=</span> head;
<span style="color: #008800; font-weight: bold;">while</span> (temp1<span style="color: #333333;">-></span>next <span style="color: #333333;">!=</span> <span style="color: #007020;">NULL</span>) {
temp1 <span style="color: #333333;">=</span> temp1<span style="color: #333333;">-></span>next;
}
temp1<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> temp;
}
<span style="color: #008800; font-weight: bold;">return</span> head;
}
<span style="color: #008800; font-weight: bold;">struct</span> Node<span style="color: #333333;">*</span> <span style="color: #0066bb; font-weight: bold;">addIndicator</span>(<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>head, <span style="color: #333399; font-weight: bold;">int</span> indicator) {
<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>newNode, <span style="color: #333333;">*</span>scan;
<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>temp1 <span style="color: #333333;">=</span> head;
<span style="color: #008800; font-weight: bold;">while</span> (temp1 <span style="color: #333333;">!=</span> <span style="color: #007020;">NULL</span> <span style="color: #333333;">&&</span> temp1<span style="color: #333333;">-></span>next <span style="color: #333333;">!=</span> <span style="color: #007020;">NULL</span>) {
newNode <span style="color: #333333;">=</span> (<span style="color: #008800; font-weight: bold;">struct</span> Node<span style="color: #333333;">*</span>) malloc(<span style="color: #008800; font-weight: bold;">sizeof</span> (<span style="color: #008800; font-weight: bold;">struct</span> Node));
newNode<span style="color: #333333;">-></span>data <span style="color: #333333;">=</span> indicator;
newNode<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> temp1<span style="color: #333333;">-></span>next;
temp1<span style="color: #333333;">-></span>next <span style="color: #333333;">=</span> newNode;
temp1 <span style="color: #333333;">=</span> newNode<span style="color: #333333;">-></span>next;
}
<span style="color: #008800; font-weight: bold;">return</span> head;
}
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">printList</span>(<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>head) {
<span style="color: #888888;">//using recursion</span>
<span style="color: #008800; font-weight: bold;">if</span> (head <span style="color: #333333;">==</span> <span style="color: #007020;">NULL</span>) {
<span style="color: #008800; font-weight: bold;">return</span>;
}
printf(<span style="background-color: #fff0f0;">"%d "</span>, head<span style="color: #333333;">-></span>data);
printList(head<span style="color: #333333;">-></span>next);
}
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">main</span>(<span style="color: #333399; font-weight: bold;">int</span> argc, <span style="color: #333399; font-weight: bold;">char</span><span style="color: #333333;">**</span> argv) {
<span style="color: #008800; font-weight: bold;">struct</span> Node <span style="color: #333333;">*</span>head <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>; <span style="color: #888888;">// head point to no address</span>
head <span style="color: #333333;">=</span> insert(head, <span style="color: #0000dd; font-weight: bold;">2</span>);
head <span style="color: #333333;">=</span> insert(head, <span style="color: #0000dd; font-weight: bold;">4</span>);
head <span style="color: #333333;">=</span> insert(head, <span style="color: #0000dd; font-weight: bold;">6</span>);
head <span style="color: #333333;">=</span> insert(head, <span style="color: #0000dd; font-weight: bold;">8</span>);
printList(head);
printf(<span style="background-color: #fff0f0;">"</span><span style="background-color: #fff0f0; color: #666666; font-weight: bold;">\n</span><span style="background-color: #fff0f0;">"</span>);
<span style="color: #888888;">//Adding a indicator which is 99</span>
<span style="color: #333399; font-weight: bold;">int</span> indicator <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">99</span>;
head <span style="color: #333333;">=</span> addIndicator(head, indicator);
printList(head);
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
</pre>
</div>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-91073136269779195602013-10-06T12:35:00.002-07:002013-10-06T12:36:21.162-07:00Yet another another language for scientific computing<div class="separator" style="clear: both; text-align: center;">
<a href="http://julialang.org/images/logo_hires.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://julialang.org/images/logo_hires.png" height="135" width="200" /></a></div>
<br />
<div style="text-align: justify;">
i have written a post about which programming language to use for the implementation of algorithms in machine learning, yet i have came across another scientific computing language while i was searching about recurrence. It's called <a href="http://julialang.org/" target="_blank">Julia</a>:</div>
<blockquote class="tr_bq" style="text-align: justify;">
<span style="background-color: white; font-family: Georgia, 'DejaVu Serif', serif; font-size: 15px; line-height: 23px;">Julia is a high-level, high-performance dynamic programming language for technical computing, with syntax that is familiar to users of other technical computing environments. It provides a sophisticated compiler, distributed parallel execution, numerical accuracy, and an extensive mathematical function library. The library, largely written in Julia itself, also integrates mature, best-of-breed C and Fortran libraries for linear algebra, random number generation, signal processing, and string processing. In addition, the Julia developer community is contributing a number of </span><a href="http://docs.julialang.org/en/latest/packages/packagelist/" style="background-color: white; color: #8888bb; font-family: Georgia, 'DejaVu Serif', serif; font-size: 15px; line-height: 23px; margin: 0px; padding: 0px; text-decoration: none;">external packages</a><span style="background-color: white; font-family: Georgia, 'DejaVu Serif', serif; font-size: 15px; line-height: 23px;"> through Julia’s built-in package manager at a rapid pace. </span><a href="https://github.com/JuliaLang/IJulia.jl" style="background-color: white; color: #8888bb; font-family: Georgia, 'DejaVu Serif', serif; font-size: 15px; line-height: 23px; margin: 0px; padding: 0px; text-decoration: none;" target="_blank">IJulia</a><span style="background-color: white; font-family: Georgia, 'DejaVu Serif', serif; font-size: 15px; line-height: 23px;">, a collaboration between the </span><a href="http://ipython.org/" style="background-color: white; color: #8888bb; font-family: Georgia, 'DejaVu Serif', serif; font-size: 15px; line-height: 23px; margin: 0px; padding: 0px; text-decoration: none;" target="_blank">IPython</a><span style="background-color: white; font-family: Georgia, 'DejaVu Serif', serif; font-size: 15px; line-height: 23px;"> and Julia communities, provides a powerful browser-based graphical notebook interface to Julia.</span></blockquote>
<div style="text-align: justify;">
i'm not sure that i need to use it but it desires to look at it because it is stated in official release that Julia beats all other high-level systems (i.e. everything besides C and Fortran) on all micro-benchmarks.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
you can read more detailed post <a href="http://strata.oreilly.com/2012/10/matlab-r-julia-languages-for-data-analysis.html" target="_blank">"MATLAB, R, and Julia: Languages for data analysis"</a> if you'd like to give a decision of using it or not. In addition, i'd like to recommend reading the post "<a href="http://2pif.info/op/julia.html" target="_blank">A Matlab Programmer's Take On Julia</a>",which criticizes Matlab. Finally, take a look at some benchmark results of <a href="http://justindomke.wordpress.com/2012/09/17/julia-matlab-and-c/" target="_blank">fibonacci and matrix multiplication computations</a> implemented with Julia.</div>
<div style="text-align: justify;">
<br /></div>
<br />
<br />
<blockquote class="tr_bq" style="text-align: justify;">
</blockquote>
<br />
<br />
<h3 class="post-title entry-title" itemprop="name" style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 20px; margin: 0.75em 0px 0px; position: relative;">
</h3>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-78325304565266404712013-09-29T15:10:00.004-07:002014-05-19T02:54:12.106-07:00Understanding thread basics with PythonRecently, I needed to use the threads in order to increase the CPU efficiency in terms of idle time in Python. I came a cross great examples from <a href="http://agiliq.com/blog/2013/09/process-and-threads-for-beginners">agiliq</a>'s blog. I have reimplemented his code and add some minor comments.<br />
You can refer the <a href="http://agiliq.com/blog/2013/09/understanding-threads-in-python/#comment-250748" target="_blank">original post</a> with more details.<br />
<div>
<br />
<b>Examining thread order:</b><br />
<b><br /></b>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #dd4422;">'''</span>
<span style="color: #dd4422;">Created on Sep 29, 2013</span>
<span style="color: #dd4422;">@author: </span><span style="color: #dd4422; line-height: 125%;">Bekoc::algorithms</span>
<span style="color: #dd4422;">'''</span>
<span style="color: #008800; font-weight: bold;">from</span> <span style="color: #0e84b5; font-weight: bold;">threading</span> <span style="color: #008800; font-weight: bold;">import</span> Thread
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">time</span>
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">urllib2</span>
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">GetUrlThread</span>(Thread):
<span style="color: #008800; font-weight: bold;">def</span> <span style="color: #0066bb; font-weight: bold;">__init__</span>(<span style="color: #007020;">self</span>, url):
<span style="color: #007020;">self</span><span style="color: #333333;">.</span>url <span style="color: #333333;">=</span> url
<span style="color: #007020;">super</span>(GetUrlThread, <span style="color: #007020;">self</span>)<span style="color: #333333;">.</span>__init__()
<span style="color: #008800; font-weight: bold;">def</span> <span style="color: #0066bb; font-weight: bold;">run</span>(<span style="color: #007020;">self</span>):
resp <span style="color: #333333;">=</span> urllib2<span style="color: #333333;">.</span>urlopen(<span style="color: #007020;">self</span><span style="color: #333333;">.</span>url)
<span style="color: #008800; font-weight: bold;">print</span> <span style="color: #007020;">self</span><span style="color: #333333;">.</span>url, resp<span style="color: #333333;">.</span>getcode()
<span style="color: #008800; font-weight: bold;">def</span> <span style="color: #0066bb; font-weight: bold;">get_responses</span>():
urls <span style="color: #333333;">=</span> [<span style="background-color: #fff0f0;">'http://www.google.com'</span>, <span style="background-color: #fff0f0;">'http://www.amazon.com'</span>, <span style="background-color: #fff0f0;">'http://www.ebay.com'</span>, <span style="background-color: #fff0f0;">'http://www.alibaba.com'</span>, <span style="background-color: #fff0f0;">'http://www.reddit.com'</span>]
start <span style="color: #333333;">=</span> time<span style="color: #333333;">.</span>time()
threads <span style="color: #333333;">=</span> []
<span style="color: #008800; font-weight: bold;">for</span> url <span style="color: black; font-weight: bold;">in</span> urls:
t <span style="color: #333333;">=</span> GetUrlThread(url)
threads<span style="color: #333333;">.</span>append(t)
<span style="color: #008800; font-weight: bold;">print</span> (<span style="background-color: #fff0f0;">'Thread </span><span style="background-color: #eeeeee;">%s</span><span style="background-color: #fff0f0;"> is calling </span><span style="background-color: #eeeeee;">%s</span><span style="background-color: #fff0f0;">'</span> <span style="color: #333333;">%</span>(t<span style="color: #333333;">.</span>getName(), url))
t<span style="color: #333333;">.</span>start()
<span style="color: #008800; font-weight: bold;">for</span> t <span style="color: black; font-weight: bold;">in</span> threads:
t<span style="color: #333333;">.</span>join()
<span style="color: #008800; font-weight: bold;">print</span> <span style="background-color: #fff0f0;">"Elapsed time: </span><span style="background-color: #eeeeee;">%s</span><span style="background-color: #fff0f0;">"</span> <span style="color: #333333;">%</span> (time<span style="color: #333333;">.</span>time()<span style="color: #333333;">-</span>start)
get_responses()
</pre>
</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjisjGSjkR-ui1jZ0WBhbWx2SaLVO1zjQqvG2SsOAMXJf4bRTZbw81FMxAZtzIjukk-lrzQnYGuRRCggDJc-KVyiQpkPOQOyn14vkAQEI1xVy9R0KVt3BcNEI9h6AcV6PSRqGPMIwIYZECV/s1600/threadOrder.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjisjGSjkR-ui1jZ0WBhbWx2SaLVO1zjQqvG2SsOAMXJf4bRTZbw81FMxAZtzIjukk-lrzQnYGuRRCggDJc-KVyiQpkPOQOyn14vkAQEI1xVy9R0KVt3BcNEI9h6AcV6PSRqGPMIwIYZECV/s1600/threadOrder.PNG" height="175" width="320" /></a></div>
<br /></div>
<div>
<b><a href="http://en.wikipedia.org/wiki/Race_condition#Example" target="_blank">Race Condition</a> example without use of <i>lock.acquire</i> and <i>lock.release</i>:</b><br />
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #dd4422;">'''</span>
<span style="color: #dd4422;">Created on Sep 30, 2013</span>
<span style="color: #dd4422;">@author: Bekoc::algorithms</span>
<span style="color: #dd4422;">'''</span>
<span style="color: #008800; font-weight: bold;">from</span> <span style="color: #0e84b5; font-weight: bold;">threading</span> <span style="color: #008800; font-weight: bold;">import</span> Thread
<span style="color: #008800; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">time</span>
<span style="color: #888888;">#define a global variable</span>
some_var <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>
<span style="color: #008800; font-weight: bold;">class</span> <span style="color: #bb0066; font-weight: bold;">IncrementThreadRaceCondition</span>(Thread):
<span style="color: #008800; font-weight: bold;">def</span> <span style="color: #0066bb; font-weight: bold;">run</span>(<span style="color: #007020;">self</span>):
<span style="color: #888888;">#we want to read a global variable</span>
<span style="color: #888888;">#and then increment it</span>
<span style="color: #008800; font-weight: bold;">global</span> some_var
read_value <span style="color: #333333;">=</span> some_var
time<span style="color: #333333;">.</span>sleep(<span style="color: #333333;">.</span><span style="color: #4400ee; font-weight: bold;">001</span>)
<span style="color: #008800; font-weight: bold;">print</span> <span style="background-color: #fff0f0;">"some_var in </span><span style="background-color: #eeeeee;">%s</span><span style="background-color: #fff0f0;"> is </span><span style="background-color: #eeeeee;">%d</span><span style="background-color: #fff0f0;">"</span> <span style="color: #333333;">%</span> (<span style="color: #007020;">self</span><span style="color: #333333;">.</span>name, read_value)
some_var <span style="color: #333333;">=</span> read_value <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>
<span style="color: #008800; font-weight: bold;">print</span> <span style="background-color: #fff0f0;">"some_var in </span><span style="background-color: #eeeeee;">%s</span><span style="background-color: #fff0f0;"> after increment is </span><span style="background-color: #eeeeee;">%d</span><span style="background-color: #fff0f0;">"</span> <span style="color: #333333;">%</span> (<span style="color: #007020;">self</span><span style="color: #333333;">.</span>name, some_var)
<span style="color: #008800; font-weight: bold;">def</span> <span style="color: #0066bb; font-weight: bold;">use_increment_thread</span>():
threads2 <span style="color: #333333;">=</span> []
<span style="color: #008800; font-weight: bold;">for</span> i <span style="color: black; font-weight: bold;">in</span> <span style="color: #007020;">range</span>(<span style="color: #0000dd; font-weight: bold;">50</span>):
t <span style="color: #333333;">=</span> IncrementThreadRaceCondition()
threads2<span style="color: #333333;">.</span>append(t)
t<span style="color: #333333;">.</span>start()
<span style="color: #008800; font-weight: bold;">for</span> t <span style="color: black; font-weight: bold;">in</span> threads2:
t<span style="color: #333333;">.</span>join()
<span style="color: #008800; font-weight: bold;">print</span> <span style="background-color: #fff0f0;">"After 50 modifications, some_var should have become 50"</span>
<span style="color: #008800; font-weight: bold;">print</span> <span style="background-color: #fff0f0;">"After 50 modifications, some_var is </span><span style="background-color: #eeeeee;">%d</span><span style="background-color: #fff0f0;">"</span> <span style="color: #333333;">%</span> (some_var,)
use_increment_thread()
</pre>
</div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8y2d77mYCqiUYKOhvCUp96ppffkahELCS9P3VG-J-zuVrpmUA2tJr5yMTQ60oyGOeKGW4HLt4haZKUSEYbr2P0ottyqHLxkJlMo-XjCHRYDSYS2j9YSZy60qrjIvX4er48VPYY0p2VyBD/s1600/raceConditionError.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8y2d77mYCqiUYKOhvCUp96ppffkahELCS9P3VG-J-zuVrpmUA2tJr5yMTQ60oyGOeKGW4HLt4haZKUSEYbr2P0ottyqHLxkJlMo-XjCHRYDSYS2j9YSZy60qrjIvX4er48VPYY0p2VyBD/s1600/raceConditionError.PNG" height="64" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<b>in order to prevent the race condition change the run function and import Lock:</b></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">from</span> <span style="color: #0e84b5; font-weight: bold;">threading</span> <span style="color: #008800; font-weight: bold;">import</span> Lock
<span style="color: #008800; font-weight: bold;">def</span> <span style="color: #0066bb; font-weight: bold;">run</span>(<span style="color: #007020;">self</span>):
<span style="color: #888888;">#we want to read a global variable</span>
<span style="color: #888888;">#and then increment it</span>
<span style="color: #008800; font-weight: bold;">global</span> some_var
lock<span style="color: #333333;">.</span>acquire()
read_value <span style="color: #333333;">=</span> some_var
time<span style="color: #333333;">.</span>sleep(<span style="color: #333333;">.</span><span style="color: #4400ee; font-weight: bold;">001</span>)
<span style="color: #008800; font-weight: bold;">print</span> <span style="background-color: #fff0f0;">"some_var in </span><span style="background-color: #eeeeee;">%s</span><span style="background-color: #fff0f0;"> is </span><span style="background-color: #eeeeee;">%d</span><span style="background-color: #fff0f0;">"</span> <span style="color: #333333;">%</span> (<span style="color: #007020;">self</span><span style="color: #333333;">.</span>name, read_value)
some_var <span style="color: #333333;">=</span> read_value <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>
<span style="color: #008800; font-weight: bold;">print</span> <span style="background-color: #fff0f0;">"some_var in </span><span style="background-color: #eeeeee;">%s</span><span style="background-color: #fff0f0;"> after increment is </span><span style="background-color: #eeeeee;">%d</span><span style="background-color: #fff0f0;">"</span> <span style="color: #333333;">%</span> (<span style="color: #007020;">self</span><span style="color: #333333;">.</span>name, some_var)
lock<span style="color: #333333;">.</span>release()
</pre>
</div>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-79805927399555461912013-09-29T15:00:00.004-07:002013-09-29T15:16:49.092-07:00Khan Academy offers Python Programming courseThere are lots of Python online courses going on around, but take a look at khan academy <a href="https://www.khanacademy.org/science/computer-science/v/introduction-to-programs-data-types-and-variables" target="_blank">playlist</a>. It includes the basic programming concepts with Python.<br />
<br />
<ol class="first progress-container" style="background-color: #f7f7f7; border-right-color: rgb(204, 204, 204); border-right-style: solid; border-width: 0px 1px 0px 0px; box-sizing: border-box; color: white; float: left; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 12px; line-height: 22px; list-style: none; margin: 0px; padding: 0px; position: relative; vertical-align: top; width: 450px;">
<li class="progress-item" style="border: 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/introduction-to-programs-data-types-and-variables" style="border: 0px; box-sizing: border-box; color: #678d00; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798248" style="background-position: 50% 50%; border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798248 video-node" style="background-image: url(data:image/png; background-position: 50% 50%; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Introduction to Programs Data Types and Variables</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/binary-numbers" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v65176942" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v65176942 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Binary Numbers</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/python-lists" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798249" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798249 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Python Lists</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/for-loops-in-python" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798250" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798250 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">For Loops in Python</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/while-loops-in-python" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798251" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798251 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">While Loops in Python</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/fun-with-strings" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v134691533" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v134691533 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Fun with Strings</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/writing-a-simple-factorial-program---python-2" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798255" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798255 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Writing a Simple Factorial Program. (Python 2)</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/stepping-through-the-factorial-program" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v132660403" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v132660403 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Stepping Through the Factorial Program</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/flowchart-for-the-factorial-program" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v132660406" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v132660406 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Flowchart for the Factorial Program</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/python-3-not-backwards-compatible-with-python-2" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v132660407" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v132660407 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Python 3 Not Backwards Compatible with Python 2</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/defining-a-factorial-function" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v132660401" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v132660401 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Defining a Factorial Function</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/diagramming-what-happens-with-a-function-call" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v132660405" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v132660405 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Diagramming What Happens with a Function Call</span></span></a></li>
</ol>
<ol class="second progress-container" style="background-color: #f7f7f7; border: 0px; box-sizing: border-box; color: white; float: left; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 12px; line-height: 22px; list-style: none; margin: 0px; padding: 0px; position: relative; vertical-align: top; width: 450px;">
<li class="progress-item" style="border: 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/recursive-factorial-function" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v132660402" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v132660402 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Recursive Factorial Function</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/comparing-iterative-and-recursive-factorial-functions" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v132660404" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v132660404 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Comparing Iterative and Recursive Factorial Functions</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/exercise---write-a-fibonacci-function" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798252" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798252 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Exercise - Write a Fibonacci Function</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/iterative-fibonacci-function-example" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798256" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798256 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Iterative Fibonacci Function Example</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/stepping-through-iterative-fibonacci-function" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798253" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798253 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Stepping Through Iterative Fibonacci Function</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/recursive-fibonacci-example" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v133798254" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v133798254 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Recursive Fibonacci Example</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/stepping-through-recursive-fibonacci-function" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v134691531" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v134691531 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Stepping Through Recursive Fibonacci Function</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/exercise---write-a-sorting-function" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v134691530" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v134691530 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Exercise - Write a Sorting Function</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/insertion-sort-algorithm" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v134691529" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v134691529 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Insertion Sort Algorithm</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/insertion-sort-in-python" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v134691532" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v134691532 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Insertion Sort in Python</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/stepping-through-insertion-sort-function" style="border: 0px; box-sizing: border-box; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v134691534" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v134691534 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Stepping Through Insertion Sort Function</span></span></a></li>
<li class="progress-item" style="border-top-color: rgb(221, 221, 221); border-top-style: solid; border-width: 1px 0px 0px; font-family: MuseoSans300, sans-serif; font-style: inherit; font-variant: inherit; line-height: 18px; margin: 0px; padding: 0px; position: relative; vertical-align: baseline;"><a class="progress-item-link" href="https://www.khanacademy.org/science/computer-science/v/simpler-insertion-sort-function" style="background-color: #ba3d66; border: 0px; box-sizing: border-box; color: white; display: block; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: inherit; margin: 0px; padding: 0px 5px; text-decoration: none; vertical-align: baseline; width: auto;"><div class="subway-icon v145846963" style="border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 52px; line-height: inherit; margin: 0px; padding: 0px; position: absolute; vertical-align: baseline; width: 40px;">
<div class="status v145846963 video-node" style="background-image: url(data:image/png; border: 0px; bottom: auto; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; height: 25px; left: 8px; line-height: inherit; margin: -12px 0px 0px; overflow: hidden; padding: 0px; position: absolute; right: auto; top: 26px; vertical-align: baseline; width: 25px; z-index: 20;">
</div>
</div>
<span class="progress-title" style="border: 0px; display: table-cell; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; line-height: 22px; margin: 0px; min-height: 40px; padding: 15px 15px 15px 50px; vertical-align: middle;"><span style="color: black;">Simpler Insertion Sort Function</span></span></a></li>
</ol>
<br />BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com29tag:blogger.com,1999:blog-5846588745367323077.post-56447863446876890702012-12-01T06:42:00.000-08:002012-12-01T06:46:04.061-08:00Linear Regression with Matlab Using Batch Gradient Descent Algorithm<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
i will implement linear regression which can be adapted classification easily, i use Matlab by following the Dr. Andrew Ng's class. You can watch the classes online from<a href="http://i%20will%20implement%20linear%20regression%20which%20can%20be%20adapted%20classification%20easily%2C%20%20%20i%20use%20matlab%20by%20following%20the%20%20andrew%20ng%27s%20class.%20you%20can%20watch%20the%20classes%20online%20from%20here./" target="_blank"> here</a>.</div>
<div style="text-align: justify;">
While implementing i also came across a very nice blog post, actually only dataset differs, in this case i use the original dataset given by the Dr. Ng, more details of the code below can be reached from <a href="http://www.dsplog.com/2011/10/29/batch-gradient-descent/" target="_blank">here</a> (<a href="http://www.dsplog.com/" style="text-align: center;" target="_blank">DSPlog</a> )</div>
<br />
<a href="http://openclassroom.stanford.edu/MainFolder/courses/MachineLearning/exercises/ex2materials/ex2Data.zip" target="_blank">download data</a><br />
<div style="text-align: justify;">
<span style="color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px;"><br /></span></div>
<span style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px;"> the linear regression model is</span><span style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px;"> </span><br />
<br />
<div style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
</div>
<div align="CENTER" class="mathdisplay" style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px;">
<img alt="\begin{displaymath}
h_{\theta}(x) = \theta^Tx = \sum_{i=0}^n \theta_i x_i, \nonumber
\end{displaymath}" border="0" src="http://openclassroom.stanford.edu/MainFolder/courses/MachineLearning/exercises/ex2/img6.png" height="55" width="184" /></div>
<br clear="ALL" style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px;" />
<div style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
</div>
<div style="background-color: #fffbf0; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
<span style="color: #333333; font-family: Arial, Helvetica, sans-serif;"><span style="font-size: 14px;"> and the batch gradient descent update rule is</span></span></div>
<div style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
<br /></div>
<div style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
</div>
<div align="CENTER" class="mathdisplay" style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px;">
<img alt="\begin{displaymath}
\theta_j := \theta_j - \alpha \frac{1}{m} \sum_{i=1}^m (h_{\...
...{(i)}) x_j^{(i)} \;\;\;\;\;\mbox{(for all $j$)} \nonumber
\par
\end{displaymath}" border="0" src="http://openclassroom.stanford.edu/MainFolder/courses/MachineLearning/exercises/ex2/img7.png" height="55" width="396" /></div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: solid gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">theta_vec = [0 0]<span style="color: #303030;">'</span>;
alpha = 0.007;
err = [0 0]<span style="color: #303030;">'</span>;
<span style="color: green; font-weight: bold;">for</span> kk = 1:1500
h_theta = (x<span style="color: #303030;">*</span>theta_vec);
h_theta_v = h_theta<span style="color: #303030;">*</span><span style="color: #007020;">ones</span>(1,n);
y_v = y<span style="color: #303030;">*</span><span style="color: #007020;">ones</span>(1,n);
theta_vec = theta_vec <span style="color: #303030;">-</span> alpha<span style="color: #303030;">*</span>1<span style="color: #303030;">/</span>m<span style="color: #303030;">*</span>sum((h_theta_v <span style="color: #303030;">-</span> y_v)<span style="color: #303030;">.*</span>x).<span style="background-color: #fff0f0;">';</span>
<span style="background-color: #fff0f0;"> err(:,kk) = 1/m*sum((h_theta_v - y_v).*x).'</span>;
<span style="color: green; font-weight: bold;">end</span>
</pre>
</div>
<br />
Cost Function:<br />
<img alt="\begin{displaymath}
J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}\left(h_{\theta}(x^{(i)})-y^{(i)}\right)^{2} \nonumber
\end{displaymath}" border="0" src="http://openclassroom.stanford.edu/MainFolder/courses/MachineLearning/exercises/ex2/img19.png" height="55" style="background-color: #fffbf0; color: #333333; font-family: Arial, Helvetica, sans-serif; font-size: 14px; text-align: -webkit-center;" width="252" /><br />
For different values of theta, in this case theta0 and theta1, we can plot the cost function J(theta) in 3d space or as a contour.<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: solid gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">j_theta = <span style="color: #007020;">zeros</span>(250, 250); <span style="color: grey;">% initialize j_theta</span>
theta0_vals = <span style="color: #007020;">linspace</span>(<span style="color: #303030;">-</span>5000, 5000, 250);
theta1_vals = <span style="color: #007020;">linspace</span>(<span style="color: #303030;">-</span>200, 200, 250);
<span style="color: green; font-weight: bold;">for</span> <span style="color: #007020;">i</span> = 1:<span style="color: #007020;">length</span>(theta0_vals)
<span style="color: green; font-weight: bold;">for</span> <span style="color: #007020;">j</span> = 1:<span style="color: #007020;">length</span>(theta1_vals)
theta_val_vec = [theta0_vals(<span style="color: #007020;">i</span>) theta1_vals(<span style="color: #007020;">j</span>)]<span style="color: #303030;">'</span>;
h_theta = (x<span style="color: #303030;">*</span>theta_val_vec);
j_theta(<span style="color: #007020;">i</span>,<span style="color: #007020;">j</span>) = 1<span style="color: #303030;">/</span>(2<span style="color: #303030;">*</span>m)<span style="color: #303030;">*</span>sum((h_theta <span style="color: #303030;">-</span> y)<span style="color: #303030;">.^</span>2);
<span style="color: green; font-weight: bold;">end</span>
<span style="color: green; font-weight: bold;">end</span>
figure;
surf(theta0_vals, theta1_vals,10<span style="color: #303030;">*</span><span style="color: #007020;">log10</span>(j_theta.<span style="background-color: #fff0f0;">'));</span>
<span style="background-color: #fff0f0;">xlabel('</span>theta_0<span style="color: #303030;">'</span>); ylabel(<span style="background-color: #fff0f0;">'theta_1'</span>);zlabel(<span style="background-color: #fff0f0;">'10*log10(Jtheta)'</span>);
title(<span style="background-color: #fff0f0;">'Cost function J(theta)'</span>);
figure;
contour(theta0_vals,theta1_vals,10<span style="color: #303030;">*</span><span style="color: #007020;">log10</span>(j_theta.<span style="background-color: #fff0f0;">'))</span>
<span style="background-color: #fff0f0;">xlabel('</span>theta_0<span style="color: #303030;">'</span>); ylabel(<span style="background-color: #fff0f0;">'theta_1'</span>)
title(<span style="background-color: #fff0f0;">'Cost function J(theta)'</span>);
</pre>
</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkJImVtEKMXF-t3z25ZoJKgq-vKJpgtVEG3fsaNymPHNLuMwhZQgEGNvLRLoRXRWuuyK0AgvTKkPKwTA2j_AgNorJ63oI_d3zZ_JeEoVtb29lb3rjgvCDkG7NDiP_w80rPZ4Qc6WoHVKiJ/s1600/fittedline.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkJImVtEKMXF-t3z25ZoJKgq-vKJpgtVEG3fsaNymPHNLuMwhZQgEGNvLRLoRXRWuuyK0AgvTKkPKwTA2j_AgNorJ63oI_d3zZ_JeEoVtb29lb3rjgvCDkG7NDiP_w80rPZ4Qc6WoHVKiJ/s1600/fittedline.png" height="240" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUs1p5AIlKJEFsJI4UYSjG041rjBoCIEz9DsyS0rxy8VtUNnvDZdC-nRByR7pQcLpsv84532TMlIHyLsVR4N_TdTd0B9hOAasAGsxx9FPUGP6WBqYeE0mazwRHPvoipTCa0ArgiGGEvq6p/s1600/contour.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUs1p5AIlKJEFsJI4UYSjG041rjBoCIEz9DsyS0rxy8VtUNnvDZdC-nRByR7pQcLpsv84532TMlIHyLsVR4N_TdTd0B9hOAasAGsxx9FPUGP6WBqYeE0mazwRHPvoipTCa0ArgiGGEvq6p/s1600/contour.png" height="240" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjp1HP9F3hvyXjQkcSKNsmsHzamtfYFtZPRuJw_VElf97ZxJvGiApZh8PbMC-jF7dKy0y7YdZkLtfsWx_ZHWXOzIP3J7IShLWTzpvInm3cnjvdjqr29SzQqLgcsfxNUrZWqFQob-tuAlFDg/s1600/3d.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjp1HP9F3hvyXjQkcSKNsmsHzamtfYFtZPRuJw_VElf97ZxJvGiApZh8PbMC-jF7dKy0y7YdZkLtfsWx_ZHWXOzIP3J7IShLWTzpvInm3cnjvdjqr29SzQqLgcsfxNUrZWqFQob-tuAlFDg/s1600/3d.png" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: solid gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: grey;">%linear regression using gradient descent algorithm to find the coefficients, </span>
<span style="color: grey;">%there are many ways to find the coefficients but now we apply gradient descent</span>
<span style="color: grey;">%one dimensional data, with an output </span>
x = load(<span style="background-color: #fff0f0;">'ex2x.dat'</span>);
y = load(<span style="background-color: #fff0f0;">'ex2y.dat'</span>);
figure <span style="color: grey;">% open a new figure window</span>
plot(x, y, <span style="background-color: #fff0f0;">'o'</span>);
ylabel(<span style="background-color: #fff0f0;">'Height in meters'</span>)
xlabel(<span style="background-color: #fff0f0;">'Age in years'</span>)
m = <span style="color: #007020;">length</span>(y); <span style="color: grey;">% store the number of training examples</span>
x = [<span style="color: #007020;">ones</span>(m, 1), x]; <span style="color: grey;">% Add a column of ones to x</span>
n = <span style="color: #007020;">size</span>(x,2);
<span style="color: grey;">%this part is for minimizing the Theta_vec: coefficients.</span>
theta_vec = [0 0]<span style="color: #303030;">'</span>;
alpha = 0.007;
err = [0 0]<span style="color: #303030;">'</span>;
<span style="color: green; font-weight: bold;">for</span> kk = 1:10000
h_theta = (x<span style="color: #303030;">*</span>theta_vec);
h_theta_v = h_theta<span style="color: #303030;">*</span><span style="color: #007020;">ones</span>(1,n);
y_v = y<span style="color: #303030;">*</span><span style="color: #007020;">ones</span>(1,n);
theta_vec = theta_vec <span style="color: #303030;">-</span> alpha<span style="color: #303030;">*</span>1<span style="color: #303030;">/</span>m<span style="color: #303030;">*</span>sum((h_theta_v <span style="color: #303030;">-</span> y_v)<span style="color: #303030;">.*</span>x).<span style="background-color: #fff0f0;">';</span>
<span style="background-color: #fff0f0;"> err(:,kk) = 1/m*sum((h_theta_v - y_v).*x)'</span>;
<span style="color: green; font-weight: bold;">end</span>
figure;
plot(x(:,2),y,<span style="background-color: #fff0f0;">'bs-'</span>);
hold on
plot(x(:,2),x<span style="color: #303030;">*</span>theta_vec,<span style="background-color: #fff0f0;">'rp-'</span>);
legend(<span style="background-color: #fff0f0;">'measured'</span>, <span style="background-color: #fff0f0;">'predicted'</span>);
grid on;
xlabel(<span style="background-color: #fff0f0;">'x'</span>);
ylabel(<span style="background-color: #fff0f0;">'y'</span>);
title(<span style="background-color: #fff0f0;">'Measured and predicted '</span>);
j_theta = <span style="color: #007020;">zeros</span>(250, 250); <span style="color: grey;">% initialize j_theta</span>
theta0_vals = <span style="color: #007020;">linspace</span>(<span style="color: #303030;">-</span>5000, 5000, 250);
theta1_vals = <span style="color: #007020;">linspace</span>(<span style="color: #303030;">-</span>200, 200, 250);
<span style="color: green; font-weight: bold;">for</span> <span style="color: #007020;">i</span> = 1:<span style="color: #007020;">length</span>(theta0_vals)
<span style="color: green; font-weight: bold;">for</span> <span style="color: #007020;">j</span> = 1:<span style="color: #007020;">length</span>(theta1_vals)
theta_val_vec = [theta0_vals(<span style="color: #007020;">i</span>) theta1_vals(<span style="color: #007020;">j</span>)]<span style="color: #303030;">'</span>;
h_theta = (x<span style="color: #303030;">*</span>theta_val_vec);
j_theta(<span style="color: #007020;">i</span>,<span style="color: #007020;">j</span>) = 1<span style="color: #303030;">/</span>(2<span style="color: #303030;">*</span>m)<span style="color: #303030;">*</span>sum((h_theta <span style="color: #303030;">-</span> y)<span style="color: #303030;">.^</span>2);
<span style="color: green; font-weight: bold;">end</span>
<span style="color: green; font-weight: bold;">end</span>
figure;
surf(theta0_vals, theta1_vals,10<span style="color: #303030;">*</span><span style="color: #007020;">log10</span>(j_theta.<span style="background-color: #fff0f0;">'));</span>
<span style="background-color: #fff0f0;">xlabel('</span>theta_0<span style="color: #303030;">'</span>); ylabel(<span style="background-color: #fff0f0;">'theta_1'</span>);zlabel(<span style="background-color: #fff0f0;">'10*log10(Jtheta)'</span>);
title(<span style="background-color: #fff0f0;">'Cost function J(theta)'</span>);
figure;
contour(theta0_vals,theta1_vals,10<span style="color: #303030;">*</span><span style="color: #007020;">log10</span>(j_theta.<span style="background-color: #fff0f0;">'))</span>
<span style="background-color: #fff0f0;">xlabel('</span>theta_0<span style="color: #303030;">'</span>); ylabel(<span style="background-color: #fff0f0;">'theta_1'</span>)
title(<span style="background-color: #fff0f0;">'Cost function J(theta)'</span>);
</pre>
</div>
<br />BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com1tag:blogger.com,1999:blog-5846588745367323077.post-34901599357310775912012-12-01T04:27:00.001-08:002014-05-19T02:55:52.755-07:00Matlab, Octove or Python for Machine Learning<div style="text-align: right;">
<i>but my adviser uses Matlab</i></div>
<br />
I start implementing ML algorithms after learning theory behind them however I really got stuck in which tool to write my code. There are 3 options for now: Octave, Matlab and Python (read <a href="http://news.ycombinator.com/item?id=363096" target="_blank">discussions</a>). You can check my previous <a href="http://bekoc.blogspot.com/p/from-perl-to-python.html" target="_blank">posts</a> about python, I switched to Python after learning Perl. For now, it seems that for implementation of machine learning algorithms preferring Matlab is a good decision.<br />
<br />
There are other tools such as R, Sage etc. i really don't know which one to master, but for now my adviser uses matlab exclusively, so do i.<br />
<br />
I list some useful posts that are good when you make your decision :<br />
<br />
<ul>
<li><a href="http://vnoel.wordpress.com/2008/05/03/bye-matlab-hello-python-thanks-sage/" target="_blank">Bye Matlab, hello Python, thanks Sage </a></li>
<li><a href="http://www.sagemath.org/tour.html" target="_blank">Sage Tour</a></li>
<li><a href="http://slashdot.org/topic/bi/r-octave-python-suits-your-analysis-needs/" target="_blank">R, Octave, and Python: Which Suits Your Analysis Needs?</a></li>
<li><a href="http://xenocoder.wordpress.com/2008/07/09/matlab-python-or-r-time-versus-money/" target="_blank">Matlab, Python, or R… Time versus Money</a></li>
</ul>
<br />
<br />
<br />
<br />
<h2 style="color: #333333; font-family: Georgia, serif; font-size: 16px; line-height: 24px; margin: 0px 0px 15px;">
</h2>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-39815412036984797032012-09-14T13:22:00.004-07:002013-12-11T03:50:58.211-08:00Switching From Perl to Python, Step 5 First Step into Machine Learning<div style="text-align: justify;">
in this post i share my experience while searching about the python machine learning modules. There are lots of them, i think that there is no one that can be used for all algorithms, so for a specific algorithm you can choose one of them that satisfies your need.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
First i start reading <a href="http://lister.dulci.duhs.duke.edu/~cliburn/summer-school/python/_build/html/getting_started.html#getting-started" target="_blank">Scientific Scripting with Python for Computational Immunology</a>, this is the best, short tutorial ever to understand the basic statistics. While going through stackoverflow questions, i realized that many people recommend <a href="http://scikit-learn.org/stable/" target="_blank">scikit-learn: machine learning in Python</a>.</div>
<div style="text-align: justify;">
<br />
<div style="text-align: left;">
i'm familiar with matplotlib and pyplot, however now in examples another module pylab is imported. <a href="http://truongnghiem.wordpress.com/" target="_blank">Clarification: matplotlib, pyplot, and pylab</a> from (<a href="http://truongnghiem.wordpress.com/">http://truongnghiem.wordpress.com</a>):</div>
<br />
<blockquote class="tr_bq">
<div style="text-align: left;">
pyplot is just a wrapper module to provide a Matlab-style interface to matplotlib.</div>
<div style="text-align: left;">
Many plotting functions in Matlab are provided by pyplot with the same names and arguments.</div>
</blockquote>
<blockquote class="tr_bq">
<div style="text-align: left;">
This will ease the process of moving from Matlab to Python for scientific computation.</div>
<div style="text-align: left;">
pylab is basically a mode in which pyplot and numpy are imported in a single namespace,</div>
<div style="text-align: left;">
thus making the Python working environment very similar to Matlab. By importing pylab: </div>
</blockquote>
<blockquote class="tr_bq">
<div style="text-align: left;">
from pylab import *</div>
<div style="text-align: left;">
we can use Matlab-style commands like:</div>
<div style="text-align: left;">
x = arange(0, 10, 0.2)</div>
<div style="text-align: left;">
y = sin(x)</div>
<div style="text-align: left;">
plot(x, y)</div>
</blockquote>
<br /></div>
Ok. Let's start, first i try simple linear regression from Scientific Scripting with Python for Computational Immunology. We have <b>dilution.cvs</b> file that contains the data of:<br />
<blockquote class="tr_bq">
Dilution Factor,Rep 1,Rep 2,Rep 3,Mean,sd<br />
1,15.16,14.95,14.55,14.89,0.31<br />
2,15.36,15.61,15.51,15.49,0.13<br />
4,16.65,16.88,16.71,16.75,0.12<br />
8,18.07,17.60,18.13,17.93,0.29<br />
16,18.86,19.63,19.39,19.29,0.39<br />
32,20.39,19.40,20.39,20.06,0.57<br />
64,21.44,20.76,21.22,21.14,0.35<br />
128,21.90,22.04,21.94,21.96,0.07<br />
256,22.87,22.77,23.36,23.00,0.32<br />
512,23.98,23.92,24.24,24.05,0.17<br />
1024,24.91,24.83,24.92,24.89,0.05<br />
2048,26.37,25.43,26.21,26.00,0.50</blockquote>
Dilution and Factor columns are used in order to implement the linear regression in two dimensional space where the line is defined as :<br />
<div class="separator" style="clear: both; text-align: left;">
<a href="http://www.codecogs.com/eqnedit.php?latex=y=mx@plus;b" style="margin-left: 1em; margin-right: 1em;" target="_blank"><img src="http://latex.codecogs.com/gif.latex?y=mx+b" title="y=mx+b" /></a></div>
<br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #d04020;">'''</span>
<span style="color: #d04020;"> *@author beck </span>
<span style="color: #d04020;"> *@date Sep 14, 2012</span>
<span style="color: #d04020;"> *Basic Statistics with Python </span>
<span style="color: #d04020;"> *bekoc.blogspot.com </span>
<span style="color: #d04020;">'''</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">numpy</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">matplotlib.pyplot</span> <span style="color: green; font-weight: bold;">as</span> <span style="color: #0e84b5; font-weight: bold;">plt</span>
<span style="color: grey;">#import pylab, # from pylab import *</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">scipy.stats</span> <span style="color: green; font-weight: bold;">as</span> <span style="color: #0e84b5; font-weight: bold;">stats</span>
xs<span style="color: #303030;">=</span> numpy<span style="color: #303030;">.</span>loadtxt(<span style="background-color: #fff0f0;">"dilution.csv"</span>,delimiter<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">","</span>, skiprows<span style="color: #303030;">=</span><span style="color: #0000d0; font-weight: bold;">1</span>, usecols<span style="color: #303030;">=</span>(<span style="color: #0000d0; font-weight: bold;">0</span>,<span style="color: #0000d0; font-weight: bold;">1</span>)) </pre>
<pre style="line-height: 125%; margin: 0;"><span style="color: grey;"># numpy array - similar to C array notation.</span>
x<span style="color: #303030;">=</span> numpy<span style="color: #303030;">.</span>log2(xs[:,<span style="color: #0000d0; font-weight: bold;">0</span>])
y<span style="color: #303030;">=</span>xs[:,<span style="color: #0000d0; font-weight: bold;">1</span>]
plt<span style="color: #303030;">.</span>plot(x,y,<span style="background-color: #fff0f0;">"x"</span>)
plt<span style="color: #303030;">.</span>xlabel(<span style="background-color: #fff0f0;">'Number of Dilutions(log2)'</span>)
plt<span style="color: #303030;">.</span>ylabel(<span style="background-color: #fff0f0;">'Rep1'</span>)
plt<span style="color: #303030;">.</span>title(<span style="background-color: #fff0f0;">'Linear Regression example'</span>)
plt<span style="color: #303030;">.</span>legend()
slope, intercept, r_value, p_value, std_error <span style="color: #303030;">=</span> stats<span style="color: #303030;">.</span>linregress(x,y)
plt<span style="color: #303030;">.</span>plot(x,intercept<span style="color: #303030;">+</span>slope<span style="color: #303030;">*</span>x,<span style="background-color: #fff0f0;">"r-"</span>) <span style="color: grey;"># y=mx+b where m is slope and b is intercept</span>
<span style="color: grey;">#plt.plot(x,x**2)</span>
plt<span style="color: #303030;">.</span>show()
</pre>
<pre style="line-height: 125%; margin: 0;"></pre>
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhh0vq2W4ENIano73MRDUpNRv3bGz3iNMgRQb7aOTepZ3MfNZIr52MpohT3BTp8n-Cj1K8CrCMYnRdEuydBCQDMXltEPlrR5R-Iw27MTdLqeOR13_ipuD9GYabP7nD254QnJkZt1Uu8gxk0/s1600/linreg.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhh0vq2W4ENIano73MRDUpNRv3bGz3iNMgRQb7aOTepZ3MfNZIr52MpohT3BTp8n-Cj1K8CrCMYnRdEuydBCQDMXltEPlrR5R-Iw27MTdLqeOR13_ipuD9GYabP7nD254QnJkZt1Uu8gxk0/s320/linreg.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
straight line seems reasonable</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
Resources for machine learning:<br />
<div>
<a href="http://scikit-learn.org/stable/#" target="_blank">scikit-learn: machine learning in Python, Easy-to-use and general-purpose machine learning in Python</a></div>
<div>
<a href="http://stackoverflow.com/questions/1289920/is-there-a-recommended-package-for-machine-learning-in-python" target="_blank">Is there a recommended package for machine learning in Python?</a><br />
<br /></div>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-30953506037064591142012-09-04T12:28:00.001-07:002012-09-15T04:14:55.039-07:00Switching From Perl to Python, Step 4 Basic Statistics<table style="background-color: white; border-collapse: collapse; color: black; font-family: 'Lucida Grande', 'Lucida Sans Unicode', Geneva, Verdana, sans-serif; font-size: 14px; line-height: 21px; margin: 0px -0.5em; text-align: left;"><tbody>
<tr bgcolor="#ddddff"><td style="padding: 0.2em 0.5em;"><br /></td><td style="padding: 0.2em 0.5em;"><div style="margin-bottom: 0.5em; margin-top: 0.8em; text-align: right;">
<i>On August 28 2012 at 10am, the creator of matplotlib, John D. Hunter died from complications arising from cancer treatment, after a brief but intense battle with this terrible illness. John is survived by his wife Miriam, his three daughters Rahel, Ava and Clara, his sisters Layne and Mary, and his mother Sarah.</i></div>
<div style="margin-bottom: 0.5em; margin-top: 0.8em; text-align: right;">
<i>If you have benefited from John's many contributions, please say thanks in the way that would matter most to him. Please consider making a donation to the <a href="http://numfocus.org/johnhunter/" style="color: #ca7900;">John Hunter Memorial Fund</a>.</i></div>
</td></tr>
</tbody></table>
<br />
<blockquote class="tr_bq">
<div style="text-align: justify;">
<div style="text-align: right;">
<i>Rest in peace, John Hunter (1968-August 28th, 2012). My sincere condolences to his family. Thank you for all your contribution. A great loss to the community.Thank you again. </i></div>
</div>
</blockquote>
<br />
After learning the basics of Python, today i will try to implement some basic statistical methods including plotting. We need two important packages mathplotlib and scipy. I remember that there is also numpy library, a bit confused but it's explained very well in official <a href="http://www.scipy.org/" target="_blank">scipy documentation</a>:<br />
<blockquote class="tr_bq">
<div style="text-align: justify;">
<span style="background-color: white; font-family: Verdana, Helvetica, Arial, sans-serif; font-size: 12px; line-height: 16.78333282470703px;">"SciPy (pronounced "Sigh Pie") is open-source software for mathematics, science, and engineering. It is also the name of a very popular </span><a class="http" href="http://conference.scipy.org/" style="background-color: white; border: 0px; color: #0066cc; font-family: Verdana, Helvetica, Arial, sans-serif; font-size: 12px; line-height: 16.78333282470703px; text-decoration: none;">conference</a><span style="background-color: white; font-family: Verdana, Helvetica, Arial, sans-serif; font-size: 12px; line-height: 16.78333282470703px;"> on scientific programming with Python. The SciPy library depends on </span><a class="http" href="http://numpy.scipy.org/" style="background-color: white; border: 0px; color: #0066cc; font-family: Verdana, Helvetica, Arial, sans-serif; font-size: 12px; line-height: 16.78333282470703px; text-decoration: none;">NumPy</a><span style="background-color: white; font-family: Verdana, Helvetica, Arial, sans-serif; font-size: 12px; line-height: 16.78333282470703px;">, which provides convenient and fast N-dimensional array manipulation. The SciPy library is built to work with NumPy arrays, and provides many user-friendly and efficient numerical routines such as routines for numerical integration and optimization."</span></div>
</blockquote>
i follow two useful blogs in order to learn how to plot and make basic statistical calculation by using pyton, after i learn these topics, i will search about machine learning libraries.<br />
<ul>
<li><a href="http://oneau.wordpress.com/2011/02/28/simple-statistics-with-scipy/" target="_blank">Simple statistics with SciPy</a></li>
<li><a href="http://bespokeblog.wordpress.com/2011/07/11/basic-data-plotting-with-matplotlib-part-3-histograms/" target="_blank">Basic Data Plotting with Matplotlib Part 3: Histograms</a></li>
</ul>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-20281974927685141352012-08-13T15:13:00.000-07:002013-02-16T04:53:09.683-08:00Switching From Perl to Python, Step 3 Python Data Structures<div style="text-align: right;">
<i>We read the Knuth, so you don't need to</i></div>
<div style="text-align: right;">
<i>-Tim Peters</i></div>
<br />
After finishing first part of Python, today i decided to read about Python data structures.<br />
Today's topics are:<br />
Night -2-<br />
10. Modules<br />
11. Data Structures<br />
12. Problem Solving<br />
<br />
While i was reading about the data structures in Python, list, tuple and dictionary implementations are very similar to corresponding Java collections list, set and map. Please check<a href="http://www.sthurlow.com/python/lesson06/" target="_blank"> here </a>to review some examples.<br />
<br />
While reading about the dictionaries, defaultdict implementation was interesting, in addition, i really like the one liners, as an example:<br />
<br />
<div style="text-align: justify;">
<span style="color: #222222; font-family: Courier New, Courier, FreeMono, monospace; font-size: x-small;"><span style="line-height: 18px;"><br /></span></span></div>
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">myfile<span style="color: #303030;">=</span><span style="color: #007020;">open</span>(<span style="background-color: #fff0f0;">'names'</span>, <span style="background-color: #fff0f0;">'r'</span>)
words<span style="color: #303030;">=</span>[line<span style="color: #303030;">.</span>rstrip() <span style="color: green; font-weight: bold;">for</span> line <span style="color: black; font-weight: bold;">in</span> myfile]
quote<span style="color: #303030;">=</span><span style="background-color: #fff0f0;">'''google</span>
<span style="background-color: #fff0f0;"> excite</span>
<span style="background-color: #fff0f0;"> yahoo</span>
<span style="background-color: #fff0f0;"> bing</span>
<span style="background-color: #fff0f0;"> altavista '''</span>
<span style="color: grey;">#find the words that exits in file but not in quote</span>
difference<span style="color: #303030;">=</span>[word <span style="color: green; font-weight: bold;">for</span> word <span style="color: black; font-weight: bold;">in</span> quote<span style="color: #303030;">.</span>split() <span style="color: green; font-weight: bold;">if</span> word <span style="color: black; font-weight: bold;">not</span> <span style="color: black; font-weight: bold;">in</span> words]
<span style="color: green; font-weight: bold;">print</span> difference
</pre>
</div>
<br />
Some useful resources:<br />
<a href="http://python%20in%20high%20performance%20computing/" target="_blank">Python in High performance computing </a><br />
<a href="http://www.python.org/doc/" target="_blank">Official python documentation</a><br />
<a href="www.zenisoft.cn:10010/get/pdf/1020" target="_blank">Data Structures and Algorithms Using Python</a><br />
<br />
<br />BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com1tag:blogger.com,1999:blog-5846588745367323077.post-69201884695087151512012-08-10T06:41:00.000-07:002012-08-11T12:49:27.696-07:00Switching From Perl to Python, Step 2 Python Basics<div style="text-align: right;">
<i> If you don't know any computer languages, I recommend starting with Python. It is cleanly designed, well documented, and relatively kind to beginners. Despite being a good first language, it is not just a toy; it is very powerful and flexible and well suited for large projects.
</i></div>
<div style="text-align: right;">
<i><a href="http://www.catb.org/esr/faqs/hacker-howto.html" target="_blank">How To Become A Hacker</a>, Eric Steven Raymond</i></div>
<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://coffeeghost.net/pybat/python_cheatsheet.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="640" src="http://coffeeghost.net/pybat/python_cheatsheet.png" width="524" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">From <a href="http://coffeeghost.net/pybat/python_cheatsheet.png" target="_blank">coffeeghost</a></td></tr>
</tbody></table>
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">Following topics are from </span><a href="http://www.ibiblio.org/g2swap/byteofpython/files/120/byteofpython_120.pdf" style="background-color: white; color: #cc0000; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px; text-decoration: none;" target="_blank">Byte of Python </a><span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">which is a free Python book </span><span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">for </span><span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">completely beginners.</span><br />
Today's topics:<br />
<div>
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">Night -1-</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">1. → Translations</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">2. → Preface</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">3. → Introduction</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">4. → Installation</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">5. → First Steps</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">6. → Basics</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">7. → Operators and Expressions</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">8. → Control Flow</span><br />
<span style="background-color: white; color: #222222; font-family: 'Courier New', Courier, FreeMono, monospace; font-size: 13px; line-height: 18px;">9. → Functions</span> </div>
<div>
<br /></div>
<div>
Resources that i have reviewed:</div>
<div>
<ul>
<li><a href="http://wiki.python.org/moin/SimplePrograms">http://wiki.python.org/moin/SimplePrograms</a>
</li>
<li><a href="http://www.sthurlow.com/python/">http://www.sthurlow.com/python/</a></li>
<li><a href="http://cs.simpson.edu/?q=node/26">http://cs.simpson.edu/?q=node/26</a> : when i was reading this page, <b>Pygame Graphics Examples</b> were interesting</li>
</ul>
<br /></div>BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-20045515795421844472012-08-10T04:42:00.002-07:002013-02-14T06:46:03.307-08:00Switching From Perl to Python, Step 1 Which IDE to use for Python programming ?<br />
<div style="text-align: justify;">
<div style="text-align: right;">
<i><span style="background-color: white; font-family: Arial, Verdana, Geneva, 'Bitstream Vera Sans', Helvetica, sans-serif; font-size: 14px; line-height: 21px; text-align: start;"> Python 2.x is the status quo, Python 3.x is the present and future of the language (</span><a href="http://wiki.python.org/moin/Python2orPython3">http://wiki.python.org/moin/Python2orPython3</a><span style="background-color: white; font-family: Arial, Verdana, Geneva, 'Bitstream Vera Sans', Helvetica, sans-serif; font-size: 14px; line-height: 21px; text-align: start;">)</span></i></div>
<div style="text-align: right;">
<i><span style="background-color: white; font-family: Arial, Verdana, Geneva, 'Bitstream Vera Sans', Helvetica, sans-serif; font-size: 14px; line-height: 21px; text-align: start;"><br /></span></i></div>
<br />
i followed the instruction from <a href="http://www.vogella.com/articles/Python/article.html" target="_blank">vogella</a>, however instead of installing python 2.7 directly from official python web page, i installed from <a href="http://www.enthought.com/products/getepd.php" target="_blank">enthought</a> academic version which includes the <b>numpy, Scipy and matplotlib</b>. These modules will be useful when we start programming,<br />
i do not give details for now.<br />
<br />
<br />
<blockquote class="tr_bq">
<b>Academic versions of Enthought:</b><br />
Students or employees from degree-granting institutions may use these installations for an extended period free of cost.</blockquote>
<br />
<br /></div>
After installing Eclipse and configuration of <b>PyDev</b> , i guess i'm ready for Python. Actually, i'd like to use netbeans instead but netbeans does not have python support after 7.0 versions.<br />
<br />
Some experiments to be sure that everything works smoothly:<br />
<br />
1-First (little) Python module (from vogella)<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZZpVz-h6sfnqJl9XiJeYtuvRfLygoTSEXFNWNmHksmeYh8-C3UKyS3WyzENjYhYiqopzT0AxnGzLRoykEvR_6PerGcS-IXifnPZ_oDIGdJHNlmKP1QIqHOEyyhWJSZ-m8ih6qJBfJR4q2/s1600/pythonfirst.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZZpVz-h6sfnqJl9XiJeYtuvRfLygoTSEXFNWNmHksmeYh8-C3UKyS3WyzENjYhYiqopzT0AxnGzLRoykEvR_6PerGcS-IXifnPZ_oDIGdJHNlmKP1QIqHOEyyhWJSZ-m8ih6qJBfJR4q2/s320/pythonfirst.PNG" height="219" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both;">
2- First (little)NumPy module</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwXIF9ZEAX9CwEuYc6qFvfZYxUBFNb99YPtMmP-vtozVAsEHUzLniAOGioGZ3mB3FmTIKxgqYFMqgMJkg6Of1VcBuQhoHG0CSik-h3zFkrlY0PPxc5SmRkg8GQRfWQyqTx9aFE2zoH-eZt/s1600/Numpy.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwXIF9ZEAX9CwEuYc6qFvfZYxUBFNb99YPtMmP-vtozVAsEHUzLniAOGioGZ3mB3FmTIKxgqYFMqgMJkg6Of1VcBuQhoHG0CSik-h3zFkrlY0PPxc5SmRkg8GQRfWQyqTx9aFE2zoH-eZt/s320/Numpy.PNG" height="152" width="320" /></a></div>
<div class="separator" style="clear: both;">
3-Scipy and Matplotlib module</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhODE4XhVqC0R-1IaLElcMJTi1ti6ayf5kYcT5_Uw_To1Lv9ZrTuo3Vbg6T3cRO9wzsts0iTJelwqFmaBudgMv7VokQ8I2sqBX2KPcTxExjlZTjPOHIciQQ4H3wGoKU7pGnnvEKafWnn_8z/s1600/matSci.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhODE4XhVqC0R-1IaLElcMJTi1ti6ayf5kYcT5_Uw_To1Lv9ZrTuo3Vbg6T3cRO9wzsts0iTJelwqFmaBudgMv7VokQ8I2sqBX2KPcTxExjlZTjPOHIciQQ4H3wGoKU7pGnnvEKafWnn_8z/s320/matSci.PNG" height="181" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
Code is from <a href="http://oneau.wordpress.com/2011/02/28/simple-statistics-with-scipy/" target="_blank">oneau</a></div>
<span style="background-color: white; font-family: Lato, arial, sans-serif; font-size: 16px; line-height: 24px;"><br /></span>
Ok. then i'm ready for Night 1 for tomorrow:<br />
<br />
1. → Translations<br />
2. → Preface<br />
3. → Introduction<br />
4. → Installation<br />
5. → First Steps<br />
6. → Basics<br />
7. → Operators and Expressions<br />
8. → Control Flow<br />
9. → Functions<br />
<br />
<br class="Apple-interchange-newline" />BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-77017618050926982512012-08-05T14:07:00.000-07:002012-08-10T04:47:20.271-07:00Binary Tree based algorithm questions<br />
i will try to find the answers of following 4 algorithm questions which can be implemented using binary search tree (BST). Please refer to the original questions with the Python implementation at <a href="http://www.ardendertat.com/2012/01/09/programming-interview-questions/" target="_blank">Arden's blog</a>.<br />
<ul>
<li style="text-align: justify;"><b>Binary Search Tree Check: </b>Given a binary tree, check whether it’s a binary search tree or not</li>
</ul>
<ul>
<li style="text-align: justify;"><b>Tree Level Order Print:</b> Given a binary tree of integers, print it in level order. The output will contain space between the numbers in the same level, and new line between different levels.</li>
</ul>
<ul>
<li style="text-align: justify;"><b>Tree Reverse Level Order Print</b>: This is very similar to the previous post level order print. We again print the tree in level order, but now starting from bottom level to the root.</li>
</ul>
<ul>
<li style="text-align: justify;"><b>Trim Binary Search Tree:</b> Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree.</li>
</ul>
<div style="text-align: justify;">
To understand or polish your knowledge about BST, you can go over the<a href="http://cslibrary.stanford.edu/110/BinaryTrees.html" target="_blank"> great tutorial of Nick Parlenta</a> and for the applications of binary trees you may read the <a href="http://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees" target="_blank">answers</a> posted in SO.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
To implement BST in Java, we need to create class like:</div>
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> <span style="color: green; font-weight: bold;">static</span> <span style="color: green; font-weight: bold;">class</span> <span style="color: #b00060; font-weight: bold;">TreeNode</span> <span style="color: #303030;">{</span>
TreeNode leftReference<span style="color: #303030;">;</span>
TreeNode rightReference<span style="color: #303030;">;</span>
<span style="color: #303090; font-weight: bold;">int</span> nodeValue<span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: #0060b0; font-weight: bold;">TreeNode</span><span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> nodeValue<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">this</span><span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span> <span style="color: #303030;">=</span> nodeValue<span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
</pre>
</div>
<br />
With a given BST, there are 3 kind of walk can be defined, inorder tree walk, preorder tree walk and postorder tree walk. Refer to <a href="http://en.wikipedia.org/wiki/Tree_traversal" target="_blank">Wikipedia article</a> to get details. While using <b>inorder tree walk</b>, note that the BST property allows us to print out all the values in the Binary Search Tree in sorted order. Before, i start implementation we need to understand these terms in order to write the code.<br />
<br />
<span style="text-align: justify;">we can implement inorder tree walk </span><span style="text-align: justify;">for binary search tree check </span><span style="text-align: justify;">and if BST is not sorted then we conclude that it's a not a BST. Both </span><span style="text-align: justify;">Tree Level Order Print and </span><span style="text-align: justify;">Tree Reverse Level Order Print can be implemented in similar way using recursion.</span><br />
<b style="text-align: justify;"><br /></b>
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: green; font-weight: bold;">package</span> pkg7binarysearchtreechk<span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">class</span> <span style="color: #b00060; font-weight: bold;">Main</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">static</span> <span style="color: green; font-weight: bold;">class</span> <span style="color: #b00060; font-weight: bold;">TreeNode</span> <span style="color: #303030;">{</span>
TreeNode leftReference<span style="color: #303030;">;</span>
TreeNode rightReference<span style="color: #303030;">;</span>
<span style="color: #303090; font-weight: bold;">int</span> nodeValue<span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: #0060b0; font-weight: bold;">TreeNode</span><span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> nodeValue<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">this</span><span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span> <span style="color: #303030;">=</span> nodeValue<span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">main</span><span style="color: #303030;">(</span>String<span style="color: #303030;">[]</span> args<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
run<span style="color: #303030;">();</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">run</span><span style="color: #303030;">()</span> <span style="color: #303030;">{</span>
<span style="color: grey;">// tree root node.</span>
<span style="color: #303090; font-weight: bold;">int</span> rootValue <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">40</span><span style="color: #303030;">;</span>
TreeNode rootnode <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> TreeNode<span style="color: #303030;">(</span>rootValue<span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"root node created, "</span> <span style="color: #303030;">+</span> rootnode<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">);</span>
<span style="color: grey;">// insertNode new element starting with rootnode.</span>
insertNode<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">11</span><span style="color: #303030;">);</span>
insertNode<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">15</span><span style="color: #303030;">);</span>
insertNode<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">16</span><span style="color: #303030;">);</span>
insertNode<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">23</span><span style="color: #303030;">);</span>
insertNode<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">79</span><span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"print the content of tree in inOrderTree walk"</span><span style="color: #303030;">);</span>
printTree<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"print the content of tree in preOrderTree walk"</span><span style="color: #303030;">);</span>
printPreOrderTree<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"print the content of tree in postOrderTree walk"</span><span style="color: #303030;">);</span>
printPostOrderTree<span style="color: #303030;">(</span>rootnode<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">private</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">insertNode</span><span style="color: #303030;">(</span>TreeNode parentNode<span style="color: #303030;">,</span> <span style="color: #303090; font-weight: bold;">int</span> nodeValue<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>nodeValue <span style="color: #303030;"><</span> parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">leftReference</span> <span style="color: #303030;">!=</span> <span style="color: green; font-weight: bold;">null</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">// Go more depth to left.</span>
insertNode<span style="color: #303030;">(</span>parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">leftReference</span><span style="color: #303030;">,</span> nodeValue<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"LEFT: new node value "</span> <span style="color: #303030;">+</span> nodeValue
<span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">" ,its root "</span> <span style="color: #303030;">+</span> parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">);</span>
parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">leftReference</span> <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> TreeNode<span style="color: #303030;">(</span>nodeValue<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>nodeValue <span style="color: #303030;">></span> parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">rightReference</span> <span style="color: #303030;">!=</span> <span style="color: green; font-weight: bold;">null</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">// Go more depth to right</span>
insertNode<span style="color: #303030;">(</span>parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">rightReference</span><span style="color: #303030;">,</span> nodeValue<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"RIGHT: new node value "</span> <span style="color: #303030;">+</span> nodeValue <span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">", its root "</span> <span style="color: #303030;">+</span> parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">);</span>
parentNode<span style="color: #303030;">.</span><span style="color: #0000c0;">rightReference</span> <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> TreeNode<span style="color: #303030;">(</span>nodeValue<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: grey;">// inorder tree walk</span>
<span style="color: green; font-weight: bold;">private</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">printTree</span><span style="color: #303030;">(</span>TreeNode node<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: #303090; font-weight: bold;">int</span> comparison<span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>node <span style="color: #303030;">!=</span> <span style="color: green; font-weight: bold;">null</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
printTree<span style="color: #303030;">(</span>node<span style="color: #303030;">.</span><span style="color: #0000c0;">leftReference</span><span style="color: #303030;">);</span>
comparison <span style="color: #303030;">=</span> node<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>comparison <span style="color: #303030;"><</span> node<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"Error not BST"</span><span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"node value "</span> <span style="color: #303030;">+</span> node<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">);</span>
printTree<span style="color: #303030;">(</span>node<span style="color: #303030;">.</span><span style="color: #0000c0;">rightReference</span><span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: grey;">// preorder tree walk </span>
<span style="color: green; font-weight: bold;">private</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">printPreOrderTree</span><span style="color: #303030;">(</span>TreeNode node<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>node <span style="color: #303030;">!=</span> <span style="color: green; font-weight: bold;">null</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"node value "</span> <span style="color: #303030;">+</span> node<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">);</span>
printTree<span style="color: #303030;">(</span>node<span style="color: #303030;">.</span><span style="color: #0000c0;">leftReference</span><span style="color: #303030;">);</span>
printTree<span style="color: #303030;">(</span>node<span style="color: #303030;">.</span><span style="color: #0000c0;">rightReference</span><span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: grey;">// postorder tree walk</span>
<span style="color: green; font-weight: bold;">private</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">printPostOrderTree</span><span style="color: #303030;">(</span>TreeNode node<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>node <span style="color: #303030;">!=</span> <span style="color: green; font-weight: bold;">null</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
printTree<span style="color: #303030;">(</span>node<span style="color: #303030;">.</span><span style="color: #0000c0;">leftReference</span><span style="color: #303030;">);</span>
printTree<span style="color: #303030;">(</span>node<span style="color: #303030;">.</span><span style="color: #0000c0;">rightReference</span><span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"node value "</span> <span style="color: #303030;">+</span> node<span style="color: #303030;">.</span><span style="color: #0000c0;">nodeValue</span><span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
</pre>
</div>BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-52203978497958202412012-07-27T02:37:00.000-07:002014-05-19T02:57:08.230-07:00String based algorithm questions<div style="text-align: justify;">
in this post, I try to implement the following string-related algorithm questions, note that as i mentioned before these questions are taken from Arden's <a href="http://www.ardendertat.com/2012/01/09/programming-interview-questions/" target="_blank">blog</a>, he implemented questions by using python (Please check his blog for more detailed explanations) I would<span style="background-color: white;"> like to implement using Java and try to make additional comments which I think that are useful for understanding the implementations of some type of data structures in Java programming language.</span></div>
<ul>
<li style="text-align: justify;"><span style="background-color: white;"><b>Non Repeated Characters in String : </b> </span>return the
unique characters in a given letter.</li>
<li style="text-align: justify;"><span style="background-color: white;"><b>Anagram Strings:</b> g</span><span style="background-color: white;">iven two strings, check if they’re anagrams or not. Two strings are anagrams if they are written using the same exact letters, ignoring space, punctuation and capitalization. Each letter should have the same count in both strings. For example, ‘Eleven plus two’ and ‘Twelve plus one’ are meaningful anagrams of each other.</span></li>
<li style="text-align: justify;"><span style="background-color: white;"><b>Find Word Positions in Text : </b>Given a text file and a word, find the positions that the word occurs in the file. We’ll be asked to find the positions of many words in the same file.</span></li>
<li style="text-align: justify;"><b>Remove Duplicate Characters in String:</b> <span style="background-color: white;">Remove duplicate characters in a given string keeping only the first occurrences. For example, if the input is ‘tree traversal’ the output will be ‘tre avsl’.</span></li>
</ul>
<div style="text-align: justify;">
In order to understand these types of questions, it <span style="background-color: white;"> </span><span style="background-color: white;">requires to store unique key and count of values each, </span><span style="background-color: white;">especially </span><span style="background-color: white;">basic understanding of hashmap is essential. Please </span><a href="http://www.mkyong.com/java/how-to-use-hashmap-tutorial-java/" style="background-color: white;" target="_blank">check here</a><span style="background-color: white;"> before you start reviewing the codes.</span><br />
<span style="background-color: white;"><br /></span></div>
<div style="text-align: justify;">
<div>
Ok. Let's start.</div>
<div>
<br /></div>
<div>
<h4>
<b><span style="background-color: white;">1- </span><span style="background-color: orange;">Non Repeated Characters in String </span><span style="background-color: white;">: </span></b> return unique characters in a given String </h4>
<div style="text-align: left;">
In this question, we use hashmap and complexity is :<br />
<div class="separator" style="clear: both; text-align: left;">
<a href="http://bekoc.blogspot.com/" style="margin-left: 1em; margin-right: 1em;" target="_blank"><img src="http://latex.codecogs.com/gif.latex?O(n) where~n ~is ~the ~length ~of~ a ~given ~word." title="O(n) where~n ~is ~the ~length ~of~ a ~given ~word." /></a></div>
<br /></div>
</div>
<div style="text-align: justify;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg3TfQxXFv-mJ9mvL5zOYTu2mxgl-70hNhXnXk3Tv84vpZBU-J96oFBICabFs4YjM6I0uPs3MiKhahjlhDldVhS02DRJedHiN1GmCYl60PTi2-3A-beI3NG-JYlPLsNiXaI5n1hy8rgPbIu/s1600/StrringUniqueChars.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg3TfQxXFv-mJ9mvL5zOYTu2mxgl-70hNhXnXk3Tv84vpZBU-J96oFBICabFs4YjM6I0uPs3MiKhahjlhDldVhS02DRJedHiN1GmCYl60PTi2-3A-beI3NG-JYlPLsNiXaI5n1hy8rgPbIu/s320/StrringUniqueChars.PNG" height="157" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<h4 style="text-align: justify;">
<span style="font-weight: normal;"><b><span style="background-color: white;">2- </span><span style="background-color: orange;">Anagram Strings</span><span style="background-color: white;">:</span></b><span style="background-color: white;"> g</span></span><span style="background-color: white; font-weight: normal;">iven two strings, check if they’re anagrams or not. Two strings are anagrams if they are written using the same exact letters, ignoring space, punctuation and capitalization. Each letter should have the same count in both strings. For example, ‘Eleven plus two’ and ‘Twelve plus one’ are meaningful anagrams of each other.</span></h4>
<div>
<span style="background-color: white; font-weight: normal;">Two implementations have coded, basic knowledge of Multiset is required to understand the second implementation which reduces the complexity to O(n).</span><br />
<span style="background-color: white; font-weight: normal;"><br /></span>
<span style="background-color: white; font-weight: normal;"></span><br />
<div>
<span style="background-color: white; font-weight: normal;"><span style="background-color: white;">To test: </span></span></div>
<div>
<div>
<span style="background-color: white; font-weight: normal;"><span style="background-color: white;"><span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> boolean result = isAnagram("Eleven plus two", "Twelve plus one");</span></span></span></div>
<span style="background-color: white; font-weight: normal;"><span style="background-color: white;"></span></span><br />
<div>
<span style="background-color: white; font-weight: normal;"><span style="background-color: white;"><span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> boolean result2 = isAnagramMultiset("ad", "daas");</span></span></span></div>
<span style="background-color: white; font-weight: normal;"><span style="background-color: white;"></span></span><br />
<div>
<span style="background-color: white; font-weight: normal;"><span style="background-color: white;"><br /></span></span></div>
<span style="background-color: white; font-weight: normal;"><span style="background-color: white;"></span></span></div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<span style="background-color: white; font-weight: normal;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEfogGaDLqr8cj7Vsw3ZeuvLaA1efvOuKfXyPJk-twapBxj4bd233D7XfUI6KVU8SQAX18kfxG3t-7Hbv1C_8DXwdu4wXn2EDI0cqXry3DeN06y9iOftWEZQMB-nbruq4XZf6fF_KpzLUS/s1600/anagram.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEfogGaDLqr8cj7Vsw3ZeuvLaA1efvOuKfXyPJk-twapBxj4bd233D7XfUI6KVU8SQAX18kfxG3t-7Hbv1C_8DXwdu4wXn2EDI0cqXry3DeN06y9iOftWEZQMB-nbruq4XZf6fF_KpzLUS/s320/anagram.PNG" height="49" width="320" /></a></span></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
</div>
<span style="background-color: white;"><b><br /></b></span>
<span style="background-color: white;"><b>3- </b></span><b style="background-color: orange;">Find Word Positions in Text :</b><b style="background-color: white;"> </b><span style="background-color: white;">Given a text file and a word, find the positions that the word occurs in the file. We’ll be asked to find the positions of many words in the same file. </span><br />
<br />
For this questions, we use a text instead of file to find the given word's position. We create a map and to store the values, arraylist is used. For a given key, if there are more than one appearance of a value, positions are appended to the arraylist.<!-- HTML generated using hilite.me --><br />
<br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
Map<span style="color: #303030;"><</span>String<span style="color: #303030;">,</span> ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">>></span> map <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> HashMap<span style="color: #303030;"><</span>String<span style="color: #303030;">,</span> ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">>>();</span></div>
<br />
we can test by :<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">findWordPosition<span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"have a nice try did you try try try"</span><span style="color: #303030;">,</span> <span style="background-color: #fff0f0;">"try"</span><span style="color: #303030;">);</span>
</pre>
</div>
<br />
<span style="background-color: white;"><b>4-</b></span><b style="background-color: orange;">Remove Duplicate Characters in String:</b><span style="background-color: white;"> </span><span style="background-color: white;">Remove duplicate characters in a given string keeping only the first occurrences. For example, if the input is ‘tree traversal’ the output will be ‘tre avsl’.</span><br />
<span style="background-color: white;"><br /></span>
<span style="background-color: white;">This question best fits with use of sets, you can check the <a href="http://bekoc.blogspot.com/p/java-structures.html" target="_blank">cheatsheet</a> of java collections to make decision which collection is better for a given problem.</span><br />
<span style="background-color: white;"><br /></span>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> Set<span style="color: #303030;"><</span>Character<span style="color: #303030;">></span> set <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> LinkedHashSet<span style="color: #303030;"><</span>Character<span style="color: #303030;">>();</span>
</pre>
</div>
<span style="background-color: white; font-weight: normal;"></span><br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> Set<span style="color: #303030;"><</span>Character<span style="color: #303030;">></span> set <span style="color: #303030;">=</span> removeDuplicateChars<span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"tree traversal"</span><span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span>Character entry <span style="color: #303030;">:</span> set<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span>entry<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span></pre>
</div>
</div>
<div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjCszvTx46jSXDrnvv87XeOO1Ebr4uYYcjN5juTxxMYvX1Y_wE20eCGE7R7Rd_gNfTlMVi0uLNbQCMKNDJGj6R0NwzBwYpOPG-fnkgIu0DQ6lA51PP_yfebAiBzxC8XOybxBatmOQzknV4h/s1600/string3-4.PNG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjCszvTx46jSXDrnvv87XeOO1Ebr4uYYcjN5juTxxMYvX1Y_wE20eCGE7R7Rd_gNfTlMVi0uLNbQCMKNDJGj6R0NwzBwYpOPG-fnkgIu0DQ6lA51PP_yfebAiBzxC8XOybxBatmOQzknV4h/s320/string3-4.PNG" height="155" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">output of problem 3 and 4</td></tr>
</tbody></table>
</div>
</div>
</div>
<h3>
<b>Implementations of 4 questions</b></h3>
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: grey;">/*</span>
<span style="color: grey;"> *@author beck </span>
<span style="color: grey;"> *@date Jul 27, 2012 </span>
<span style="color: grey;"> *StringAlgorithms </span>
<span style="color: grey;"> *bekoc.blogspot.com </span>
<span style="color: grey;"> */</span>
<span style="color: green; font-weight: bold;">package</span> stringalgorithms<span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">com.google.common.collect.HashMultiset</span><span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">com.google.common.collect.Multiset</span><span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.*</span><span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">class</span> <span style="color: #b00060; font-weight: bold;">StringAlgorithms</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">main</span><span style="color: #303030;">(</span>String<span style="color: #303030;">[]</span> args<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">//1-Non Repeated Characters in String : return the unique characters in a given letter.</span>
ArrayList<span style="color: #303030;"><</span>String<span style="color: #303030;">></span> uniqueCharsResults <span style="color: #303030;">=</span> uniqueLetters<span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"teesstedbyyourself"</span><span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> i <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span> i <span style="color: #303030;"><</span> uniqueCharsResults<span style="color: #303030;">.</span><span style="color: #0000c0;">size</span><span style="color: #303030;">();</span> i<span style="color: #303030;">++)</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">print</span><span style="color: #303030;">(</span>uniqueCharsResults<span style="color: #303030;">.</span><span style="color: #0000c0;">get</span><span style="color: #303030;">(</span>i<span style="color: #303030;">)</span> <span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">" "</span><span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: grey;">//2- Anagram Strings: given two strings, check if they’re anagrams or not.</span>
<span style="color: grey;">//Two strings are anagrams if they are written using the same exact letters, ignoring space, punctuation and capitalization. </span>
<span style="color: grey;">//Each letter should have the same count in both strings. </span>
<span style="color: grey;">//For example, ‘Eleven plus two’ and ‘Twelve plus one’ are meaningful anagrams of each other.</span>
<span style="color: grey;">//complexity is logn</span>
<span style="color: #303090; font-weight: bold;">boolean</span> result <span style="color: #303030;">=</span> isAnagram<span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"Eleven plus two"</span><span style="color: #303030;">,</span> <span style="background-color: #fff0f0;">"Twelve plus one"</span><span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"Anagram Test using sorting, Result is: "</span> <span style="color: #303030;">+</span> result<span style="color: #303030;">);</span>
<span style="color: grey;">//to reduce the complexity linear time, n, we can use hashtable</span>
<span style="color: grey;">//first store Text1 in a hastable </span>
<span style="color: grey;">//(key, value pairs where key is the each character in Text1 </span>
<span style="color: grey;">//and value is the count of the characters) and then go thru Text2 one by one</span>
<span style="color: grey;">//character and decrease the count of the text1, if all counts of text 1 is 0 then</span>
<span style="color: grey;">//can be called as anagram Strings.</span>
<span style="color: #303090; font-weight: bold;">boolean</span> result2 <span style="color: #303030;">=</span> isAnagramMultiset<span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"ad"</span><span style="color: #303030;">,</span> <span style="background-color: #fff0f0;">"daas"</span><span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"Anagram Test using Multiset, Result is: "</span> <span style="color: #303030;">+</span> result2<span style="color: #303030;">);</span>
<span style="color: grey;">//3- Find Word Positions in Text : Given a text file </span>
<span style="color: grey;">//and a word, find the positions that the word </span>
<span style="color: grey;">//occurs in the file. We’ll be asked to find the positions of </span>
<span style="color: grey;">//many words in the same file.</span>
findWordPosition<span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"have a nice try did you try try try"</span><span style="color: #303030;">,</span> <span style="background-color: #fff0f0;">"try"</span><span style="color: #303030;">);</span>
<span style="color: grey;">//4-Remove Duplicate Characters in String: Remove duplicate characters </span>
<span style="color: grey;">//in a given string keeping only the first occurrences. For example, </span>
<span style="color: grey;">//if the input is ‘tree traversal’ the output will be ‘tre avsl’.</span>
Set<span style="color: #303030;"><</span>Character<span style="color: #303030;">></span> set <span style="color: #303030;">=</span> removeDuplicateChars<span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"tree traversal"</span><span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span>Character entry <span style="color: #303030;">:</span> set<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span>entry<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> ArrayList<span style="color: #303030;"><</span>String<span style="color: #303030;">></span> uniqueLetters<span style="color: #303030;">(</span>String text<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">//create a hashmap with key and value pairs, where key is the each letter and</span>
<span style="color: grey;">//value is the count of each letter of a given text</span>
Map<span style="color: #303030;"><</span>Character<span style="color: #303030;">,</span> Integer<span style="color: #303030;">></span> map <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> HashMap<span style="color: #303030;"><</span>Character<span style="color: #303030;">,</span> Integer<span style="color: #303030;">>();</span>
<span style="color: grey;">//to store unique letters create an arraylist</span>
ArrayList<span style="color: #303030;"><</span>String<span style="color: #303030;">></span> uniqueChars <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> ArrayList<span style="color: #303030;"><</span>String<span style="color: #303030;">>();</span>
<span style="color: grey;">//we check each letter in a given text, so in this problem we don't need StringTokenizer</span>
<span style="color: grey;">//StringTokenizer tokenizer = new StringTokenizer(text);</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> i <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span> i <span style="color: #303030;"><</span> text<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">();</span> <span style="color: #303030;">++</span>i<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>map<span style="color: #303030;">.</span><span style="color: #0000c0;">containsKey</span><span style="color: #303030;">(</span>text<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">)))</span> <span style="color: #303030;">{</span>
<span style="color: #303090; font-weight: bold;">int</span> count <span style="color: #303030;">=</span> map<span style="color: #303030;">.</span><span style="color: #0000c0;">get</span><span style="color: #303030;">(</span>text<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">));</span>
map<span style="color: #303030;">.</span><span style="color: #0000c0;">put</span><span style="color: #303030;">(</span>text<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">),</span> count <span style="color: #303030;">+</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">);</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: #303030;">{</span>
map<span style="color: #303030;">.</span><span style="color: #0000c0;">put</span><span style="color: #303030;">(</span>text<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">),</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: grey;">// Loop in a hashSet to get keys and values</span>
Iterator iterator <span style="color: #303030;">=</span> map<span style="color: #303030;">.</span><span style="color: #0000c0;">entrySet</span><span style="color: #303030;">().</span><span style="color: #0000c0;">iterator</span><span style="color: #303030;">();</span>
<span style="color: green; font-weight: bold;">while</span> <span style="color: #303030;">(</span>iterator<span style="color: #303030;">.</span><span style="color: #0000c0;">hasNext</span><span style="color: #303030;">())</span> <span style="color: #303030;">{</span>
Map<span style="color: #303030;">.</span><span style="color: #0000c0;">Entry</span> pairs <span style="color: #303030;">=</span> <span style="color: #303030;">(</span>Map<span style="color: #303030;">.</span><span style="color: #0000c0;">Entry</span><span style="color: #303030;">)</span> iterator<span style="color: #303030;">.</span><span style="color: #0000c0;">next</span><span style="color: #303030;">();</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span>pairs<span style="color: #303030;">.</span><span style="color: #0000c0;">getKey</span><span style="color: #303030;">()</span> <span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">" = "</span> <span style="color: #303030;">+</span> pairs<span style="color: #303030;">.</span><span style="color: #0000c0;">getValue</span><span style="color: #303030;">()</span> <span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">" times appeared"</span><span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>pairs<span style="color: #303030;">.</span><span style="color: #0000c0;">getValue</span><span style="color: #303030;">().</span><span style="color: #0000c0;">equals</span><span style="color: #303030;">(</span><span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">))</span> <span style="color: #303030;">{</span>
uniqueChars<span style="color: #303030;">.</span><span style="color: #0000c0;">add</span><span style="color: #303030;">(</span>pairs<span style="color: #303030;">.</span><span style="color: #0000c0;">getKey</span><span style="color: #303030;">().</span><span style="color: #0000c0;">toString</span><span style="color: #303030;">());</span>
<span style="color: #303030;">}</span>
iterator<span style="color: #303030;">.</span><span style="color: #0000c0;">remove</span><span style="color: #303030;">();</span> <span style="color: grey;">// avoids a ConcurrentModificationException</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">return</span> uniqueChars<span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">boolean</span> <span style="color: #0060b0; font-weight: bold;">isAnagram</span><span style="color: #303030;">(</span>String text1<span style="color: #303030;">,</span> String text2<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">//1st method is to sort both strings and check one by one</span>
<span style="color: grey;">//sorting adds an complexity of nlogn (e.g. merge sort)</span>
<span style="color: grey;">//this code considers space, punctuation etc.</span>
<span style="color: grey;">//getChars method may also be used here</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">""</span><span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>text1<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">()</span> <span style="color: #303030;">!=</span> text2<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">())</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"inside isAnagram: "</span> <span style="color: #303030;">+</span> text1<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">()</span> <span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">" "</span> <span style="color: #303030;">+</span> text2<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">());</span>
<span style="color: green; font-weight: bold;">return</span> <span style="color: green; font-weight: bold;">false</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: #303030;">{</span>
String sorted1 <span style="color: #303030;">=</span> convertToCharArrayFromString<span style="color: #303030;">(</span><span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">,</span> text1<span style="color: #303030;">);</span><span style="color: grey;">// 1 is for sorted return </span>
String sorted2 <span style="color: #303030;">=</span> convertToCharArrayFromString<span style="color: #303030;">(</span><span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">,</span> text2<span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> i <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span> i <span style="color: #303030;"><</span> sorted1<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">();</span> i<span style="color: #303030;">++)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>sorted1<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">)</span> <span style="color: #303030;">!=</span> sorted2<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">))</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">return</span> <span style="color: green; font-weight: bold;">false</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">return</span> <span style="color: green; font-weight: bold;">true</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> String <span style="color: #0060b0; font-weight: bold;">convertToCharArrayFromString</span><span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> option<span style="color: #303030;">,</span> String text<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: #303090; font-weight: bold;">char</span><span style="color: #303030;">[]</span> content1 <span style="color: #303030;">=</span> text<span style="color: #303030;">.</span><span style="color: #0000c0;">toLowerCase</span><span style="color: #303030;">().</span><span style="color: #0000c0;">toCharArray</span><span style="color: #303030;">();</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>option <span style="color: #303030;">==</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
Arrays<span style="color: #303030;">.</span><span style="color: #0000c0;">sort</span><span style="color: #303030;">(</span>content1<span style="color: #303030;">);</span>
String sorted1 <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> String<span style="color: #303030;">(</span>content1<span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">return</span> sorted1<span style="color: #303030;">;</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: #303030;">{</span>
String unsorted1 <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> String<span style="color: #303030;">(</span>content1<span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">return</span> unsorted1<span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">boolean</span> <span style="color: #0060b0; font-weight: bold;">isAnagramMultiset</span><span style="color: #303030;">(</span>String text1<span style="color: #303030;">,</span> String text2<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">//requires basic knowledge of Multiset from guova libraries</span>
<span style="color: grey;">//may be implemented using pure JDK specifications</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>text1<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">()</span> <span style="color: #303030;">!=</span> text2<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">())</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">return</span> <span style="color: green; font-weight: bold;">false</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
Multiset<span style="color: #303030;"><</span>Character<span style="color: #303030;">></span> chars <span style="color: #303030;">=</span> HashMultiset<span style="color: #303030;">.</span><span style="color: #0000c0;">create</span><span style="color: #303030;">();</span>
String unsorted1 <span style="color: #303030;">=</span> convertToCharArrayFromString<span style="color: #303030;">(</span><span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">,</span> text1<span style="color: #303030;">);</span>
String unsorted2 <span style="color: #303030;">=</span> convertToCharArrayFromString<span style="color: #303030;">(</span><span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">,</span> text2<span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> i <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span> i <span style="color: #303030;"><</span> unsorted1<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">();</span> i<span style="color: #303030;">++)</span> <span style="color: #303030;">{</span>
chars<span style="color: #303030;">.</span><span style="color: #0000c0;">add</span><span style="color: #303030;">(</span>unsorted1<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">));</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> i <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span> i <span style="color: #303030;"><</span> unsorted1<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">();</span> i<span style="color: #303030;">++)</span> <span style="color: #303030;">{</span>
chars<span style="color: #303030;">.</span><span style="color: #0000c0;">remove</span><span style="color: #303030;">(</span>unsorted2<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">),</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">);</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"Multiset "</span> <span style="color: #303030;">+</span> chars<span style="color: #303030;">.</span><span style="color: #0000c0;">count</span><span style="color: #303030;">(</span>unsorted2<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">)));</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>chars<span style="color: #303030;">.</span><span style="color: #0000c0;">count</span><span style="color: #303030;">(</span>unsorted2<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">))</span> <span style="color: #303030;"><</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">return</span> <span style="color: green; font-weight: bold;">false</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">return</span> <span style="color: green; font-weight: bold;">true</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">findWordPosition</span><span style="color: #303030;">(</span>String text<span style="color: #303030;">,</span> String word<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
Map<span style="color: #303030;"><</span>String<span style="color: #303030;">,</span> ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">>></span> map <span style="color: #303030;">=</span> createInvertedIndex<span style="color: #303030;">(</span>text<span style="color: #303030;">);</span>
<span style="color: grey;">// for (Map.Entry<String, ArrayList<Integer>> entry : map.entrySet()) {</span>
ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">></span> position <span style="color: #303030;">=</span> map<span style="color: #303030;">.</span><span style="color: #0000c0;">get</span><span style="color: #303030;">(</span>word<span style="color: #303030;">);</span>
<span style="color: grey;">// System.out.println("Key " + entry.getKey() + entry.getValue());</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span>Integer value <span style="color: #303030;">:</span> position<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"Key: "</span> <span style="color: #303030;">+</span> word <span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">" its positions "</span> <span style="color: #303030;">+</span> value<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> Map<span style="color: #303030;"><</span>String<span style="color: #303030;">,</span> ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">>></span> createInvertedIndex<span style="color: #303030;">(</span>String text<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">//assume that text is given with appropriate</span>
<span style="color: grey;">//letters so no need for regular expressions</span>
<span style="color: grey;">//we can create a map with a key of String (each word) and</span>
<span style="color: grey;">//their positions that is integer array</span>
Map<span style="color: #303030;"><</span>String<span style="color: #303030;">,</span> ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">>></span> map <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> HashMap<span style="color: #303030;"><</span>String<span style="color: #303030;">,</span> ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">>>();</span>
String<span style="color: #303030;">[]</span> words <span style="color: #303030;">=</span> text<span style="color: #303030;">.</span><span style="color: #0000c0;">split</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">" "</span><span style="color: #303030;">);</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> i <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span> i <span style="color: #303030;"><</span> words<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">;</span> i<span style="color: #303030;">++)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>map<span style="color: #303030;">.</span><span style="color: #0000c0;">containsKey</span><span style="color: #303030;">(</span>words<span style="color: #303030;">[</span>i<span style="color: #303030;">]))</span> <span style="color: #303030;">{</span>
ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">></span> position <span style="color: #303030;">=</span> map<span style="color: #303030;">.</span><span style="color: #0000c0;">get</span><span style="color: #303030;">(</span>words<span style="color: #303030;">[</span>i<span style="color: #303030;">]);</span>
position<span style="color: #303030;">.</span><span style="color: #0000c0;">add</span><span style="color: #303030;">(</span>i<span style="color: #303030;">);</span>
map<span style="color: #303030;">.</span><span style="color: #0000c0;">put</span><span style="color: #303030;">(</span>words<span style="color: #303030;">[</span>i<span style="color: #303030;">],</span> position<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: #303030;">{</span>
ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">></span> position <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> ArrayList<span style="color: #303030;"><</span>Integer<span style="color: #303030;">>();</span>
position<span style="color: #303030;">.</span><span style="color: #0000c0;">add</span><span style="color: #303030;">(</span>i<span style="color: #303030;">);</span>
map<span style="color: #303030;">.</span><span style="color: #0000c0;">put</span><span style="color: #303030;">(</span>words<span style="color: #303030;">[</span>i<span style="color: #303030;">],</span> position<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">return</span> map<span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> Set<span style="color: #303030;"><</span>Character<span style="color: #303030;">></span> removeDuplicateChars<span style="color: #303030;">(</span>String text<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: grey;">// for insertion sort order LinkedHashSet is used</span>
Set<span style="color: #303030;"><</span>Character<span style="color: #303030;">></span> set <span style="color: #303030;">=</span> <span style="color: green; font-weight: bold;">new</span> LinkedHashSet<span style="color: #303030;"><</span>Character<span style="color: #303030;">>();</span>
<span style="color: green; font-weight: bold;">for</span> <span style="color: #303030;">(</span><span style="color: #303090; font-weight: bold;">int</span> i <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span> i <span style="color: #303030;"><</span> text<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span><span style="color: #303030;">();</span> i<span style="color: #303030;">++)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(!</span>set<span style="color: #303030;">.</span><span style="color: #0000c0;">contains</span><span style="color: #303030;">(</span>text<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">)))</span> <span style="color: #303030;">{</span>
set<span style="color: #303030;">.</span><span style="color: #0000c0;">add</span><span style="color: #303030;">(</span>text<span style="color: #303030;">.</span><span style="color: #0000c0;">charAt</span><span style="color: #303030;">(</span>i<span style="color: #303030;">));</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: green; font-weight: bold;">return</span> set<span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
</pre>
</div>
BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0tag:blogger.com,1999:blog-5846588745367323077.post-48858886333919292182012-07-18T16:41:00.001-07:002012-08-10T04:47:49.277-07:001- (Array question) Given an integer array, output all pairs that sum up to a specific value k.You may want to check the original post with more comprehensive explanation from <a href="http://www.ardendertat.com/2011/09/17/programming-interview-questions-1-array-pair-sum/" target="_blank">here</a>.<br />
<br />
<div style="background: #ffffff; background: white; border-width: .1em .1em .1em .8em; border: dashed gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="font-family: Georgia, 'Times New Roman', serif;"><span style="color: grey;">/*</span>
<span style="color: grey;"> * Given an integer array, output all pairs that sum up to a specific value k.</span>
<span style="color: grey;"> */</span>
<span style="color: green; font-weight: bold;">package</span> pkg1arraypairsum<span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">import</span> <span style="color: #0e84b5; font-weight: bold;">java.util.Arrays</span><span style="color: #303030;">;</span>
<span style="color: grey;">//Non-static method cannot be referenced from a static context</span>
<span style="color: grey;">//requires an instance of the X class in order to call it</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">class</span> <span style="color: #b00060; font-weight: bold;">Main</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">int</span> currentSum<span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">main</span><span style="color: #303030;">(</span>String<span style="color: #303030;">[]</span> args<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
Integer<span style="color: #303030;">[]</span> array <span style="color: #303030;">=</span> <span style="color: #303030;">{</span><span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">3</span><span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">2</span><span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">12</span><span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">4</span><span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">5</span><span style="color: #303030;">};</span>
<span style="color: #303090; font-weight: bold;">long</span> lStartTime <span style="color: #303030;">=</span> System<span style="color: #303030;">.</span><span style="color: #0000c0;">nanoTime</span><span style="color: #303030;">();</span> <span style="color: grey;">//start time</span>
pairSum<span style="color: #303030;">(</span>array<span style="color: #303030;">,</span> <span style="color: #0000d0; font-weight: bold;">6</span><span style="color: #303030;">);</span> <span style="color: grey;">//method execute</span>
<span style="color: #303090; font-weight: bold;">long</span> difference <span style="color: #303030;">=</span> System<span style="color: #303030;">.</span><span style="color: #0000c0;">nanoTime</span><span style="color: #303030;">()</span> <span style="color: #303030;">-</span> lStartTime<span style="color: #303030;">;</span> <span style="color: grey;">//check difference</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span><span style="background-color: #fff0f0;">"Elapsed value of the most precise available system time: "</span> <span style="color: #303030;">+</span> difference<span style="color: #303030;">);</span>
<span style="color: #303030;">}</span>
<span style="color: grey;">//Complexity: O(NlogN)</span>
<span style="color: green; font-weight: bold;">public</span> <span style="color: green; font-weight: bold;">static</span> <span style="color: #303090; font-weight: bold;">void</span> <span style="color: #0060b0; font-weight: bold;">pairSum</span><span style="color: #303030;">(</span>Integer<span style="color: #303030;">[]</span> array<span style="color: #303030;">,</span> <span style="color: #303090; font-weight: bold;">int</span> k<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>array<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span> <span style="color: #303030;"><</span> <span style="color: #0000d0; font-weight: bold;">2</span><span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
<span style="color: green; font-weight: bold;">return</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
Arrays<span style="color: #303030;">.</span><span style="color: #0000c0;">sort</span><span style="color: #303030;">(</span>array<span style="color: #303030;">);</span>
<span style="color: #303090; font-weight: bold;">int</span> left <span style="color: #303030;">=</span> <span style="color: #0000d0; font-weight: bold;">0</span><span style="color: #303030;">;</span>
<span style="color: #303090; font-weight: bold;">int</span> right <span style="color: #303030;">=</span> array<span style="color: #303030;">.</span><span style="color: #0000c0;">length</span> <span style="color: #303030;">-</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">;</span>
<span style="color: green; font-weight: bold;">while</span> <span style="color: #303030;">(</span>left <span style="color: #303030;"><</span> right<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
currentSum <span style="color: #303030;">=</span> array<span style="color: #303030;">[</span>left<span style="color: #303030;">]</span> <span style="color: #303030;">+</span> array<span style="color: #303030;">[</span>right<span style="color: #303030;">];</span>
<span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>currentSum <span style="color: #303030;">==</span> k<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
System<span style="color: #303030;">.</span><span style="color: #0000c0;">out</span><span style="color: #303030;">.</span><span style="color: #0000c0;">println</span><span style="color: #303030;">(</span>array<span style="color: #303030;">[</span>left<span style="color: #303030;">]</span> <span style="color: #303030;">+</span> <span style="background-color: #fff0f0;">" "</span> <span style="color: #303030;">+</span> array<span style="color: #303030;">[</span>right<span style="color: #303030;">]);</span>
left <span style="color: #303030;">+=</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">;</span><span style="color: grey;">//or right-=1;</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: green; font-weight: bold;">if</span> <span style="color: #303030;">(</span>currentSum <span style="color: #303030;"><</span> k<span style="color: #303030;">)</span> <span style="color: #303030;">{</span>
left <span style="color: #303030;">+=</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span> <span style="color: green; font-weight: bold;">else</span> <span style="color: #303030;">{</span>
right <span style="color: #303030;">-=</span> <span style="color: #0000d0; font-weight: bold;">1</span><span style="color: #303030;">;</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: #303030;">}</span>
<span style="color: grey;">// is it possible to reduce the complexity O(N)?</span>
<span style="color: grey;">// Yes</span>
<span style="color: #303030;">}</span></span>
</pre>
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5DtWCZJE3rCCarhlNw7KE6YC18qTxkAivLisKx7uG8I68lgLY7KVgbd-Lzgm5F7RUdqvVxNwALyAC8ZWfxdRpybs9HU25YyKH3ekp2G67JxdB5pLviSrUua2LgKypeV-N0Zam7g7-8o1f/s1600/pairsum.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="71" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5DtWCZJE3rCCarhlNw7KE6YC18qTxkAivLisKx7uG8I68lgLY7KVgbd-Lzgm5F7RUdqvVxNwALyAC8ZWfxdRpybs9HU25YyKH3ekp2G67JxdB5pLviSrUua2LgKypeV-N0Zam7g7-8o1f/s400/pairsum.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Output</td></tr>
</tbody></table>
<br />BekoChttp://www.blogger.com/profile/01084337785008277396noreply@blogger.com0