Interesting C++ Notions

Hey there!

Been really busy with coding and projects these past few days so no updates. But I have learned a lot of cool new stuff which I now wish to share with you.

Let’s dive in: I am guessing you remember what a stringstream is? If you don’t, there is an old post that I have explaining its super-utility. Once you can get your head wrapped around it, one interesting thing to note is how to clear the stream. On careful scrutiny of the API, you find it has 2 methods, flush() and clear(), which you may think might get the job done. Well, turns out both are quite misleading. The flush() command is actually used to synchronize the stream buffer so that it writes any unwritten characters on the next opportunity it gets, and the clear() command is actually used to reset the flag bits associated with the stream. Thus, none of them achieve our basic objective of clearing the stream.

The answer is actually in the constructor. The str() method is the way to go. Simply call ss.str(“”) and ss.clear() to reset any fail bits (where ss is my stringstream variable), and there you have it.

Another neat trick is that of manipulator functions. We use endl when dealing with cin and cout. Turns out, you’ve been using a manipulator function all along. Other uses include printing decimals in scientific notations and changing the base of your output/input.

Probably the most useful of all the ideas here is the use of a comparator function in the sort function. The template of sort() is sort(start_iterator, end_iterator, comparator_func) and we don’t usually use this form simply because of the awesome overloaded capabilities of the sort() function. However, this form gives us greater control over our execution and I have personally used innumerable times.

The comparator function takes 2 parameters of the same type as the list to be sorted. We return true if the first parameter goes before the second and false otherwise. Thus, this allows us to define the comparison criteria for user types like classes and structs. :-D

A final trick that I would like to mention is the transform function. A handy tool for performing various transformative operations on lists, the most basic being changing the case of strings. This one needs some memory to remember the manipulator functions, but I am sure you can handle it.

Hope this helps you write more succinct, poignant code in the future.

Till then, eviva!

2012
05/09
POSTED BY
CATEGORY
Coding
Computer Science
TAGS


Write comment

Project Euler 58 : The Ulam Spiral

Alrighty! Back to Project Euler after a really long time and the difference is pretty noticeable, both in PE as well as my thinking.

PE’s got a new interface and an awesome new badge system for would-be Eulerians. However the cooler thing is that I was able to solve a problem that initially gave me many a sleepless night.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36   35   34  33  32  31
38 17   16   15  14  13  30
39 18    5     4    3    12  29
40 19    6     1    2    11  28
41  20   7     8    9    10  27
42  21  22   23  24  25  26
43  44  45   46  47  48  49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Pretty harrowing at first glance, but the solution is really straightforward. :-)

This spiral is nothing but the Ulam Spiral and it has some interesting properties. Notice the left-down diagonal has all squares? The square value is simply twice the spiral layer plus 1 squared. So the first layer i.e. 1 gives (2*1 + 1)^2 = 9. Then the other 4 values are obtained by subtracting the previous even number’s 3 multiples from the square.

E.g. Take 49. That is the square of 7, 6 is the even number before it. So to get the other diagonal elements, all I do is 49 – 6, = 43, 49 – 12 = 37 and 49 – 18 = 31. This simple pattern works all the time for every layer, feel free to check!

Now, the code to solve this is even simpler. C++ can do this, but finding the range of prime numbers is a big hassle and I couldn’t find a good enough upper bound to apply The Sieve without getting a Segmentation fault, and too large values just can’t be accommodated.

Thankfully, I learnt Python this last semester while doing the coursework of an online Robotics class by Prof. Thrun. So, I decided to write a terse program to achieve the solution. Here it is:

from math import *

def isprime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    for x in range(3, int(n**0.5)+1):
       if n % x == 0:
           return False
    
    return True;


def calculate():
    primes = 3
    count = 5
    layer = 1

    while float(primes)/count >= 0.1:
        layer += 1
        m = 2*layer + 1
    
        for i in range(4):
            if isprime(m*m - i*(m-1)):
                primes += 1
            count += 1

    return 2*layer + 1

