Posts by Rashakil Fol

Whine whine whine. What is with these people and their sense of entitlement?

I suppose somebody can.

heres a question: i understand that array insertion is carried out in constant time - O(1) - but if the array is 2D (n*n), then would this still hold true if i wanted to insert the same value into each array?

Now what do you mean, saying array insertion is carried out in constant time? What do you mean by insertion? Exactly what datastructure are you using to represent the array? If you've got some naive array in memory somewhere, then you can't grow it at all, and you'll have to recopy the whole thing to a new location, and that takes O(n) operations! (Where n is the number of elements in the array.) But if you've got some space allocated on the sides of the array, you can shift array elements one unit over -- and in the worst case, that's still O(n) operations. If you mean to append an element to the very end of an array, that depends on whether you have pre-allocated extra space. If you have, it's O(1). If not, you'll need to reallocate and copy the entire contents over. Which is O(n). If you double your allocation space on each reallocation, you'll endure an O(1) cost per element added, on average, though. This form of array is called a vector, in C++.

let me explain a bit better, if i have a 2D array of ints, and the array looks like this:

1 2 3 4 5
1 2 3 4 5

It can't.

It's proven that in any Turing-complete language you can create a program that writes its own code as output.

int y = (x * 43691) >> 17;

works for all unsigned ints x (32-bit) that are less than 98303.

And you can implement the multiplication using bitwise operators too... (note that 43691 == 0xaaab, or 1010101010101011 in binary, and the reason this works is that (1 << 17) / 3 == 0xaaaa).

unsigned int divthree(unsigned int x) {
  unsigned int y;
  y = x << 1;
  y += y << 2;
  y += y << 4;
  y += y << 8;
  y += x;
  return (y >> 17);
}

If you can use 64-bit integers, you could write the following, which works on all unsigned 32-bit ints.

unsigned int divthree(unsigned int x) {
  unsigned long long y;
  y = x << 1;
  y += y << 2;
  y += y << 4;
  y += y << 8;
  y += y << 16;
  y += x;
  return (y >> 33);
}

Reverse postorder means you traverse each node's children from right to left.

Life's too short to worry about operating systems.

Well, I was kind of joking when I said straightforward :)

But anybody with a good understanding of basic algebra could be taught how to do this and understand how it works.

Also, anybody capable of following instructions can be taught how to do this by hand.

And if you can do this by hand, you better be able to write a computer program that can do it, too, if you call yourself a programmer.

