Comp Sci noob Questions

[eternaloptimist]

Hi all, I have 2 questions that I'd like to ask.

1. If I had a fibonacci function (assuming I am correct = O(2N)). If I used memoization, will that change anything? The function will be way faster but is it still O(2N)?

2. I have been playing around with multiprocessing (Python) and I am kinda wowed by it all. My question is, have any of you used this in the real world? i.e Parallel Computing? Is figuring out the parallelizable parts of your code always obvious?

Thanks!

 

[cguy]

Hi all, I have 2 questions that I'd like to ask.

1. If I had a fibonacci function (assuming I am correct = O(2N)). If I used memoization, will that change anything? The function will be way faster but is it still O(2N)?

It depends on the algorithm, although I strongly expect that if memoization helped, the original algorithm was probably not O(N). BTW, O(2N) is the same as O(N).

2. I have been playing around with multiprocessing (Python) and I am kinda wowed by it all. My question is, have any of you used this in the real world? i.e Parallel Computing? Is figuring out the parallelizable parts of your code always obvious?

Thanks!

I use it all the time. It's also not always obvious. Generally, many problems are "embarrassingly parallel", which usually means that there is just one for loop that needs to go parallel, but sometimes, threads have to run very different code and interact and communicate in complex ways ("tightly coupled parallelism).

 

[[)roi(]]

Hi all, I have 2 questions that I'd like to ask.

1. If I had a fibonacci function (assuming I am correct = O(2N)). If I used memoization, will that change anything? The function will be way faster but is it still O(2N)?

Let's separate a few aspects:

• Each calculation is O(1); the work to calculate 1 value in a sequence; because we simply pass in two values and add these together.
• When determing complexity, we need to know the algorithm that is being used; you haven't mentioned that, standard recursion is O(2^n) for time, and O(n) re the call stack (assuming no tail recursion, or trampoline). Again this can be improved with different approach, some approaches are even O(1) but at the cost of precision.
• Memoization saves time complexity for consecutive calls but does so at the cost of space complexity O(n). It does not however change the complexity of the memoization initialization. Saving this to disk for reload in memory, means you've sacrificed space to improve time.

2. I have been playing around with multiprocessing (Python) and I am kinda wowed by it all. My question is, have any of you used this in the real world? i.e Parallel Computing? Is figuring out the parallelizable parts of your code always obvious?
Thanks!

Nope, parallel computing is never easy; complexity abounds. Category Theory's Associativity is usually a clear indicator of the potential for parallel processing, however it's certainly not the only indicator.

If you were following along with the Whiteboad Challenge thread, you would have probably seen the question on finding the missing integer; using binary search was the fastest time solution O(logn) but did so at the cost of requiring a sorted list. Using the Gauss formula was probably the fastest time solution to the general problem because it didn't have any preconditions. Looking at the algorithm gauss, you should have noticed it reduced the problem to simple arithmetic (sum of elements subtracted from gauss calculation). The highest time complexity of that formula is the summing of the elements, but as I explained in that thread the sum part is associative meaning the order of summation doesn't matter, for example:

• (1 + 2) + 3 == 1 + (2 + 3)

So that's a clear example that the method can be parallelized with something like SIMD, and the results are significantly faster. For example: standard summation for a sequence of 100 Millions values runs well over 10seconds (depending on your computer), using SIMD: we can do the same in milliseconds.

/Edit missed answering your "used this in the real world" question. Yes of course. None of the computing solutions you use every day could work without it.

 

[eternaloptimist]

Thanks for the responses. Ya I meant O(2^n) just didn't know how to type that.
I'm curious cguy, is this what this paper is about re: your last point? http://www.usingcsp.com/cspbook.pdf
Do you work with Big Data by any chance? In what language/s?

droid, some enlightening stuff! Hadn't thought about memory re: memoization! I actually tried to follow that thread and I felt like most of the stuff mentioned was beyond me haha. I will defo give it another go now.
Thanks again for responding, I'm learning a lot!

 

[[)roi(]]

droid, some enlightening stuff! Hadn't thought about memory re: memoization! I actually tried to follow that thread and I felt like most of the stuff mentioned was beyond me haha. I will defo give it another go now.
Thanks again for responding, I'm learning a lot!

Lol...
Here's some easy to understand links on Big O notation; hopefully helpful:

• Time complexity, space complexity, and the O-notation
• Comparative examples

Apologies if the "whiteboard challenge" thread appears too complex; wasn't the intention. Intention was to encourage not only participation but also to hopefully share technique behind typical problems.

I'll certainly try to expand a bit more on the explanation if that'll help + to make sure that a good portion of the challenges are easier to solve. Otherwise If you have any recommendations then please either post it in the thread or send me a PM.

/Edit what is the exact nature of your studies; is this something at a varsity or is this just part of your own personal growth?

 

[eternaloptimist]

You are doing amazing work droid, I (and I'm sure many others) appreciate what you doing on here and on your blog. I'll spend some time going over the links you posted. I am currently doing a higher diploma in comp sci.

 

[cguy]

Thanks for the responses. Ya I meant O(2^n) just didn't know how to type that.
I'm curious cguy, is this what this paper is about re: your last point? http://www.usingcsp.com/cspbook.pdf
Do you work with Big Data by any chance? In what language/s?

droid, some enlightening stuff! Hadn't thought about memory re: memoization! I actually tried to follow that thread and I felt like most of the stuff mentioned was beyond me haha. I will defo give it another go now.
Thanks again for responding, I'm learning a lot!

Yeah, that book is a very formal treatment of concurrent processes. It was covered in a course in my honours year. Tightly coupled parallel programming is something that very few people can get right. One doesn't need the level of formality in that course in practice, but then a lot of tightly coupled parallel code that runs in practice isn't provably correct, and can often have "one in a quad million" scale race conditions (I've debugged one or two of these - it's a nightmare).

Yes, I work on Big Data, using C/C++ and R. (Edit: and some Python for the glue).