Saturday, November 26, 2005

Thoughts on Science and Engineering

I think of myself as a little bit of a researcher. Being a researcher requires me to read journal papers and to try and understand them the best I can. I have a degree in Computer Science and Engineering.

So, the question keeps popping up -- "What is the difference between Science and Engineering?"
Well, here is my understanding so far (not complete yet)

Science
  1. It is very theoretical
  2. It relies on abstraction and the ability to visualize things
  3. Proofs (mathematical) are important for completeness

Engineering

  1. Relies on Science for getting started and for establishing a base for understanding concepts
  2. Is more practical in the sense that ideas should be feasible to implement. Science will allow you to get away with black holes and infinity, engineering will not
  3. It is the art of observing and collecting data and using it to solve problems

To illustrate the difference further, consider the mathematical concept of infinity, mathematics has a notation for it ∞. In computing, we cannot get away without finding a practical representation for infinity, hence computer engineers had to develop the concept of NAN (Not A Number), but in science we can simply use the notation for ∞.

Collecting data also plays a critical role in keeping things practical, analyzing data to come up with solutions to problems is very important in engineering.

There are occasions when science and engineering work very well together. Consider for example the Huffman algorithm, science predicts that it the most optimal algorithm for finding codes and engineering allows us to implement it. On the other hand, in the case of traveling salesman problem, science suggests that there is no way to design the most optimal solution to the problem except to use brute force, but engineers try to find a solution that is close to optimal.

Get the point - science vs engineering?

Thursday, November 17, 2005

Data Structure Patterns

Teaching and books have a profound impact on how we think and solve problems.

In college when I learnt data structures, I was taught to embed the element in the data structure (list)


struct x {
struct x *next, *prev;
int element;
};


But I soon realized that I did not always want "int" as the type of the element, so I learnt the magical type void *

Here is another way to achieve the same thing


struct list {
struct list *next, *prev;
};

struct y {
int element;
struct list l;
};


This way, I could embed the list in anything without building any type information in list. Cool right?

If tomorrow I decided to use a tree, I could simply change


struct y {
int element;
struct tree t;
};


This way the impact on my code for "y" is minimal. In the traditional approach, I would have to use


struct tree xt {
int element;
struct tree *left, *right;
};


and redo most of the code.

The moral of the story

Embed the data structure in the data type and not the other way around





Figure illustrating the differences b/w embedding the data type in the data structure versus embedding the data structure in the data type

Tuesday, November 08, 2005

First example of using scilab

I tried generating beat waves using scilab


-->Ts=0.0001;

-->n=-1000:1000;

-->tn=n*Ts;

-->xn=2*cos(40*3.14159*tn).*cos(800*3.14159*tn);

-->plot(tn, xn);



This program shows the Beat waves for the equations given below

eq1

Equations for the two signals

The individual plots and the resultant beat wave is shown below


Plot of frequency equal to 20

Plot of frequency equal to 400


Resultant Beat Wave


This should come as no surprise, that beating forms the basis for Amplitude modulation.

The equation has been mentioned in Signal Processing First (© 2003, James H. McClellan Ronald W. Schafer, and Mark A. Yoder)

Book Recommendation

I have started a part time MS program, the program requires me to read books instead of merely buying them :-)

I would highly recommend "Signal Processing First" for anyone interested in getting started with Digital Signal Processing



Cover of the book

Unfortunately the copy of the Indian Edition I have does not come with the CD, it comes with the license for using the CDROM and the cover mentions the CD, but the book did not have one.

What I like about the book is the simple use of mathematics to explain signal processing concepts. The book made me go back to my "S.L.Loney" trigonometry book. The book uses matlab to explain concepts, I am forced to use scilab as a cheaper alternative to matlab.



Scilab screenshot

Overall, I find this to be the best Signal Processing book I have come across.

Friday, November 04, 2005

Solution to the Interesting problem with trees

I posted a problem in Problem with Trees. The answer is posted below, use the Euler's tour to verify. If it is not correct, I know where I would be losing marks in the exam.

tree_ip2

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...