There are still a few important subtle issues, though. One is that of double roots. If you have a double root, then one of your partial fractions must contain a squared denominator. (And with a triple root, you'll also have a cubed denominator, etc.) For example,
[tex]\frac{3x+4}{x^2+10x+25}[/tex]
expands into
[tex]\frac{3}{x+5}-\frac{11}{(x+5)^2}[/tex]
This is arguably not really a partial fraction expansion; you might say the problem has no solution.

Not only does that issue add some complexity to the program, it raises the question: how do you detect a double root? Well that's an annoying problem, if you're finding solutions numerically. So I would recommend finding some magical polynomial root finder algorithm, at least, that recognizes multiple roots (somehow), and use that. But don't even trust that.

So finding partial fraction expansions is a very tricky problem, and it's sensitive to numerical inaccuracy. The good news is, if you do have multiplicated roots but can't recognize them because of numerical inaccuracies, you'll notice when your numerators blow …

Yeah, there's a simple and straightforward algorithm for this.

The first step is to understand how to represent a linear system of equations with matrices and how to solve that with a computer program.

Once you understand that, you'll need some way to be able to find all the roots of a polynomial (so that it can be factored). You can't do this exactly -- some solutions will need to be approximate, i.e. 'numerical'. And of course you'll need to use complex numbers.

Then, you'll need to understand how to implement polynomial division (and then implement that on a computer).

Once you've done that, it's a simple matter of taking a rational expression and using polynomial division to turn that into the sum of a polynomial and a remainder, a remainder that looks like [tex]\frac{A_0 + A_1 x + A_2 x^2 + \cdots + A_{n-1} x^{n-1}}{B_0 + B_1 x + B_2 x^2 + \cdots + B_{n} x^n}[/tex] and then find the roots of the bottom polynomial to factor the bottom into [tex]\alpha (x - z_1)(x - z_2)\cdots (x - z_n)[/tex], at which point you can conclude that we're looking for an expansion of the form [tex]\frac{C_1}{x - z_1} + \frac{C_2}{x - z_2} + \cdots \frac{C_N}{x - z_n}[/tex] At this point, just add the fractions together (symbolically), and then you'll get expressions in C_1, C_2, etc in a system of equations with teh A_n's on the right side, which you know how to solve since it's just …

In some distributions you can, if you're on the AMD64, i.e. x86-64 architecture, since it's a superset of x86 -- there are issues that come up, like the fact that you need thirty-two-bit libraries /and/ sixty-four-bit libraries installed on the system.

In UNIX-like systems, a file descriptor is a small integer associated with an open file stream. You can use procedures like read and write to read and write to a particular file stream, and in order to do this, you need to provide the file descriptor for the open file you want written to. The procedure open is used to open files, and it returns the integer that should be used as the file descriptor (or in case of error, returns -1).

The standard C library, with procedures like fopen, fread, and fwrite uses 'FILE pointers', pointers of type FILE*, to refer to open files.

I don't know what Windows uses for OS-specific input/output.

There's an infinite number of purposes, and only a finite number of languages, so at least one language has to be the best for an infinite number of purposes.

While Python is a decent language, it just doesn't seem to shine at any particular thing. I'd use it if one of its libraries had some ability that happened to be direly useful to me at the moment.

For interacting with the OS (especially Unix OSes), I feel very comfortable with Perl -- more comfortable than with anything else. I can't recommend against Perl. But I keep looking at Lua (haven't used it) and it just seems very nice.

I think anything but PHP is tolerable. It's not like you're only allowed to learn only one language -- I end up using different languages for different things, anyway.

getch() returns an int, not a char. And there is an open parenthesis missing in the if condition.

int c; 
if( (c==getchar())!='\n')
<snip>

I don't see why two people assume that == is the desired operator between c and getchar(). For one, (c==getchar()) will never return a value equal to '\n'. And of course Deacon J's use of == is nonsensical.

a new stack is allocated

A new stack frame. There's just one stack (in C, anyway), and you normally don't make copies of it.

That's not bad at all. You'd have to store user 3's membership information for each of the 1000 groups anyway, and you'd have to delete that anyway, so this is a linear multiple of the amount of work you'd have to do.

And if by 1000 groups you're including compound groups, then don't store the masks for every user for compound groups; just calculate them user-by-user whenever you need to know all the users that are members.

Oh wow, it seems like they described my personality very precisely!

The thing is, I picked the boxes using rand().

Also, if you're using C++, there's no reason you should be writing typedef struct { ... } foo; . Just write struct foo { ... }; .

[tex]\lim_{N\to\infty}{N^2 \over 2} + {N \over 2} = N^2[/tex]

Don't use fake mathematics. For starters, N^2/2 is nowhere near N^2. And even if you wrote N^2/2, the distance away as N appoaches infinity would be infinity also.

The reason the function is [tex]O(N^2)[/tex] is that, with [tex]N_0 = 5[/tex] and [tex]k = 1[/tex], it's true that [tex]\frac{N^2}2 + \frac{N}2 \leq k N^2[/tex], for all [tex]N \geq N_0[/tex]. Other values would work for [tex]N_0[/tex] and [tex]k[/tex], too.

Your intuition is correct, of course; it would be correct to say that
[tex]\lim_{N\to\infty}\frac{\frac{N^2}2 + \frac{N}2}{N^2} = \frac12[/tex]. And that is also sufficient to prove big-O-ness (since that proves the previous statement).

Here's another Haskell version.

main = mapM_ (putStrLn . show) [1..10]

loller, are you 16 years old? I make an exercise out of guessing people's ages based on their writing style and would like to see how accurate I am.