print calculate()

So I hope you understand what I am trying to do. The code is short and sweet and pretty self-explanatory, except, for the sake of the while loop, I am starting from the first layer rather than the zeroth layer which only has 1.  Now I better get back to my other programs!

Eviva!

2012
04/22
POSTED BY
CATEGORY
Coding
Mathematics
TAGS

Write comment

TinyOS Installation Made Easy

Howdy people! Long time since a post but couldn’t help it, busy being a busybee.

Well, I have started a project on Wireless Sensor Networks and the best way to go about it has been using an amazing operating system called TiinyOS. This OS is so tiny, it uses only 400 kb of memory to run! Holy Cow!!

But getting TinyOS on 64-bit machines hasn’t been well documented and I assume that lack of documentation brought you here. Well no fear, I will be showing a stepwise guide to getting TinyOS up-and-running on any 64-bit machine you have.

Note: I am using Ubuntu 11.10 64-bit as my host operating system, but the method should work on all distros of Linux.  If you’re using Windows, may God have mercy on your soul. Also, this post involves installing TinyOS 2.1.1. I cannot guarantee that all the steps will work as is for other older versions. You’ll have to do some research for that.

Step 1:

First up, we need Java, the JRE and the JDK as a lot of the TinyOS and Mote communication framework is built in Java. You can use the OpenJDK but I have found using Sun’s original JDK yields better results!

Open up a terminal and simply type in these commands to get the JRE and JDK installed in your machine.

sudo apt-get install python-software-properties
sudo add-apt-repository ppa:ferramroberto/java
sudo apt-get update
sudo apt-get install sun-java6-jdk sun-java6-plugin

Step 2:

Now that we have our environment setup, we are ready to install the TinyOS development environment.

  1. Install the Synaptic Package manager by running “sudo apt-get install Synaptic” in a terminal.
  2. In Synaptic, go to Settings ->Repositories.
  3. Click on 3rd party software and add the following (simple copy-paste):
    deb http://tinyos.stanford.edu/tinyos/dists/ubuntu * main
  4.  Click OK and reload your repositories.
  5. After reloading, simply search for TinyOS and select it. Click install and allow Synaptic to handle dependency installation for you.
  6. Once the packages have been properly installed, go back to a terminal and type “sudo gedit ~/.bashrc” and add this line at the absolute end:
                         source /opt/tinyos-2.1.1/tinyos.sh
  7.  Finally, close the current terminal and open up a new one and type in $MAKERULES. If all went well, you should get the path.

Congrats, we have TinyOS ready. But we’re not done yet!

Step 3:

Now, when writing TinyOS programs, you’ll very much want to simulate them to see what are the results. A very handy tool for TinyOS simulation is TOSSIM. But when you run the make micaz sim to generate your executable you might get a Python related error. Try these steps:

  1. In a terminal, run sudo apt-get install python-dev.
  2. Even after installing python, some configuration is required.
  3. Run python –version  and note the version of Python installed. In my case, it was 2.7.
  4. Go to /opt/tinyos-2.1.1/support/make/
  5. Open the sim.extra file in gedit with super user privileges.
  6. In the entry labelled PYTHON_VERSION, check to see if the entry matches with the Python version installed. For me, it was 2.6, so I changed it to 2.7.
Python Configuration

The Python version entry to be edited

Step 4:

As the final step, this involves some minor configuration to your tinyos.sh file found in /opt/tinyos-2.1.1. This is done so that when you run the make micaz sim command to generate TOSSIM related files, the appropriate Java classes are generated to help in the simulation. Otherwise you’ll get a long list of errors that will make no sense at all.

Editing the tinyos.sh file makes the change permanent which is exactly what you need. Simply go to the directory in which the tinyos.sh file is located (given in the start of  this step).

Open the tinyos.sh file in gedit with super user privileges. There is an entry called CLASSPATH. Simply edit the original to $TOSROOT/support/sdk/java/tinyos.jar, similar to how it is in the image.

