……. programming requires more concentration than other activities. It’s the reason programmers get upset about ‘quick interruptions’ – such interruptions are tantamount to asking a juggler to keep three balls in the air and hold your groceries at the same time.”

–Steve McConnell, Code Complete

So… I am trying to concentrate… but you can still drop an email to me at khuram.ali@aim.com or follow me on LinkedIn on LinkedIn

1. Alethor

Great job!
You ar edoing a great job here! Keep working on it! 🙂
Best of luck!

2. zinat

I would like to know whether it is possible to “write a program or algorithm” to find the time and space complexity of any given program taken as input.

Input : any program (P) [in any language or of a particular language]

Output : time complexity of that program (P).

Have there been any prior attempts to write such a program? Are there any algorithms available for this purpose?

If so please provide the necessary links, references or with any kind of guidance possible.

• if you mean by space complexity as memory requirements and memory leaks and from time, you mean to say running time, yes. every good IDE has these facilities. visual studio, Net beans and Eclipse are good example to check your code. but if you are talking about time and space complexity of an algorithm, i don’t think so, there is a any automated system to do that. I don’t want to say impossible but it is fairly difficult to write one in comparison of doing your maths manually. Furthermore, computers are not yet achieved to think out of the box as we humans do. so many algorithms are just a peace of art and intelligence. Actually, you are mixing two things… an algorithm is not dependant to any language or code. though it can be translated/implemented in any language. email me if you have any further questions. Thanks!

3. zinat

what i exactly need to find is given a program find its complexity in terms of asymptotic notation..
for example:
void Function(int n )
{
int i,count=0;

for (i=1;i*i<=n;i++)
count++;
}

this should give me output as O(√n)

• Asymptotic notation is an estimation not an absolute thing. we can write a program to get it for simple code for an exercise but writing it so that it can work for many different set of codes and will also give fairly accurate results is way too complex. just a rough example for above code you might need two mins to get your asymptotic notation but writing a program for that may took you hours, if not days. It is good to get things automated but there should be a good reason for doing that. just to give you an idea, your program to calculate complexity of Algorithm from code, not only needs to understand the language and its rules… but also needs to do all algebraic calculations and than also needs to have some intelligence to get a nice assumption about asymptotic notation. Still you cannot guarantee that it will produce accurate results in every situation!

• by the way, just to get what i am talking about, flip the situation. try to write a program who will take any simple algorithm and translate it to any language of your choice. take any simple and short algorithm like bubble sort!

4. zinat

thank you for your reply.. yes the other way round is possible but i just wanted to confirm whether measuring that way is possible or not

5. Ahmed

It is a place for seasoned programmers I don t know what am I doing here?
but I ma stuck with BST not the concepts but implementation in c++.

• if the concepts are clear… there shouldn’t be any issue in implementation as it is quite simple!!! Let me know what is the issue>

6. Ahmed

Thank you so much for an early response.
Please tell me what all to master -> to understand the codes of the BST written by you.
I think I lack the knowledge of many .functions that you have used in implementing that code.
may be that is the real issue of my lack of understanding.
I coppied the codes in two files header and cpp , and the main was empty . it compiles very well with no issues. then I borrowed the codes of main from the university handout , and it gives errors .
In Main till here it gives no errors
const int ITEM_NOT_FOUND = -9999;
BinarySearchTree t( ITEM_NOT_FOUND );
int NUMS = 30;
int i;
but at this stage it gives erors

cout << "Inserting elements (1 to 30) in the tree …….)" << endl;
for( i = 0; i <= NUMS; i++ )
t.insert( i );
error list
Error(1) 2 error LNK1120: 1 unresolved externals D:\SINGLYLINKLIST\BST\Debug\BST.exe BST
Error (2)
Error 1 error LNK2019: unresolved external symbol "public: void __thiscall BinarySearchTree::insert(int const &)” (?insert@?\$BinarySearchTree@H@@QAEXABH@Z) referenced in function _main D:\SINGLYLINKLIST\BST\BST\BST.obj BST

Please be informed that this is not my assignment . but the lectures are based on these codes . exactly word to word. first of all the university handout codes do not compile at all, and the teacher Takes big leaps and every thing goes above my head and I do not understand a bit what he says. I have learnt how to implement the BSTs in simple ways from Paul programming on you tube + plus the concepts of BST. But with the template class I am yet to compile this program so that I may get a vision of what is the code doing.

I will appreciate you generosity of this-> Charity( Knowledge) as I am the needy and deserve a help
Regards
Ahmed.

7. There are two ways to solve your problem: the simple way is to send me your code and i will fix it and send you back. it will not be fruitful for you. The true learning needs blood and sweat. just take your time and sit down and write your very own simple BST. just forget about any code of BST you found anywhere and try to write down your very own. It will be a difficult task, but once you write it, it will be yours and you will understand all ins and outs of it. Furthermore, always try to write your own code, at least on this stage, as you are learning to code so coding is the only way you can learn it. no shortcuts.
Universities normally use a specific set of compilers, please check if you are using the same compiler for compiling your source code. Thanks!

8. Ahmed

Thank you so much for your intuitive advise. I will write my own codes and will post them to you . how ever I will post the codes of BST which are being used by the univ as well
As 9 lectures are based on this code and My understand stops where Real world implementation is missing
Thank you so much and I appreciate
Regards
Ahmed