Which step don't you get? Do you understand how I got to [tex](3N + 6) + (3(N-1) + 6) + \cdots + (3(2) + 6) + (3(1) + 6)[/tex]?

When you look at how much money is spent to keep ONE prisoner in prison, then it's just not fair to let them live.

If you compare this to the cost of actually executing people, it's the other way around.

Count the total number of basic operations, those which take a constant amount of time. That's all there is to it.

For example, the code int Sum = 0; is 1 basic operation. Then j = 0; is another basic operation. Then j < i forms yet another basic operation. Count these, and you get your time complexity.

For example, take the loop,

for (j = 0; j < i; j++)
  Sum++;

In this loop, you end up evaluating j = 0 once, j < i a total of i + 1 times, j++ i times, and Sum++; i times. So the total number of basic operations is: 1 + (i + 1) + i + i = 3i + 2.

Then take the block of code,

int Sum = 0;
     int j;
     for (j = 0; j < i; j++)
    Sum++;
   cout << Sum << endl;
   i--;

Here, we have int Sum = 0; taking one operation, for (j = 0; j < i; j++) Sum++; taking 3i + 2 operations, cout << Sum << endl; taking 1 operation (or 2 operations, depending on how you look at it, but the whole thing takes a constant amount of time anyway). Then i--; takes one operation. So that's a total of 1 + (3i + 2) + 1 + 1 = 3i + 5.

Then take the block of code,

