On Decidability

Today, someone was saying that he/she finds decidability in TOC very hard to understand. And, my mind could not resist the temptation to type this out.

TOC deals with the key notion of “algorithm”. The question that we are interested in answering is, what problems can have an ‘algorithm’ and what cannot? In other words, which problems are solvable and which are not. This forms the theoretical basis for the entire world of software development that follows in courses like Algorithms, Data Structures, Programming, Software Engineering and so on.

If you were asked to answer this key question, how would you approach? There starts the beauty of this subject, TOC. First, we have to build models of machines which can solve something. Then, we have to build models of ‘software’ that solves something. At the end, we need some formalism to prove that depending on the nature of the machine, certain problems are unsolvable.

We first introduce the major idea that everything in this world can be modeled using a set. Yes, the usual normal set notation that we know of, such as A = {1,2,3}. We build and represent machines as sets. We represent input and output as sets. This idea, for itself, must have got a Nobel prize! You should take few days to sink this idea hard into your head.

Next, we show that there are only few classes of machines we could build. Everything else that we can think of is equivalent in power to these machines! I would have given second Nobel prize for this idea. If there are only few such machines, what are they? How do they look like? How do they process the input? How is an algorithm encoded? After answering these usual questions, the last major question we ask is “What is that this machine cannot solve?”.

My dear friends, this last question is your hello world to decidability. If there is one “wow” thing in computer science which stays in my heart forever, it would be the way TOC develops these ideas. Decidability is an extremely easy topic if you have absorbed these ideas correctly and completely. There is no need to mug up any table. There is no need to look at any videos. Just take a nice book, find a calm place, and dive into the beauty. If you have a friend or a parent who will get you a coffee in between, what more do we need in life!

Beautiful computer science.

Advertisements

Why do we fail?

An important bit of advice for success as a student.

When we read something new, it sits in some remote corner of our brain. We are very likely to forget it soon, perhaps even as soon as the very next day. If we encounter the same thing again, it could perhaps be recalled with ease. It stays there a little longer. Revisiting often enables our brain to recall much faster. Moreover, there is one more function of our brain that is important to understand. When we store multiple concepts, it makes connections among them. Over time, these connections become deep provided you revisit these ideas or concepts frequently. These connections develop the most desired quality in us which we call, *aptitude*. Most exams test our aptitude and not knowledge.

A common mistake we do is to over-estimate our command over our knowledge just because a concept sounded simple when we heard it first. Many concepts look simple at the first glance. Also, since it looks simple, and since time is always limited, we prioritize reading more new things than to stick to our revision strategy. We go the exam and only experience a total blackout!! This is why many of us fail.

So, my advice to you is to buy a nice notebook and start taking good quality notes. Keep multi-color pens with you. Be creative in taking your notes. Mark one hour every day only to read your notes. Make it a point to read all your notes everyday. Over a period of time, the notes will grow. But, so will your brain’s ability to retain and recall. After a while, when you do not need such large notes, make shorter version of the same notes. Read the shorter version every day. After few weeks, you will see your brain doing magic. It can now solve problems which the best students in your class struggle with.

Keep one important point in mind. You as an individual student have the same potential and qualities as any of your classmates. Know that it is not just Kohli’s muscle power, it is his technique that also counts. Learn the right techniques to study. You already have the necessary muscle power to do well in studies.

Excellence in studies is not a rare quality. It is just a conscious choice. Good luck!

Some Exam Tips

Exams are around the corner. Many of you must be burning the mid-night oil. The nights of group study that I did with my friends, are moments that turned into pleasant memories which remain treasured for life. As you approach your exams, here are some tips.

There are three qualities that go into meticulous preparation.

Firstly, it is your ability to organize the material in your head. Start with making a mind map of the syllabus. Gradually expand the mind map with details in a hierarchical fashion. Usually, what looks very simple at one level suddenly becomes vague at the next level of detail. This is what I call as “illusion of knowledge”. Kill the illusion of knowledge by continuously seeking examples. Look at several problems to apply your knowledge. Verify if your answer is correct.

Secondly, it is your tenacity to do that tiny bit more than your peers. Last minute preparation limits you. Yet, your age and energy gives you the necessary stamina to put long hours with strong focus. Someone told me, if there is one skill to teach, teach your kid the ability to focus. There is Afghanistan threatening India not on battlefield but on the cricket ground. Perhaps we won’t worry as much if it was battlefield. Anushka Sharma keeps coming in the news just to spoil our focus on exams. The distractions are too many. Learn to focus.

Finally, know that there is one part of your brain which takes care of abstract thinking. All of us can understand when concrete examples are thrown at us. Generalizing from concrete examples is an art by itself. Consider a complicated C program thrown at you. For a small input, you can trace and figure out the output. But, you need to now generalize your finding to a larger input by way of abstract thinking. You need to connect few theoretical dots to get there. This requires special training which only aptitude problems (see RS Agarwal’s book) and continuous practice can give you. At the end of the day, all you need to know is how to handle 6 pieces (Rook, Knight, Bishop, King, Queen and Pawn) to beat Viswanathan Anand in Chess. You know, knowledge is not enough. Same is true with any exam. Do not settle for surface knowledge. It is that one inch deeper that you choose to dive which will find you the beautiful pearl of knowledge on the exam floor.

All said and done, cracking exams is a fairly easy art. It takes very few attempts at exams to know the tricks. Hence, we all know that exams are not fool-proof and grades are to be taken with caution. So, do not give too much importance to the result. Just enjoy the learning experience. Execute with as much perfection as you can. Have fun. Good luck with your exams.

Beware of your words! :-)

Today, I was reading about the Thumb Instruction Set of ARM family. I landed into this line which made me quite curious – “All Thumb instructions are encoded into a 16-bit half-word format”.

We know of bits and bytes, even words. If we have half-words, there must be some history to it. First of all, word is (put loosely) just a fixed-sized piece of data handled as one unit by the processor. In 1970s, DEC came up with VAX which used 16-bits for these chunks. So, 16 bits became a word. They referred to 32 bits as longword. The x86 family offered three different word lengths (16, 32 and 64). They continued to designate word to 16 bits. The earlier documentation written prior to 1970s did not agree with a 16 bit word though. Microsoft’s Windows API refers 16 bits as WORD regardless of whether you use a 32 bit or a 64 bit processor where the word size changes accordingly. They call 32 bits as Double Word or DWORD and 64 bits as QWORD (quad word). By now, backword compatibility has become a huge issue. So, we stick with this terminology.

Well, ARM like me is quite different! For ARM, we have a 16-bit half-word!! Next time, if you get confused with WORD, at least know that it is not your fault.

Unfortuantely, a little bit of knowledge of our hardware and the associated computer organization is required for us to become good programmers. Yet, at universities, we jump into coding a little too early!

Beautiful computer science.

How to Title Case?

Most conferences, especially the ACM conferences which I write to, suggest that we use title case for titles and headings.

There seems to be no agreement on what is right way to title case. Turns out that there are several styles such as the APA, Chicago, AP, MLA and so on.

The best way seems to be go with the https://capitalizemytitle.com/# site. Check the APA and Chicago style for your title. Use a title where both these styles agree. For instance, I wanted to title “Code Variants and their Retrieval using Knowledge Discover based Approaches”. I figured out that the APA and Chicago version after title casing this statement is, “Code Variants and Their Retrieval Using Knowledge Discover Based Approaches”. So, I went with it.

Correctness, Precision, Accuracy – What is the difference?

Correctness and completeness are typically used to evaluate software quality. The idea can be extended to just about any task. Correctness usually reflects if the program works as expected for all test inputs. Completeness refers to the availability of all features requested as per the requirement. In software testing parlance, a program is required to be correct and complete to the best extent possible.

This terminology sounds strikingly similar to precision and recall. In the Information Retrieval community, precision is defined as the fraction of relevant results retrieved over all the retrieved results. Recall refers to the fraction of relevant results retrieved over all relevant results found in the system.

In our research work of ANNE, we tag code snippets with natural language phrases. For example, “[ ]” is tagged as “array”. In this context, instead of the information retrieval terminology of precision, we chose to use “correctness” for the tagging task. It was more intuitive since we are not searching for anything here. Similarly, completeness refers to the fact if all entities are discovered and tagged. It makes more sense over recall.

Machine Learning community, especially the classifier builders use “Accuracy” which is not exactly the same as a combination of precision and recall, say “f-score”. Let us say that you are developing a binary classifier to predict if a tumor is malignant or benign. You would calculate accuracy as the fraction of the number of correct classification over the entire set that was classified. This sounds exactly like precision. The only difference is we do not have a restricted set of results. For instance, there is no Accuracy@10 like we do with precision@10.

I believe, the ideas as similar. Terminology is different. Depending on the task at hand, we apply our best judgment to select the most appropriate measure.

I’m planning to prepare for GATE. I’m doing full time job Mon to Friday 8am to 8pm. Any tip and advise you would like to give me. I’ve attended gate forum coaching earlier during my engineering but didn’t prepare and do well in my first attempt. I have all resources for studying. This time I’m planning to do just self study.

This is a common question many people ask.

Exam preparation is different from studying for knowledge. So, first of all, you should get the clarity on what is it that you want. Are you looking to enhance your knowledge and acquire new skills? Or, do you want to invest your time in getting a good GATE score? From the context of your question, I believe your objective is to do the latter.

Exam preparation requires you to acquire aptitude. Aptitude comes by investing time in thinking and practice. So, my first advice would be to value depth instead of breadth. Take few topics which are easy to score and do your best to solve as many problems as you can. You should be confident that if a question comes from this topic, you will certainly score it. Do not run behind covering syllabus.

My second advice would be to be conscious about the illusion of knowledge. Often, it seems that we understood a concept. Understanding a concept and solving a problem related to that concept are at different levels of aptitude. So, do not stop if you think you understood. Spend time in quality thinking and problem solving. One way to evaluate whether you have the aptitude is to solve past year problems on your own. So, mark few problems for testing and few problems for training.

My third and most important bit of advice is to hone your ability to recall. This sounds trivial. But, many people will agree that they knew it but had a black out during the exam. Their brain just could not recall anything. One way to do this is to practice recall. To be specific, everyday, spend 30 minutes recalling what you did before. Some call it revision. Do not look at the notes. Try to recall page by page what you wrote before. Recall the ideas. Recall some interesting problems.

CS is a vast subject. Too many topics and too many ideas to master. You may not get enough time to rock. Do not feel pressurized. Give importance to your job. If there is further time left, hopefully these tips will help you. Remember, if you are not having fun, you are not doing it the right way. This applies to learning and preparing for GATE too. Cheers and good luck!