Posts by Rashakil Fol

^
Is too friendly to criticize Nichito for not using his money for more efficient forms of generosity. :-)

Generally speaking, algorithms which cut the input size in half on each constant time iteration.

Do you understand big O notation?

But why is your logarithm in the base [tex]\sqrt{2}[/tex]?

You're right. I should have said [TEX]2\log(n+1)[/TEX].

What? How can the height of a tree be a non-integral value?

Dear All,
Since understading of Induction Is very Important in the Analysis of Algorithm .I have studied it ,but have never practically put them in use ,while desigining my programs. can you kindly explain to me how one should exploit this conceps while desiging an algorithm using loops and recursions. Simple Example will help me to uderstand the concept little clearly.

Algorithm design is an exercise in procrastination. Ask yourself, "what's the least I can do that will make this problem easier?" And then do that. For example, take the algorithm that finds the sum of an array of length N.

First, you might think, "okay, to find the sum, well, all we have to do is find the value at index 0, and then add to it the sum of the values from indices 1 to N-1."

So now you're interested in finding the sum from 1 to N-1. And to do that, you just take ray[1] (let's assume that 'ray' is the name of our array) and add it to the sum of the array elements from 2 to N-1. And in general, it looks like we'll want an algorithm that takes the sum of an array from indices i to j, for arbitrary values of i and j, where i <= j. And if i = j, we have a simple problem: finding the sum of an empty slice of array (and that sum is zero).

So we could have

