Jump to content
quad

Programming Task

Recommended Posts

Hey,

 

If anybody has a clue an explanation would be highly appreciated. This is a task I need to finish to apply to uni ;o

 

We investigate the behavior of an unknown program. Different parts of program are written in different programming languages and source codes aren't equipped with any comments. We have found that one of the most important and more often executable code part is the following
for (j=0;  j<K; j=j+1)
     run_dlx();
where K is given as a fixed (integer) parameter. The procedure run_dlx() is an external procedure which can't provide any parameters when called, but only a start signal.
Default value of K is 10. For K=10 the program running time is 6.534 seconds. When we changed K=20, the running time was 41.32 seconds. When we changed K=30, it seemed us that program does not finish its work at all and we terminated it. Therefore, we tested for K=25, for which the running time was 18 minutes and 41 seconds. For K=0 the running time was 6.5 seconds. Finally, we decided to test once more for K=30 and decided to wait more patiently a little bit longer - the running time was 9 hours and 54 minutes.  
To be sure of the results we obtained, we decided to repeat all the experiments - for all K values 0, 10, 20, 25 and 30. In all cases we got the same results (running times) as for previous trials.
Tasks: 

Please explain, what might be the reason that for high K values the program running time is extremely long.
Please explain, what we can conclude about the behavior and features of procedure run_dlx() having the above-mentioned testing data.
Try to evaluate program running time for K=40 and K=50 and additionally for K=15.



Thanks!

Edited by quad

Share this post


Link to post
Share on other sites

Wrong section, off-topic as it it not pko/top-related.

 

Also you may want to refrain from tagging several people that have no relation to this and not try to "force" their attention to your issue.

  • Confused 1

Share this post


Link to post
Share on other sites
50 minutes ago, Mii said:

Wrong section, off-topic as it it not pko/top-related.

 

Also you may want to refrain from tagging several people that have no relation to this and not try to "force" their attention to your issue.

I have removed tags. Also, description clearly states 'questions and discussions related to programming', for the record, it does not say a word that my question has to be top-related. And, I have never tagged you, so I'm not sure why you're being aggressive, as it couldn't even bother you. Besides, I can notice a couple more questions with zero relation to this game, so you might consider leaving some comments out there, too.

 

In case anyone's interested, the above mentioned program was used to brute force. Topic can be closed.

 

Have a good day, MI :)

Edited by quad

Share this post


Link to post
Share on other sites
13 hours ago, Mii said:

Wrong section, off-topic as it it not pko/top-related.

 

Also you may want to refrain from tagging several people that have no relation to this and not try to "force" their attention to your issue.

And what is the problem? Can not help - walk past

  • Like 1

Share this post


Link to post
Share on other sites
9 hours ago, V3ct0r said:

And what is the problem? Can not help - walk past

No problem at all.

Was simply pointing out some people may not want to be tagged to every possible thread(in general not specifically just by quad) out of consideration.

I wasn't being aggressive/toxic or trying to offend anyone but sorry if it bothered you.

Anyways,so as to not go off-topic any further and walk past~

Have a good day :)

Edited by Mii
  • Like 1

Share this post


Link to post
Share on other sites
3 hours ago, deguix said:

I didn't study in university, but you should definitely read about https://en.wikipedia.org/wiki/Memory_leak, one of the most common mistakes in programming.

 

About brute-force... well... it would make sense, except why then would K=10 be almost the same time as K=0?

Hey there,

I'm really unsure since no parameters are passed and idk how it would brute force without knowing what length to use. They should reply soon with the answers and I'll post them here, might be interesting for someone perhaps.

Edited by quad

Share this post


Link to post
Share on other sites

This is also the exact reason why we have various sorting algorithm,
if we would sort a small list, say consisting of 4 entries, an "insertion" sort would be suitable,
but once the list too big, as suggested by your question, perhaps we can use some other algorithm to solve
the sorting of the giant list to save cost and time. try "Bubble" sort.

In your question above, we try to scale the number of execution by a fixed amount regardless how many
entries are in the list. This is how one would try to optimize their programs.

  • Like 1

Share this post


Link to post
Share on other sites

As a fellow university student, this is how I would answer this question.

 

With no further information about run_dlx(), this is my conclusion:

- run_dlx() is dependent on the variable K, which is probably global.

- run_dlx() doesn't scale well with the variable K, and thus runs on an inefficient algorithm.

- Plotting the given time costs against the values of K will easily reveal its exponential complexity and should allow you whether algebraically/geometrically to find a relation to approximate these values.

 

Also a side-note is that in Donald Knuth's Bibles, DLX refers to his implementation of Algorthim X using the Dancing Links Approach with a complexity of O(N^N^2), so that's something for yall to taste!

  • Like 3

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×