CLASSPATH Edit

Change to CLASSPATH entry in tinyos.sh file

And voila!! You’re done and ready to start writing some incredible TinyOS code.

I hope this blog entry has been useful to you. For any doubts or problems, the TinyOS mailing list is a great place filled with really helpful people and I highly recommend posting both newbie and advanced doubts there.

Till next time, Eviva!

———————————————————————————————————————————
P.S. These are some of the links I used to get TinyOS up and working. Thought they might be useful for the future:

http://superuser.com/questions/353983/how-do-i-install-the-sun-java-sdk-in-ubuntu-11-10-oneric
http://mythicalcomputer.blogspot.in/2008/08/installation-of-tinyos-in-ubuntu.html
http://mail.millennium.berkeley.edu/pipermail/tinyos-help/2011-October/052537.html
https://www.millennium.berkeley.edu/pipermail/tinyos-help/2010-November/048947.html

2012
03/09
POSTED BY
CATEGORY
Computer Science
Linux
TinyOS
TAGS



2 comments

Crypto Cracking

Well, round 2 of InCTF 2012 was a blast! There was lots to do and considering that 2 of my team-mates had very limited internet access, I had to do quite a lot of heavy-lifting.

The challenges were fun and varied, ranging from Reverse-Engineering to Website Hacking. But the category that elicited the most interest from me was the Cryptography challenge. Having an old love affair with puzzles and ciphers, I got cracking.

Sadly, I do not have the questions with me as the 2nd round portal has been deactivated, however I can easily explain the concept to cracking them.

The premise was that you are a decoder in a top-secret intelligence agency that has an agent who has infiltrated a dangerous terrorist outfit. The agent’s job is to relay encrypted terrorist messages to you and our job is to decode the message and save the world.

In the first question a.k.a. the 1st transmission, we were given the encrypted message and our job was to find the location of the next meeting place of the Terrorist leaders. Well, you might’ve played this game in the newspapers that involves deciphering a message by substituting characters and looking for common words and patterns in order to figure out the cipher, that was the stratagem I applied. Finally on closer inspection, you realize the cipher is pretty simple:

“Each alphabetic character has been replaced by its numerical equivalent from the reverse alphabet, i.e. if a=1, b=2..z=26, then in the encrypted message you’ll have a=26,b=25..z=1.”

So all I had to do was write a program to manipulate the ASCII values such that whatever character I was reading, I would substitute it with 26-(ASCII value of character) and thus print out the complete legible message.

Question 1: CRACKED!

The second question was even easier than the first, on account of the hint mentioning that the agent had used a DVORAK keyboard to type the message. Simple patter recognition will tell you that all the Capital letters are conforming to the QWERTY keyboard whereas all lower-case characters have been typed using a DVORAK board but with a QWERTY board in mind. So it was simply a physical translation of keys. :-)

Immediately fired up Wikipedia and got the layout of the DVORAK keyboard. This allowed me to do the translation in a matter of minutes. Ofcourse, I did not decipher the whole message, just the location of the next meeting.

Question 2: CRACKED! Feeling good.

Sadly, that is where the good feeling lasted till. The next two questions were supposedly easy, but since the cryptographical code was written in Python, I could not make heads or tails of what the code was doing. And since I had never worked on Python, I didn’t even have a clue as to how to run the darn code. :-P

Well, no issues. I did my part, with my team managing a rank of 16 in the 2nd round. Now looking forward to the 3rd round and some serious Flag-Capturing!!

Eviva! :-D

2012
01/29
POSTED BY
CATEGORY
Coding
Computer Science
TAGS

Write comment

Breaking Into Linux

Let’s get this straight: This is just a tutorial for a competition I am participating in called India Capture The Flag or InCTF for short. I do not like, nor do I endorse cracking of other people’s systems and/or stealing of private and confidential data. I believe in building stuff, not tearing down things like password-protections.

