Learning Algorithms with “Introduction to Algorithms”


I’ve been reading “Introduction to algorithms, third edition” (on Lorenzo‘s recommendation), its a massive book but I’m making my way through it. A bit pricey but definitely worth it, and would recommend it to anyone who has an interest in algorithms. While going through the first few chapters I realised I was lacking on some of the mathematics required, thankfully the appendix covers the math you need. I’ve decided to do a series of posts on the stuff in the appendix to help me remember it all and hopefully help others as well. I’ll try to be as accurate as possible but I’m learning this as I go along so it wouldn’t be a bad idea to double check that I am in fact doing things right. Read more of this post

Archimedean Spiral – “Plug a bit of maths in and ‘magic’ will happen!”


After looking at a few options for placing stuff in an outward spiral I came across the Archimedean Spiral. I’m rendering my items on an HTML5 canvas so this is all being done in Javascript. After implementing it I started to play around with the values a bit and produced some very interesting effects. Below are two of my favorites…

Mind you this is being done with part-finished code so it may not even be a good way of achieving it but it did the trick and I thought I’d post it before the code morphs into something far beyond what’s necessary/needed for this.


The little Javascript/HTML snippet that does this is:

        <canvas id="tags" width="1200" height="600"></canvas>     
        <script type="text/javascript">

            window.onload=function(){
                var c = document.getElementById('tags');
                var context = c.getContext("2d");
                var halfx = context.canvas.width / 2;
                var halfy = context.canvas.height / 2;


                context.clearRect(0, 0, 300, 300);

                context.moveTo(halfx, halfy);
                context.beginPath();
                //check if both the max X and Y edges have been reached
                var Xmaxxed=false,Ymaxxed=false;
                var i=0;
                while(!Xmaxxed||!Ymaxxed){
                    var x = i*0.1 * Math.cos(i);
                    var y = i*0.1 * Math.sin(i);
                    x=x+600;
                    y=y+300;
                    if(x>=c.width){
                        Xmaxxed=true;
                        console.log(["xMaxxed",x,y]);
                    }
                    if(y>=c.height){
                        Ymaxxed=true;
                        console.log(["yMaxxed",x,y]);
                    }
                    console.log(["Attempt "+i,x,y]);
                    context.lineTo(x, y);
                    i+=1;
                }
                context.strokeStyle = "#000";
                context.stroke();

            }
        </script>

Well, that's it, play around with the two lines
var x = i*0.1 * Math.cos(i);
var y = i*0.1 * Math.sin(i);
and see what effects you can come up with, I'd be interested to see more...

Implementing the Bubble sort algorithm in J2ME


A friend asked me two days ago how to implement a sort algorithm on J2ME…
Never used the J2ME API but I thought, hey, can’t be that bad right. I must say, after seeing the primitive nature of J2ME I don’t think I would or even could do mobile dev. with that API. It’d drive me insane. In any case, I figured out a quick way of sorting an array of names in alphabetical order… Read more of this post

Algorithm to swap the values of two variables without using a temporary variable


In a recent interview, I was asked whether or not it would be possible to swap the contents of two variables without using a temporary variable of any sort.

The scenario, given two variables X,Y where X=5 and Y=3; Swap the contents of the variables such that,
outputting X produces the value 3 and outputting Y produces the value 5. Your algorithm must only use the two variables
X and Y and you’re allowed to perform any Mathematical operation on them to achieve the desired results.

What I came up with worked…sort of (that was on the fly without much time/thought). After thinking about the algorithm I came up with below achieves this using only the two variables by using addition and subtraction. (The below solution is an extension of what my original answer was).

The Java program (works in any language,easily translated)


/**
 *
 * @author Courtney
 */
public class Test {

    public static void main(String... args) {
        int y = 3;
        int x = 5;
        System.out.println(&quot;Original X and Y Value&quot;);
        System.out.println(&quot;Y : &quot; + y);
        System.out.println(&quot;X : &quot; + x);
        //add X on to Y so that we can take it off again later
        x = x + y;
        /**
         * We want to get the original X value into Y
         *we now know that sum(x)=x+y
         *therefore remove y =&gt; (x-y)
         */
        y = x - y;
        /**
         * At this point we know that the original X value is stored in Y,
         * we also know that X's value is x+y i.e. sum(x)=x+y
         * and we want X to get Y's original value so remove X's original
         * value and we're left with Y's original value
         */
        x = x - y;
        System.out.println(&quot;Swaped X and Y Value&quot;);
        System.out.println(&quot;Y : &quot; + y);
        System.out.println(&quot;X : &quot; + x);
    }
}

The output from the program should be:

Original X and Y Value
Y : 3
X : 5
Swaped X and Y Value
Y : 5
X : 3

Never thought about doing this before so I was caught completely off guard when asked...didn't even know it was
possible until I was asked... Hope it helps

Follow

Get every new post delivered to your Inbox.

Join 1,385 other followers

%d bloggers like this: