CCDSAP Preparation - Day1

This post is simple.

I had registered for codechef certification so that I would get confidence in myself.

Confidence in solving problems and improve my algorithmic thinking.

So, basically, through this blog, I would like to share my thoughts from the time I have started preparation till the time I have passed the certification exam.

Preparation Topics:

From this link - https://www.codechef.com/certification/prepare#foundation
we can get the topics which I need to prepare.

Basically I was chosen for foundation level, because I dont have a active and high-scored codechef profile. Hopefully I get to solve more problems and pass other certification exams like: Advanced level. I shall write regarding the topics one by one.

I saw a video from mycodeschool about the first topic and it was quite interesting. ( Ram and Shyam example )

Asymptotic Analysis - Big O notation -

In my college days, I remember studying theoretic aspects of this. But, now after working for few years, I have almost lost touch with this topic. What I know is that: We have an algorithm. We have input for that algorithm on which it operates. ( Side question - can we quantify time complexity for neural networks algorithms? ). ( Side update - I am eating some banana chips while typing). We would like to know how this algorithm behaves when the input size increases. It is not something like in this form: If the input is 1 trillion positive random integers, how much time this algorithm would take?. Basically we are not actually interested in how much exact time it takes.

We are interested in scale.  And Big O is a scale to measure this scale ( pun intended )

If my input size increases, how would my algorithm behave. For small size input, for example: input size of 10 , it might take in order of few microseconds, For medium size input, for example: input size of 100, it might take in order of few milliseconds. For large size input, for example: input size of 1000, it might take in order of few seconds. Imagine you type some text in google search input, and you get the output after few days. In this case, algorithm is search algorithm. Main Input for the algorithm is the entire web ( that which google can view - side: google spiders can crawl them ). User input is the search text. Now, if we want to think of scale, we can think of many input variables:

• How many websites google is going to crawl?
• How many webpages google is going to look into?
• How many concurrent users google is going to support?
• How many ...

So, we can see that there are lot of input variables. For each of the input variables, there are going to be some corresponding logic ( in combined form or separately ). If each logic is measured in terms of its efficiency. We will know the overall efficiency. And a good algorithm engineer would look at overall efficiency and say, I think it could be improved. Let me look at the constituents and tweak them. So identifying the complexity of our algorithms is the first step in determining scalability of our system against the different inputs. And it is essential trait of a good software developer. ( Just take a java method, look at the input - assuming that it is a set/list/map etc - think if my input size increases, how long would my code take - check if there is a loop present - check if there's some recursion logic present - check the logic which depends on the input size - basically if there's a iteration present.

Basically I just saw one video in youtube till now - I have not solved any problem yet.

Miscellaneous:

I also got to check many questions asked in Quora - How to prepare for these certifications.

And fundamentally the answer is Practice.

Output is proportional to input. By the way, lets make each day count towards our well being. We all want to be happy, one way is to work smart and hard to reach your goals. 

( I feel slightly guilty, since I did not put more hours in Day 1). Let's go to Day 2 with more rigour ( definition - quality of being extremely thorough and careful ). Let me put my goal for Day 2 as finishing Asymptotic Analysis section topics and starting with solving problems from Arrays section.

Please feel free to add your tips about solving problems in the comments.
If you want to share your experience, please share it in comments, that will help someone like me. Thanks.