Now that the disclaimer is out of the way, let’s do this!

There’s a really easy way to hack (or what I prefer to call “crack”) a person’s Linux machine, even if they have a Grub password in order to prevent someone from editing the files on their filesystem and getting access to their machine.

And all it needs is a Live CD. Any distro should do but generally people prefer to use the Live CD of the same distro they are trying to crack into.

Just insert the live CD into your disk tray and reboot the system, making sure that booting from disk is at a higher priority that booting from hard-drive. Then, on boot-up, select “Try Live CD without any change” and enter into the Live boot.

The first thing you should do is what every Linux lover does: Run the Terminal. Type into the terminal “sudo fdisk -l” to list out all the active drives in your system. You should be able to see which disk is the one that is being used as the primary one by the original Linux installation. Make sure you note down this drive. For this hack, we’ll assume it to be /dev/sda1.

Now comes the easy part. Having obtained the path to the primary disk partition, we create a folder/directory using “mkdir /media/temp”. Since this is a live boot, this file is not created on your hard-drive, just your RAM. Still not breaking anything.

This is where it gets interesting. We now mount the primary drive to our temporary folder, thus effectively creating a logical connection between the two. Just type “sudo mount /dev/sda1 /media/temp” into the terminal and we’re done.

Finally!! We’ve done all the preparation. We’ve stalked our prey like the merciless hunters we are. It’s now time to go in for the kill. Runnig “sudo chroot /media/temp” creates a shell with a different root directory, and passing /media/temp as the parameter gives us our primary partition as that new filesystem. So any changes now made in this shell, will be reflected directly in the primary partition. OH YEAH!!

Now it’s just a trivial matter of running “sudo passwd” to change our password to the desired one. Then all we have to do is reboot, and we’ll have complete control over the machine.

Congratulations! You are now a Linux Hacker.

Eviva!

2012
01/15
POSTED BY
CATEGORY
Linux
TAGS




Write comment

Tweaks To Suit Your Style

Alrighty people! I now have Ubuntu 11.10 aka Oneiric Ocelot on a Mactel laptop and I am totally relishing the computing experience.

However, it seems the MacBook has some quirks while running Ubuntu, namely to make use of function keys, I have to couple them with the fn key, else I end up adjusting my LED brightness or sound levels! Also, my left internal speaker had gone dead for some odd reason!!

But as Geoff Johns says, “no fear”, as I was working on Linux. :-)

To use the function keys without having to press the fn key, simply run the following commands:


$sudo -i
$echo 2 > /sys/module/hid_apple/parameters/fnmode

That was a temporary fix. A more permanent fix is this one:

$ echo options hid_apple fnmode=2 | sudo tee -a /etc/modprobe.d/hid_apple.conf
$ sudo update-initramfs -u
$ sudo reboot

And on restart, you’ll have your Function keys working just the way you’d want them to.

To fix the speaker problem, just install a little tool called GNOME AlsaMixer by running the command

sudo apt-get install gnome-alsamixer

Then go to the Alsa Mixer, unmute the Surround Sound and bring it up to max and we’re good to go! :-D

As a final tweak, installing the Gnome3 desktop is always a great idea, so just run

sudo apt-get install gnome-shell

and enjoy the Gnome experience!

Eviva!

2012
01/05
POSTED BY
CATEGORY
Coding
Linux
TAGS



2 comments

Semester V of Computer Science

Ah. Another semester gone by and another treasure trove of knowledge discovered and assimilated.
This was semester V and what a semester it was. We finally dove right into core Computer Science and Engineering with the following awesome sujects:

  • Algorithm Analysis and Design
  • Microprocessor Interfacing Techniques
  • Principles of Programming Languages
  • Computer Networks
  • Computer Graphics

Truly great subjects for a Computer Science major to undertake. So let’s dissect them and see what it meant to study these topics.

1. Principles Of Programming Languages
A subject which involves the study of various programming paradigms so that one understands what are the benefits of the multitude of features being introduced in Programming Languages on a daily basis, so that we can understand the motivation behind it as well as better use it in our program design. Sadly, marred by not-so-good teachers who decided they would teach us C++ and Prolog programming rather than cool concepts like the Liskov Substitution Principle.

2. Microprocessor Interfacing Techniques
A fundamental and challenging subject, it made us truly think about the Simplicity vs. Efficiency Model of programming. Learning about the underlying hardware that controls our machines and lets you see this text here, was simply great. Read about the PS3 Cell Broadband Engine after taking this course and found that I was really able to understand all the hardware jargon on the page. All in all, 8085 and 8086 coding was FUN!

3. Computer Networks
A genuine rote subject made interesting by the fervour and enthusiasm of the faculty, this subject stands as a fine example of how great education can be undertaken provided the teacher has the motivation for it. Initially not a fan of Computer Networks due to the mugging tendency of the subject, was thrilled to see how succinctly all the various protocols and their algorithms were presented in a manner that was perfectly logical. Doubts were effortlessly quelled and the various abstractions used just made the learning curve gentler. Coupled with some great laboratory sessions (the teacher actually wanted to do a lot more), this subject became one of my learning high-points this semester.

4. Computer Graphics
A subject with a bad reputation for having outdated curriculum, I took it because the faculty in charge of it was going to revamp the topics and introduce us to OpenGL. Started great, awesome practical submissions and fun classes. Got a little drab in the middle because of redundant topics like Matrices and Vector Geometry as these had already been taught in High-School Maths. In the end, it was a good introductory class to the magical world of Computer Graphics.

5. Algorithm Analysis and Design
Saved the best for the last. My favourite subject of the semester as it coupled pure Computer Science and Mathematics to form a foundation for Computing everywhere. I already had good algorithm skills thanks to all those hours poured in Project Euler and UVa Toolkit, but this course really cleared my head and gave me the tools to really understand just what the heck I was coming up with. Intuitive solutions were given names and ideas were presented as theorems. Various problem-solving approaches helped me understand how to better analyze and tackle problems and applications were given as much importance as the concepts themselves. Someone once famously sayed, “To be a great coder, you can either write codes for ten years or take a semester-worth course on Algorithms”. Guess I saved myself 9 years of pain. :-P

Thus, great semester, lots of nice topics, finally got some Computer Science and Engineering done. Let’s hope the new semester is as much enthralling as this one.

Eviva!

2011
12/22
POSTED BY
CATEGORY
Algorithms
Coding
College
Computer Science
Graphics
TAGS




Write comment

Soothsayer

I and a bunch of guys at my college decided to take part in the Atos IT Challenge and try to win ourselves a trip to the UK for the 2012 London Olympics, the theme being Smart Mobility.

Our college was one of the lucky ones to have been selected to participate in this contest and I can see the competition from my institute itself, if not the entire world, is pretty nerve-wracking.

My team consists of Arth “Vyarth” Patel, Nimit “Lame-it” Shah, Sunny “Not Funny” Shah, Jigar “The Dafda” Dafda and Yours truly.

Having vetoed the original idea for a mobile disaster management system, I suggested a smart app that can mine and learn from the User’s history, match that with the current trends in the world and filter it with his/her geo-location to give the User some truly meaningful information that is highly relevant to their current situation, with all the data-crunching taking place on the Cloud.

This competition gives us a great opportunity to learn about a new field, Mobile Computing, a new platform, and also a chance to practice some of the AI techniques we’ve picked up in the past few months. But the biggest plan is to possibly Patent our idea. That would be TOTALLY COOL :-D .

Our idea page is here. If you liked our idea, please don’t hesitate to click on the FaceBook Like Button.

Now let’s hope the judges deem our idea worthy of selection so we can make it into the next round and begin the development stage.

Eviva!