int sum(int* …

Of course, y = x + 1.

I'd like to nitpick the statement that the height is [TEX]\log n[/TEX]. On a balanced tree, it's correct to say that the height is [TEX]O(\log n)[/TEX], but not exactly (or even remotely close to, in any base) [TEX]\log n[/TEX]

Yes.

no

nicotene is more toxic than cyanide by the way

Citation needed.

> Instead of simply informing Dani when there's a technical glitch or hole, he demonstrates how it could possibly be used in a bad way.

I wouldn't say that. I decided that some people behave too materialistically about reputation points, as if they carried any meaning whatsoever. And I thought it would be fun. And it was.

>For example, not too long ago he created a thread that was full of profanity.

And I reported it twice! I was really just confused, because it seemed like there was no profanity filter at all anymore.

> as far as I know (someone correct me if I am wrong here), did not abuse his powers,

More out of laziness than benevolence :P

Exe files have to follow a certain format, and not every piece of machine code forms valid instructions. Yours was broken. You'd probably want to take some source code and compile it, if you want to create an exe.

Let me summarize the situation here: You're all idiots. Get over yourselves.

That doesn't involve function pointers though :-/

Mentioning function pointers must be a sign of being completely lost, since there's only a finite constant set of values a function pointer can attain in any given executable; you might as well implement a stack using a bounded set of integers, or something crazy like that.

I am very confused. How in the world are you going to implement a stack using function pointers?

What you've just described is selection sort, where you select the minimum element from an array and append that onto an array that you're growing.

Insertion sort takes out the first element of the remaining elements and inserts it into the right place. To sort [2 7 3 9 4], you'd sort in the following fashion, where the list on the left is the sorted list that we're building, and the list on the right is the unsorted list we're taking elements from:

[] [2 7 3 9 4]
-- take the 2 and insert it 'in the right place'
[2] [7 3 9 4]
-- take the 7 and insert it 'in the right place'
[2 7] [3 9 4]
-- take the 3 and insert it 'in the right place'
[2 3 7] [9 4]
-- take the 9 and insert it...
[2 3 7 9] [4]
-- take the 4 and insert it...
[2 3 4 7 9] []
-- we're done!

And the sorted list becomes [2 3 4 7 9].

Now, I've been using the word 'list' instead of array, but that's only because I'm speaking abstractly. You can do an insertion sort on an array, in the fashion described above, in-place. Instead of changing the sizes of two 'lists' (whatever that means in the context of programming), you can simply walk an index through the array, from 0 to …

Who are participants.

... they don't choose to inhale smoke, and they do not enjoy the atmosphere. But, hell.. if every restaurant is like that what can you do? Who doesn't enjoy the occasional trip to a restaurant for good food?

So if you don't have any chinese restaurants in town but a bunch of people want to eat chinese food, it's okay for them to force restaurants to make chinese food?

AGAIN, something like sunbathing doesn't harm the people around you that choose not to participate whereas smoking does. I thought we at least agreed on that.

Smoking in restaurants only harms people that choose to participate.........

> It is the smoker's right to smoke, and my right to enjoy a restaurant without having to endure smoke.

No it is not! You don't have this right. This is a completely made up right. I thought that's what we've been arguing about. Your logic is fully circular.

If there are no restaurants in the area, are your rights being violated? That's a simple test which shows you don't have a right to have a nearby restaurant that isn't filled with cigarette smoke.

> And here's an idea. If you think that everyone has a right to smoke and it doesn't hurt anyone then why don't we legalize marijuana too?

Um, we should legalize marijuana. Why should it be banned? You confuse me.

> Why not legalize assault?

You mean battery, right?

It is legalized. You are allowed to get into fights as long as you obey some basic legal requirements. Have you ever heard of boxing? How about football? Ice hockey?

> Smoking has no benefit for anyone.

Unless you're God, it's not your place to decide these things.

> Unfortunately there are four flaws in your little story. One: Sunlight only causes cancer under certain circumstances as in far too much exposure.

One: This is where you lose your mind. Second hand smoke causes cancer only under overexposure, too.

> Two:

Two: You can count!

Three: So can I.

> Sunlight is natural and inevitable (unlike smoking).

Four: No, you can block it with shading technology.

> Three: Smoking is something that is much easier and reasonable to ban than sunlight.

Five: Do you have any justification for this? Or do you justify your moral beliefs by making stuff up?

> Four: Someone that is resistant to sunlight can take precautions of there own such as sunscreen, an umbrella, etc. as they are a minority (such as smokers are a minority as well).

Six: In that case, let's ban rap. Black people are a minority, and their minority music is polluting the neighborhood.

THE ADVENTURES OF ALYSSA P. HAIRYLEGS: EPISODE 1

A group of people decided to meet together in some building and enjoy some great food made by a neighbor of theirs. They all smoke and they're all happily enjoying a night of food. It's good and they pay their neighbor for the service of cooking it. Their neighbor decides to make this a regular thing, so he renovates his building's kitchen, adds tables, asks a few folks if they'd like to waitress there in exchange for money. They agree. The establishment has great food, lots of cool people, a nice view overlooking the western horizon and such.

Then Alyssa P. Hairylegs happens by and decides that this seems like it might be a nice place to eat. She waltzes in, foxtrots over to a table, tangos into a chair and opens a menu. She looks for any vegetarian entrées but can't find any. Approvingly, she orders a steak and lights up a cigar.

It's getting late, and the sun is setting. The building's interior is bathed in light from the setting sun. Alyssa asks a waitress if the windows could be shaded so that she doesn't have sunlight fall on her. The waitress tells her that there are no shades for the windows. Alyssa stands up and shouts, "I DEMAND TO SEE THE MANAGER! NOW!!!1"

The manager walks out of the manager's closet and asks her what the problem is.

Alyssa replies, "THE SUN IS ON …

Aw.. you didn't reply to my post.. :-/

>I don't recall being forced to go to public places. Do you really choose to hang out in places where people smoke when you clearly don't like it?

haha.. you're funny. So, basically you're saying that we should just not go to places where smoking inside is legal.. Oh, okay. So, if we want to go to our favorite restaurant, or shop at the mall, or go get some ice cream, etc. then too bad for us? Hell, no.. We should NOT be punished simply b/c others choose to smoke. Why should we be forced out of establishments simply b/c others choose to smoke??

Wait a second: if you don't like cigarette smoke so much, why is your favorite restaurant the one that has smoke lingering in the air? Are you retarded, or do you just get off by acting that way around others?

It was his choice to drink and drive, but his choice killed innocent people who did not choose to drink and drive. Is this fair? NO! Which is why it is illegal to drink and drive. What's the difference between this and smoking?

In the interest of giving you the benefit of the doubt, I'm going to pretend that's not a rhetorical question. The difference is the following: the reason drinking and driving is wrong is not that it kills people who did not choose to drink and drive. It's that it kills people who did not …

They just passed a law in Ohio making it illegal to smoke in indoor public places. I'm glad. If you can't go one meal in a restaurant without smoking you need to start backing off of it some.

Are you so full of yourself that you think it's your place to dictate how other people live their lives?

MinGW, not MiniGW.

>I encounterred a person who said that C++ is an unsafe language.
It is and it isn't. C++ doesn't do much to protect you from doing something wrong, so in that light it's an unsafe language. However, if you do things right, it's perfectly safe. I'd say that person was wrong for making such an absolute and general statement, but a lot of absolute and general statements have some ring of truth.

The definition of 'safe' and 'unsafe' are usually clearly and precisely defined, or definable, and under all versions I know, C++ is unsafe. It's not type-safe, and it's not safe from memory leaks, and exception-wise, it is unsafe, too (and will always be, if you have exit). To state that doing things right makes it perfectly safe is to annihilate any definition of safety, except the one that has to do with whether the language is practical or not.

What is truly the purpose of this post? It seems demeaning, and almost as if you view yourself better than others.. Your smart rashakil, a bit of an ass.. But truthfully you aren't quite as intelligent as you think.. I've never seen any post of yours to be brilliant.. I'd say that you're about avg. intelligence.. with a bit more wit then some.. but nothing more.

Clearly, it's demeaning. You think people should send out their little reps saying "you're dumb" without getting demeaned? Since christina>you was ignorant of the behavior people have come to expect of her, you don't think she should be informed of that fact? She usually is the nicest person on the forum, but I don't think passive aggressive behavior needs to be tolerated. If she knows her behavior to be truly good and just, then she should regard my opinion of her reputation (if you'll excuse the pun) as the ravings of an idiot lunatic.

I don't see what you mean by "better than others." That doesn't make sense. You can't compare people and declare one to be "better" than another. Well, I suppose you could do such a thing, if you felt like being silly. Regardless, I don't think I've come across as acting as if intelligence is a primary virtue: if anything, it's curiosity, expressiveness, and recognition of the fundamental absurdity of things that I've treated as good characteristics in people.

The interesting question is the following: Why do you jump …

I don't understand why he thinks I'm going to bad rep him.

Because that's what you do? Why don't you rep him with "you're dumb"? That's what you do, right? And he's dumb. So tell him that! It'll make you feel good when it's done. You'll make your mark on the world, telling people that they're unintelligent. I'm sure then that they'll strive harder to achieve your level of perceptitude.

To summarize: because the standard says so.

The distance from the origin, assuming you're using Euclidean distance, is sqrt(x^2 + y^2 + z^2).

The dot product? Google it.

That's what if statements are for.

I am serious. There are three cube roots of -2 -- three values x for which x^3 = -2. I'm talking about complex numbers. Which one should be returned? The negative one? Or the two others which are sixty degree rotations of that? What about the sqrt(9999999999999999)/300000000 power of -2? What's that? You've got an irrational power that's really close to to 1/3. All of the sudden, you have countably infinite values x for which x ^ (300000000/sqrt(9999999999999999)) = -2. Which one do you choose? What about the pow(-2,1.0/3.0)? Remember that 1.0/3.0 is not one third. The floating point approximation will exactly represent some number in reduced form that has a denominator that is a power of two, greater than one. That means all the roots are not real.

If you want to approximate the function that's the inverse of the function f, where f(x) = x^3, you can't just use pow. You need to take the absolute value to the 1.0/3.0, and then adjust the sign.

If you were to ask me what pow(-2,1/3) should return, if it could return complex numbers, I'd say it should return the value equivalent to pow(2,1/3) * cos(pi/3) + i * pow(2,1/3) * sin(pi/3).

The cube root of -2 isn't a real number. So you're not going to get a real answer.

Store the array alongside a 'multiplier value' that you multiply the elements of the array by when reading them (and divide by when writing...). Then have MultiplyAll simply change the multiplier value.

Also, keep a counter and increment it with every ZeroAll call. Store with each element in the array a value that tells what the counter's increment was the last time you wrote to it. If the ZeroAll counter is greater than the counter alongside your value, then treat the value as if it were zero.

Your get_letter grade function has a space in its name, and the implementation doesn't return anything.

1. The expression "Literal string" is a cute way of writing a memory address that points to to the front of an array of bytes, somewhere, whose contents are "Literal string". Except when initializing an array.

2. Both of those produce equivalent behavior, nyes?

3. Your program doesn't do anything; why would the compiler treat it any differently from void main() { } ? And main is supposed to return an integer.

He could just cout the string itself, so I take it this is just a test program for another project.

Your string's not null-terminated, unless you're lucky. In Dev-C++, it turns out that a zero was already there at the end of the string 'line'. In VC++'s executable, that turned out not to be the case.

You need to use

line = new char[length + 1];
strLine.copy(line,length);
line[length] = '\0';

in place of what you have there.

What you're doing is setting the characters to zero and then overwriting all the zeros you wrote, which is just pointless. You need a zero _after_ the C-style string, to delimit its end, so you need to allocate one extra byte for that zero and then set it to zero.

Not to mention that his very own example is still unsafe!

This is certainly posted in the wrong room, but that's no sin.

You mean that the OS is drawing stuff on your screen at a ninety-degree angle? That is, if you rotated your screen by ninety degrees, it would look normal?

This is a feature available for some operating systems or perhaps video cards. The way to fix it isn't hard, but it depends on which operating system you're using.

So, tell us, what kind of computer are you using? Mac or PC? (Or Linux or FreeBSD or ...)

The function might be located somewhere else in the book. If not, what do you think that function is supposed to do? It looks like it's looking at a string and asking if the user input a valid integer.

Did you add time1.cpp to your project?

That does the trick, except that computing A[j]/n takes log(n) time. But it is nice.

Because it's wrong. You can make assumptions of O(1) comparison for comparison-sort based algorithms, mainly because the comparison operation is in fact O(1) average over the course of the sorting algorithm with respect to the amount of data you have. But here, you're performing an algorithm with your data which takes non-constant time, and you're proposing ignoring it. More particularly, the square root algorithm _uses_ looping constructs (how would you propose implementing it?); are you just going to ignore those looping constructs?

If ignoring the running time of functions written by other people is your modus operandi, why not implement selection sort where the selection part of the algorithm is abstracted away by a function that you just pretend to be constant-time. Then you've proven that selection sort can be done in linear time.

Heck, if you're going to pretend the log(n) of the square root algorithm doesn't matter, why not just use merge sort and declare its log(n) factor doesn't matter either?

Considering that computing sqrt(N) takes log(N) time (at least), square rooting all the integers that you're sorting will doom you to N*log(N) complexity. And it will just arrange your elements into buckets, as they were before.

Heck, simply _looking_ at an integer takes log(N) time. My bad idea of putting elements into buckets and being smart about that requires log(N) time just to put the elements into buckets, actually, because computing k `mod` n, where k < n^2, still takes log(n) time.

Are you sure you don't need to provide O(N) _average_ time?

Here's some ideas about strategy: First of all, consider an extreme case, where sqrt(n) buckets have sqrt(n) elements fall into them. Well, know (by induction) that any bucket with more than sqrt(n) elements and n possible values can be sorted in linear time using a recursive call to this same algorithm. The hard part is sorting those buckets in which the range of possible values has length N, but the number of values is much less than N (since this is closer to the general sorting problem).

Consider another extreme case. Suppose we get n/log(n) buckets of size log(n). Then each of these buckets can be sorted in log(n)(log(log(n)) time, which makes the total running time n*log(log(n)). That's obviously not the right algorithm to use, but it's much better than n*log(n).

Well, what _can_ we do? If we're to sort each of these buckets separately, we'll need to sort them in log(n) time (which is linear with respect to size).

And in general, if we consider the cases where we get n/f(n) buckets containing approximately f(n) elements each, then sorting these buckets naively will give overall n * log(f(n)) time. In "average" cases, we'll have a long tail of buckets with 2,1, and 0 elements, which means average case will take O(n) overall running time. But if f = log, then we get nlog(log(n)). And if f(n) = sqrt(n)/log(n), we get n*log(n) running time... But if f(n) = sqrt(n) or higher, then all of the sudden we …

What about something like this:

Make buckets for the ranges 0..n-1, n..2n-1, ..., n^2-n..n^2-1.

Then, first go through the array and fill the buckets with counts of how many elements fall in the buckets (and maybe an array that you fill linearly alongside the count). Then _smartly_ (that's the key) base your strategy on the distribution of the elements in the buckets. (Of course, you'll need to figure out what strategy to use in linear time. But then again, since the counts associated with each bucket can be sorted in linear time using bucket sort.) By the way, you can allocate any amount of memory in constant time.

So maybe with the right smart selection of strategy, you can succeed in linear time.

Get an HP calculator; they're better :-)

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