The Official Programming Thread

[vcs]

For any programming related problems you might come across..

I'm struggling with one right now. I'm given a binary string and I need to find the largest substring with an equal number of 1s and 0s in it.

[8ankitj]

There is an easy order n(n-1) ~ n^2 solution, but that might not be good enough for you?

[vcs]

How do you do it.. is it using dynamic programming?

[8ankitj]

Well, I'll just check all substrings which are nC2 in number. I will start from the largest and go down to smaller lengths in each iteration. So I check in this order :

1 to n
1 to n - 1
2 to n
1 to n - 2
and so on

Not the smartest way to do it but would it for you.

[vcs]

Hmm... was hoping for something better than that. That algorithm popped into my mind, but there's got to be a better way.

[silentstriker]

So dire. I was a programmer for five years - the best day of my life will be the day I forget the Big O notation.

[8ankitj]

Ya that was the lamest approach

Here is another: convert 1s and 0s into 1s and -1s. Now do two steps:

For the string from 1 to n create an array of partial sums indexed from 0 to n, with ith element in the array representing sum of binaries from 1 to i (0th element being left as 0).

Now in this array of partial sums find duplicates that are farthest apart. If ith and jth partial sums are identical then your substring from i+1 to j has equal 0s and 1s

First step is going to be order n. Depending on how complex second step is, this may or may not be a better approach

EDIT: something tells me the two can be done simultaneously. Will get back if I can think.

[8ankitj]

We don't have to store partial sums actually. We can create a 2 dimensional array that stores the first and last occurrences of each possible partial sum result and also the difference between the two. As we run down the string calculating partial sums we just have to update the start and end point of that partial sum result.

For example, consider a string of length 15:
1 -1 -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1

You will get a 2-d array like this:

a(-1) = (3,9,6)
a(0) = (0,10,10)
a(1) = (1,13,12)
a(2) = (12,14,2)
a(3) = (15,15,0)

This indicates that partial sum -1 occurs at 3rd and 9th positions which are 6 places apart and so on.
a(1) has the largest difference (of 12). Therefore the desired largest substring is from 2 to 13.

Creating those 2-D array and determining the max of differences are both order n. So overall algorithm is also order n (unless I have missed something).

[Spark]

Doing a course on scientific computing aws. Useful, easy, and so ****ing boring. Ugh. Don't want to see another error formula in my life. And order(h to the whatever the **** it is) can go die in a fire.

[vcs]

When our professor droned on about computational complexity, and how to find the order(n to whatever the **** it is) for months on end, we used to struggle to see the point. For example, when they taught us about Strassen's Algorithm for Matrix Multiplication, one guy in class stood up and asked, why the hell are we learning about an algorithm that reduces the complexity from O(N^3) to to O(N^2.8), whoop de ****ing do. And here Intel are slaving their asses off to build better and better processors with higher clock speeds and multi-core architectures, blah blah. What's the point of all their hard work?

But yeah, these tiny details become vitally important when the problem sizes become large.

[Spark]

It's very useful and important to know tbf. Only reason why I'm subjecting myself to such bone-dry yawnfests.

[Agent Nationaux]

Hey guys, out of curiosity if I were to start my education as a programmer, what language would you recommend that I study first, or would I have to learn something else before trying to understand a programming language (I don't know anything about this field). I would like to learn visual basic because I want to become good at excel. Would I have to also improve my maths in order to do this or can I get by without. And how do I go about doing this, i.e. do I start reading particular books (what books) or take a particular course. Ideally would like someone from UK to answer this because they would understand the education system, but ideas will be welcomed from anyone who knows about the area.

I recently completed my degree in Accounting and would like to one day specialise in programming accounting software, so it would be of course useful to learn how to programme.

Thanks

[vcs]

Originally Posted by Agent Nationaux

Hey guys, out of curiosity if I were to start my education as a programmer, what language would you recommend that I study first, or would I have to learn something else before trying to understand a programming language (I don't know anything about this field). I would like to learn visual basic because I want to become good at excel. Would I have to also improve my maths in order to do this or can I get by without. And how do I go about doing this, i.e. do I start reading particular books (what books) or take a particular course. Ideally would like someone from UK to answer this because they would understand the education system, but ideas will be welcomed from anyone who knows about the area.

Thanks

Agent, if you want to get into programming, I would suggest that you start with C or C++. You don't really have to worry much about programming language syntaxes and constructs right now. If you are comfortable working in one language, you will find it easy enough to move to another if and when you need to. Aptitude in this field usually is correlated to people who enjoy solving problems, and like Maths in general. If you are interested in Discrete Maths topics like number theory, set theory, permutations, combinations, counting problems and so on, chances are you'll enjoy programming.

Once you've decided to get started, you can pick up any basic book on C or one of the vast tutorials available on the net, and try writing some simple programs to get acquainted with what is available to you, and how to translate the problem that you are trying to solve into the language. Getting to a stage where you can write simple programs is not difficult at all. Then you can let your own interest take you as deep as you wish to explore!

[Xuhaib]

this thread is like my C++ class in uni, full of Indian curry with a random Pakistani and a white guy sprinkled here and there.

I dropped from the course after 2 classes ftr.

[Quaggas]

Originally Posted by vcs

When our professor droned on about computational complexity, and how to find the order(n to whatever the **** it is) for months on end, we used to struggle to see the point. For example, when they taught us about Strassen's Algorithm for Matrix Multiplication, one guy in class stood up and asked, why the hell are we learning about an algorithm that reduces the complexity from O(N^3) to to O(N^2.8), whoop de ****ing do. And here Intel are slaving their asses off to build better and better processors with higher clock speeds and multi-core architectures, blah blah. What's the point of all their hard work?

But yeah, these tiny details become vitally important when the problem sizes become large.

Or if you can beat the other guy to the exchange by a couple of ns