Posts by Rashakil Fol

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.

Think about the only operations you can perform between two stacks if you have no extra memory, and you're sitting on top of the answer.

And if you think about it, a pair of stacks is quite similar in concept to a pointer in the middle of an array. One stack represents moving downwards in the array, and the other represents moving upwards.

You could create a lazy list datatype that only produces values when you request them -- and whose values it produces are the natural numbers. Then run the sieve of Eratosthenes on it. Then peel off the first 6 elements of the list.

Or you could use a vector that you grow whenever you need more elements and use the sieve of eratosthenes on that, or some modification thereof.

An alternative is to exploit the prime number theorem. Out of x numbers, the proportion of primes is ~(x/log(x)), so allocate a vector with max(C,ceil(1.15 * n*(1+log n))) elements if you want n primes, for some constant C that's large enough, and then use the sieve of Eratosthenes.

I guess this works better in a language that's lazy by default.

nPrimes n = take n (nubBy (\x y -> y `mod` x == 0) [2..])

I'm definitely not referring to you joeprogrammer.

Depending on your definition of "levels of nesting", you've got 0, 1, 2, 4, 5, or 8.

There are some people there who respond to a lot of posts without really knowing or understanding anything. There are a lot of people who do that here. That's okay; just pay attention whenever Bubba or Prelude or Salem or Dave Sinkula or Mad_Guy say anything. And machines like quzah are great. There are several real idiots, though, who say things that come from their own imaginary self-orbiting world. I might be one of them.

I just get really tired at their inane conversations.

So yes, it's a good site. At least morally. I don't know if it's the best. Some places know C better.

You might have x = y * CONSTANT where #define CONSTANT 0 is located someplace. That's how you could get that in your code.

Whether x = y * 0 is compiled to anything different than x = 0 is compiled to depends on the compiler.

Write one with three states: one for where it hasn't seen any vowels yet, one for where it's seen front vowels, and one for where it's seen back vowels. And a failure state if it has to be a deterministic FA. I'll leave the edges to you.

I think you can see the difference right there for yourself. This has nothing to do with optimization, unless you enable the -fretarded flag on your compiler.

Nobody can help you if they can't see the source code.

Tayster, is your post meant to be ironic?

Then you should learn C++. Taking from you the opportunity to solve this problem yourself won't solve this long-term problem.

You're missing a slash. You mean \\testload.

Sociopath

My test tracked 4 variables.
How you compared to other people your age and gender:
You scored higher than 99% on Rationality
You scored higher than 99% on Extroversion (but I am more introverted than extroverted...)
You scored higher than 99% on Brutality
You scored higher than 99% on Arrogance

First you need to describe what the '/' operator does: integer division or floating point division? Then you need to count the total number of fundamental operations that each algorithm executes, in terms of the variables at hand. Unless you've never found the running time of an algorithm before, you should be able to figure these out with some careful consideration. The first algorithm looks hard, but you can look closely at its constituent parts. The second algorithm: its running time should be very easy to analyze, if you understand the principle of counting how many fundamental operations the algorithm takes to compute.

No. There is no hope for you.

With no further information about the element or the array, you can't.

Okay, now we have an interesting Haskell snippet.

Sure.

In USA that would be a question most 8th graders could answer. You will be pretty lost in programming if you do not have at least that level of mathametical skills. You should probably take a remedial math course to bone up on algrbra and trigonometry. and there are many specialties of programming that require much higher level math skills.

WTF? This is a dumb comment.

intp

Yes, there are tutorials and websites to help you. Try reading the rest of this thread...

You find the time complexity for big programs the same way you find it for small programs.

There is no software that can do this automatically.

My keyboard is a buckling spring keyboard: http://us.st11.yimg.com/us.st.yimg.com/I/pckeyboards_1922_6667

My mouse is a Logitech MX 518.

4.What do you mean by 'text-based, console programs'?

Programs that operate over the standard input and standard output streams, that possibly expect parameters via command line arguments.

5.Why is it necessary to enclose every method in a class or interface in JAVA?

Because Java is a bondage and discipline language.

Urgent? How many people will die if we don't answer this question in time?

And why are you asking about the choice of "frequency and wavelength"? It's not like you're making two choices.

Why don't you try thinking about that question and coming up with an answer on your own.

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

Hi all. This question has been answered in IRC. If you came to this thread from a search engine, see http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html for an explanation.

mrclean, this question is complicated by the fact that you have multiple parameters to your first function, but only one parameter to your second function. Your second function runs in theta(n*n) time, yes. But take a look at your first function. Suppose you hold the value k fixed? Suppose you hold k fixed at 3, and then consider the running time as you vary n from 0 to an arbitrarily large number? You'll find that you run through the interior for loop approximately 3n times. If you fix k at any value, you'll find this to be the case, that you run through the interior loop approximately k*n times, if n is really large.

The interesting thing is, for values of n that are less than k, the growth pattern seems to be a theta(n^2). But after you increase n past the value of k, you'll find that the interior for loop gets run "k" extra times each time you increase the value of n by 1.