2011
12/07
POSTED BY
CATEGORY
AI
Cloud Computing
College
Machine Learning
Mobile Computing
People
Software
TAGS


Write comment

Cloud Conclave 2011

The weekend of 18-20th November was awesome!!! I had taken part in this contest called “What’s Your Cloud Idea” conducted by Amazon (Yes, the Amazon.com Amazon) and YourStory.in. The contest was for students from all over India and it involved coming up with an innovative idea to use Cloud Computing. Now being a Computer Science Major, I took part and even though the idea was pretty lame in my eyes, apparently, the guys at Amazon loved it and I was thus invited to Cloud Conclave 2011 at the Indian Institute of Management, Bangalore where I was to be felicitated by the CTO of Amazon, Dr. Werner Vogels himself! :-D

Now for why the weekend was awesome. For starters, this was going to be my first technical conference ever since I started College . Secondly, I was travelling to a place which was more than 1000 kms away from my current location, all alone. And finally, I was going to meet my cousin brother Shobhit (who’s studying in IIM-B) and some of my friends from college who were working in Bangalore.

The journey was brilliant! I had to skip a day of college in order to make it there. I caught a train on the eve of the 17th and was at home in Mumbai by nightfall. Next day, frantic packing and prep for the flight to Bangalore. By 1:00, I was at the domestic terminal, making my way to security check, and enjoying every moment of it! The flight was full of people who looked like they were returning from some form of business meeting. Heck, even the guy on the seat next to mine was working on his laptop before take-off (I am suspicious he worked for Renault).

I made it to Bangalore by around 5. Thanks to my father, a vehicle and accommodation had been arranged for. And thank God for that! Bangalore is a complete and utter mess when it comes to traffic. It took me a good 2 hours just to cover 20-25 kms!!

The climate was great however. It was pleasantly cool and seeing the tech capital of India was an adventure in itself.

Now about Cloud Conclave: The morning before it started, I met up with an old friend, Sanchit Suman and we had lunch together at KFC and relived the old times we had when we were both in college. After that, I picked up a great senior and friend, Prakhar Gupta (who is an engineer at Microsoft!), and we made our way to the Conference.

We made it to IIM-B with plenty of time to spare and I was awestruck at its beautiful campus. I rang up my brother and met up with him. He was kind of busy due to an Alumni meet, and thus asked to call him after I was done. We made our way to the Auditorium, where tonnes of others in suits were registering themselves. After a little chat with one of them, turns out most of the people there were professionals and I was seemingly the youngest there.

The conference started late (Dr. Werner was stuck at traffic :–P), but once it did, it was really brilliant! The keynotes by Dr. Werner and Dr. Vaidya Nathan really showed us how leveraging Cloud Computing could really carry forward our projects and businesses, how we could minimize error costs and how Cloud provided a level of ease in scaling and security that was tough to achieve anywhere else. The Q&A was the best part as the crowd asked some really interesting questions which were answered adeptly by Dr. Werner, Dr. Nathan and Shailendra Singh of Sequoia Capitals. Really informative and mind-expanding stuff here!! Here‘s a great piece that summarizes the keynote in a very crisp manner.

Finally, once it was over, I met Rutayan Patro and Tapan Deka, more friends from college and with brother Shobhit, we went for a guided tour of the campus where one of my favourite movies, “3 Idiots” was shot. We took some great snaps at the landmarks of the institute and had a great little evening walk.

Finally, the day had come to an end. We bid our goodbyes, promised to do something like this again, and made our way to our respective destinations.

The next morning was again frantic, in the sense that I had an 8:00 flight, so I had to leave the guest house by 6:30. Left in time, made it on time, boarded my flight, reached home, caught the evening train to Surat, and was greeted with cheers from my friends!

The weekend really was one of the best! :-D

P.s. For more about my idea, please go here.

2011
12/05
POSTED BY
CATEGORY
Cloud Computing
College
People
TAGS



Write comment
Follow

Get every new post delivered to your Inbox.

Join 873 other followers