int i = N;
while (i > 0)
 {
[b]we calculated this to …

1.An algo can't have both constant time and O(n^2).
2.There is no such thing as O(n^2 + <something>)

The time the algorithm takes is a function of more than one variable, so O(n^2 + <something>) is perfectly reasonable notation.

3.Time complexity of an algorithm is independent of PL, OS or anything at all. Even if you have hardware quick sort on your machine it is still O(n log n) (Worst case O(n^2))

You're missing the point. I'm talking about development time; every serious language has the same time complexities. For any given task, some programming languages take less economic resources than others. You wouldn't use Delphi to code a supercomputer, would you? If you're writing a MacOSX application, Objective C would be the language of choice, no? If you're a scientist doing some numerical calculation, you'd use Matlab or something like it, no? They're the cheapest tools for their respective jobs, and you'd be wasting money/time otherwise.

4.I still have no idea about what is the algorithm we debate on its time complexity.

You can derive a closed form of the summation by simplifying the relation

sum_from_1_to_K(x^n) - sum_from_1_to_K((x-1)^n) = K^n

iteratively or recursively. The algorithm implements this and then evaluates the closed form of the expression.

First of all Perl is almost out-dated by Python.

What does out-dated even mean in the context of programming languages? As I said, add Perl or some language inarguably more powerful than Perl to your list of languages, so add Python, if you consider it better.

Second the job could be done in less than half an hour w/ both Delphi or C#. (Don't take the language alone, the acompaniying wizards and IDE features are also a criteria of choice.)

No, I don't think so. Please introduce me to this magical wizard you use for stripping text out of malformed HTML, organizing it into rows, categorizing it, indexing rows of a CSV by words stripped out of company names, and then throwing up a soundex-like search through a CSV file for similar words and prices, and then combining that information and communicating it to a picky telnet server.

And I challeng you to write the same code in Delphi w/o using a single line of code typing.

What is the value of not typing lines of code?

You best bet would be DCG (Delphi Compiler Generator) which is an enhanced lexical analyzer-parser generator (from gcc bison and yacc) which is free. Haskell is as old as berlin wall.

Then why didn't the Pugs project use it?

No, Lisp is as old as the Berlin wall. Haskell was created in the 80s. I fail to see your point about old = bad; Pascal is older than Haskell, …

So my final opinion is C# and Borland Delphi Rocks. C and C++ are ok for performance on native code, portability and legacy stuff. For scripting and DHTML we can keep JScript (not Java Script) I guess and that's all. Tell me your favorite PL and I can tell you why it isn't necessary today w/ proofs.

"Necessary"? What does that mean? A programming language doesn't have to be "necessary," it has to be better. The only "necessary" language is machine code.

The other summer, I had a bunch of data in one text file, and then in another text file (an HTML file), I had a bunch of other data. I needed to process the information. One hour of Perl later, the job was done. Could the job have been done so quickly in C, C#, Delphi, C++, or Jscript? No. So add Perl, or some language inarguably more powerful than Perl, to your wall of necessary programming languages.

There are many tasks that the languages you've listed are not good for. For (a self-referential) example, if you needed to write a programming language interpreter, to run on PCs, as quickly as possible, what would you use? Haskell would be a better decision than the languages you've mentioned (and it would probably be the best decision).

If you measure programming languages by how much money they can make your business, then to claim that all you need are C#, C++, Delphi, C, and Jscript is laughable, …

I can see Java having to be around, for web-based applications,

That's not where Java shines.

and Visual Basic for teaching programming fundimentals,

What?????????????
????????
??????

~cries~

(The problem with Visual Basic, as a relative of mine who uses it jokes, is that it's "just not nerdy enough.")

And, um, Narue answered you with the right answer. I don't know what you expected.

Huh? Answer to what? (a AND b) OR (NOT b) is not in any of the problems...

Over.

The End.

Generally speaking, I think things would be improved with a normal font size, better contrast for all text, and for buttons. Using black instead of gray would help.

With all the gray, low-contrast colors and such, the site seems to be a bit of a ghost town.

There was once this gal named cscgal.
She thought and exclaimed, "Be a millionaire, I shall!"
Then one day, she counted up her money,
Her sequins, her gaint stones, and all her honey.

It summed past a million, and so cscgal cheered,
"I'm a millionaire. I shall be revered!"
And so the crowds gasped, and the horses reared,
But the time of her enlightenment ever so neared.
"You're not a real millionaire," one fat cat sneered.
"We use the sum towards which dollars are geared!"

And so cried the cscgal. She cried and cried and cried and cried,
And cried and cried, and nearly died,
And just a few times, she yelled,
A word that could not be succinctly spelled:

"Noooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooo!"

But then it came to her mind,
That her money was not lost to someone unkind,
That it was still hers and it was still the same,
That silly titles and words could not alter her fame.

And so she decided, to stand derided.
She stood presided, while others deprided.
And so she had rearranged the rankology,
So others learnt her newfound philosophology.

If you want to delete only one offset, use only one iterator.

vector<int> v;
for (i = 0; i < 10; ++i) {
    v.push_back(i);
}

v.erase(v.begin() + 7);

for (i = 0; i < v.size(); ++i) {
    cout << v[i] << endl;
}

Output:

0
1
2
3
4
5
6
8
9

See cppreference.com if you want more info on how erase() works.

If you feel like reading this post slowly and carefully, it will describe what this notation _really_ means.

All functions have some kind of behavior as n grows towards infinity. For example, if f(n) = 1/n, then as n grows towards infinity, f(n) gets closer and closer to zero. Whereas if f(n) = n*n, then as n grows towards infinity, f(n) grows too.

Functions can grow at different speeds. If two functions are equal, then they obviously grow at the same speed. But wait, there's more! Two functions are deemed to grow at the same speed if they're separated by a constant multiple! For example, if f(n) = n*n and g(n) = 3*n*n, then f and g are deemed to grow at the same pace, because g(n) = 3*f(n), so they are only a constant multiple apart. That is, g(n) / f(n) = 3, as n grows arbitrarily large.

But consider the scenario where f(n) = n * n, and g(n) = n. Then what is the behavior of f(n) and g(n) as n grows arbitrarily large? Well, f(n) / g(n) = (n * n) / (n). Which simplifies to f(n) / g(n) = n. Which means that as n grows large, f(n) = n * g(n). What does this mean? f and g are in this case not separated by a constant multiple. The multiple between f and g grows larger and larger as time progresses, without stopping. We say that "f grows faster than g" …

He said "factorial," zyruz.

Iamthwee, you know what a for loop is, right? Start 'answer' at 1 and multiply answer by all the numbers from 1 to n.

What is a terrorist country, and how do you kill it?

Use GET for a location if you want somebody to be able to revisit the page. For example, search engines use GET.