This leads to the interesting topic of what big O and big Theta notation really means. When you have multiple variables, it is not necessarily as straightforward an idea as when you have one. You could say that your first function has a running time Theta(k*n). What does that mean? You could consider the two directions in which you can grow the parameters of the running time function f(k,n) = k*n: increasing k while holding n constant and increasing n while …

This is not the more appropriate board; you should move it back to the CompSci forum.

That's supposed to be hard? That's not hard; that's mindless regurgitation. That exam doesn't even involve any thinking.

programming and "software engineering" are the same thing. If your school is offering a "programming" curriculum that is not called software engineering and is not called computer science, while offering a "software engineering" curriculum too, then I have to say, WTF?

There is actually no such thing as "software engineering," unless you work for NASA or other fields where the cost of failure is very high.

To answer your main questions:

- The average income of anything depends on where you'll be working.
- Your ability to get a job depends on how much of a non-moron you are.
- The stability of your job depends on how much of a non-moron you are.

no, endl should be the standard way to do things.
\n is not portable, it's a throwback to C.

How is \n not portable?

Just do the prodgect like eny ol foo wit that biz ness o urs so like there wit dat relational db and implement yo own cuz abt pmt fbi ada fcc cdc internets r 4 pone :( :).

Np enjooooooooooooooy lyf.

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

Lisp certainly is object oriented, if that's what you want. With Lisp's macros and lexical scoping, you can do anything. Common Lisp was the first ANSI-standardized object oriented language, ever.

Common Lisp is not really a 'functional' programming language, it's a language that lets you program the way you want. It has variables that you may modify -- that are mutable -- so you can use it in a brain-dead manner the way you would use C. You could also choose not to modify your variables, and you have lexical scoping, which means you can use it in a functional manner. Scheme is better at that, though, since CL is kind of weird with its 'apply' and whatnot. Lisp certainly is better for object oriented programming than, say, C++ or Java, in the general sense.

The best language for programs that need to retain state, though, is Haskell, IMO. No other language handles state transformation in a better way. None that I've heard of.

Object orientedness is really about having objects pass messages to one another. The purpose of inheritance in languages like C++ is to allow for a form of dynamic typing. Object oriented is really a subset of what Lisp offers, since an object is nothing more than a function that takes some finite enumeration of method names as its first argument, along with a list of further arguments. Common Lisp has more explicit object orientation, with classes and the like.

I don't see what the problem with that is. If the customer is interested in scum merchants, then that's the customer's choice to make. Are people to be babies that have their options obscured from them?

Dani, please see the attached screenshot.

I suppose somebody can.

You could say you have an irrational number, but what you really have is a pseudo-random sequence of bytes, that you're using to xor to the bytes of your plaintext. This is called a synchronous stream cipher.

And if you're capable of sending beforehand a one time pad that tells where the algorithm's parameters are stored in the text, why not just send the algorithm's parameters as the one time pad, instead of putting them in the text?

Well, you'd have to have a pointer to the top of the map, so that'd be 7*4 for the pointers, but of course that depends on what you formally define the 'map' to be in terms of calculating memory usage.

And there's also the fact that your memory manager will be using extra memory to maintain each of the nodes, something like 8 bytes, give or take a few multiples of 4.

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

one uses bytes whereas the other uses bits

Very simple one in brainfuck:

+++++++++++++++++++++++++++++++++++++++++++++++++.+.+.+.+.+.+.+.+.--------.-.

It really doesn't get any simpler...

Sorry, it does :)

++++[>++++[>+++>+++<<-]<-]>>+.+.+.+.+.+.+.+.+.>+.-.

Let's try another way of getting around the language filters and the people who have the disease that causes them to get offended at things.

So.

<< attempt to circumvent bad words filter >>

Now, this idea is a bit difficult. I don't know what Comp Sci you've been doing, but it's an interesting problem, since this target language is inherently less efficient than Scheme or C or C++ or Assembly language (or machine code). First, you need to understand the target language, Brainfuck. I suggest that you try to write some useful programs in the language before anything else. I hope you are not capable of doing the project without a second thought, because then there'd be no point to doing it. The real point of this will be to expose you to languages like Scheme, in case you haven't been, and more in-particularly, Brainfuck, the absurdity of which I think you might enjoy. This might be something you'd be more attuned to _after_ taking a theory of computation or programming languages class, but I don't care.

That doesn't sound like research to me...

arh, how about you write a compiler? Make a compiler for the Scheme programming language. Write the compiler in Scheme, too. Think about what optimizations you can make. Especially when it comes to dealing with call-with-current-continuation.

Oh, and have the target language be the language Brainfuck. I don't know of anybody who's make a Scheme-to-Brainfuck compiler. :-) You will have to omit file operations from the language's standard library, only input/output, of course.

Make a version that reads the input Scheme code in stdin, and then writes the Brainfuck code to stdout. Then compile the compiler into Brainfuck code!

Brainfuck is spelled B R A I N * * * *, of course.

Yes, let's lecture him on his daring choice of university while we twiddled our thumbs in our native-language universities.