Computer Science - 2014-05-19

« first day (803 days earlier) ← previous day next day → last day (3622 days later) »

1:22 AM

Was playing with prime number generation last night and wondered if there is a name for the following (inefficient) process.

Unix pipish... filter class has int and link to an instance of filter.

For (ints from 2 to MAXNUM){. ask filter if current num is prime. Filter compares num to it's private int. If a multiple return false, if filter does not link to another filter create one with the current number and return true} else { return the result of the linked filter}

sorry about the poor formatting.

I wondered if that algo has a name.

6 hours later…

7:09 AM

@Sukotto What does Filter do? Please create some pseudocode on Pastebin or Gist, I don't understand your algorithm.

7:36 AM

Well, folks, I have been looking on the site pretty much for the first time in a week. Can anybody tell me what the value of questions such as this is?

1

Q: Sum of all nodes from A to B in a Tree

Given a Tree and pointers to two of it's nodes A and B (a key value of each node is positive). Find an algorithm that sums up all the values on the path between A and B, when preproccessing is allowed.

algorithms data-structures trees

Votes would indicate that it's a highly attractive Q-A-pair. I don't see any value if we want the site to be more than just a test-question repository.
(Note in particular that the answer gives no justification at all; apparently that enough to satisfy the "needs" of the asker.)

@Raphael it's a reasonably-scoped but zero-effort, badly-written and little-interest question

looks like it should be downvoted but not closed

I think we see clearly that a significant part of all voters disagrees; they like the crap.

It's better on this one, maybe because it's an obvious dump:

-3

Q: Word count pseudo map reduce

Suppose we execute the following word-count MapReduce program on a large repository (such as a copy of Wikipedia), using 100 Map tasks and some number of Reduce tasks. class MAPPER method MAP(docid a, doc d) for all term t ∈ doc d do EMIT(term t, count 1) class REDUCER method REDUCE(term t, cou...

algorithms terminology algorithm-analysis

@Raphael hup, too broad

@Gilles I don't see how it's "too broad", and I also don't see why we would close this but not the other one.

They are equally bad.

@Raphael it's a bigger exercise than the other one

7:50 AM

@Gilles In word count, maybe. Does that matter?

it's also less useful in that it has fewer applications, it's an ad hoc exercise whereas the tree one could be useful as part of a tree processing algorithm, so if on the fence, I'd lean towards leaving the tree one open and closing the mapreduce one

-2

Q: Amortized analysis of copying a stack

This is a question I have stumbled upon in my algorithms textbook: A sequence of operations is executed on a stack of size K. After every k operation, the whole stack is copied for backup reasons. Prove, using the counting method, that for every $n$ operations executed on the stack,...

algorithm-analysis runtime-analysis amortized-analysis

Okay, that one passes as containing something that may resemble an own approach.

@Raphael what is “A and B”?

oh, I guess it's the two questions

I don't like this. We are deep in "subjective policy" land. I've always disliked this about [cstheory.SE]: skrew our scope definition; if we consider the problem interesting on some level, we keep it, and burn it to the ground otherwise.
My "close all dumps"-policy was clearer, fairer that way.

Anyway, what I notice most after last week is abysmal tagging. :/

How can we "make" regulars edit tags? They probably don't even look because they check most questions, anyway.

8:06 AM

@Raphael on U&L, it's only been a few months since people other than me have become interested in tagging. So, I don't know.

@Gilles Oh dear. :|

Do you think we could have some heuristic for putting badly tagged questions in a review queue? The system could look at questions with only one tag, no common tag, many new tags; or do even more advanced stuff like "contains tags that almost never occur together in other places".

@Raphael hmm, interesting idea. I don't remember seeing it on MSE. SE has heuristics for finding applicable tags based on the question body, but they're only enabled on a few sites. They work reasonably well on MSE. I remember the developer saying it wouldn't work on smaller sites

This could be a feature request… or even a Computer Science question if you start thinking what heuristics could work

31

Q: How are "Suggested Tags" chosen?

After you've typed in a question, you get suggested tags that appear that look like this: It appears that you need a minimum amount of characters (much like the limit on 'Similar Questions' in the right-side pane): you must have entered a title (any length) and a minimum body length of...

support tags suggested-tags

meta.stackexchange.com/questions/tagged/suggested-tags

8:25 AM

I "proposed" it a while back, but that one was too unfocused. I've been meaning to extract some concrete feature requests from that (mod-send question to review queue; time-delayed self-flag for mods; send comments to chat) but have not found the time yet.

I'm not sure automatic suggesting is a good thing. People who use "complexity" errorneously in their algorithm analysis question will, for instance, get the suggestion to tag complexity-theory, not algorithm-analysis. Or so I'd think.

Afk, talk later!

@Raphael I know that comments→chat and delayed self-flags have been requested before, not sure about sending into review but I think so too

4 hours later…

12:57 PM

Oh dear. If I ever needed a reason not to visit Christianity, this is it. The comment and the fact that no one reacts to it.

@Gilles I'd be surprised if they were not. :/

@Raphael you mean Christianity is the second-worst SE site about religion? I can believe that

@Gilles I did not check Islam or Mi Yodeya, but I'd expect the three to be about the same level of "?!?!".

(Go me, getting the name right on the third try. :|)

what, Mi Yodeya?

(spelled [judaism.se])

@Gilles (Yea, I got it after reading "jewism" and facepalming myself. :D Unfortunate choice of name, anyway; the religion has little to do with Judaea, nowadays and arguably.)

3 hours later…

3:43 PM

sukotto sounds like a variant on this

Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes (), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them which is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each pri...

Abdussami Tayyab

4:15 PM

@Raphael @vzn Just gave my Analysis of Algorithms, would you like to see what the questions were? Can I share them?

2 hours later…

5:59 PM

@AbdussamiTayyab "Gave"? Handed in your solutions, you mean? Or did you give the course?

Abdussami Tayyab

6:42 PM

Handed in my solutions.

Wandering Logic

7:12 PM

@Gilles The specific internals don't matter. What is interesting is the interaction of a data-race detector that is working with virtual addresses in situations when those virtual addresses might map to different physical addresses.

It's an interesting question about a paper that appeared in OSDI '10. OSDI is one of the top conferences in OS. I'd like to think that detailed questions about the recent research literature in OS are on-topic in cs.se.

We get an interesting OS question about once every couple of months, where by "interesting" I mean that I have to do some work, some reading, some non-trivial searching and/or some thinking to answer it.

As opposed to the typical "OS question" we get about how many addresses you can point to from a page table page in a system with 32-bit page-table entries and 4k pages.

2 hours later…

8:51 PM

@WanderingLogic In that case, the best way forward is probably to edit away the Windows reference?

9:24 PM

Naive prime number filter: pastebin.com/EFGpvkPT Does this algorithm have a name?

@vzn, I implemented the sieve of eratosthenes first :)

@Sukotto What is the idea?

In abstract terms, I mean.

create a chain of filters, each detects if a given number is a multiple of a particular number. If not, they pass the number to the next filter.

Looks like the naive "check all potential factors" algorithm to me, so there's probably no name.

if you reach the end of the chain, the number is prime.

The list of filters is obsolete, isn't it? Any Iterable will do the job.

9:29 PM

There are many better ways to do it :). Thus "Naive"

Wandering Logic

@Sukotto the linked algorithm is exactly sieve of eratosthenes.

not as I understand it. The sieve starts with the ist of numbers, iterates over the list crossing off all multiples.

Wandering Logic

It's a chain of filters. Every time a number makes it through the entire chain it's prime, and you add a new filter for that prime.

this looks at each number and sees if it is a multiple. breadth vs depth

perhaps my understanding of the sieve is flawed.

@Sukotto Breadth vs depth does not justify calling it "another algorithm" in some contexts.

Wandering Logic

9:32 PM

I'm not seeing where there is a choice of breadth v. depth.

It's a linear linked list. There's only one way to traverse it.

fair enough.

Wandering Logic

i suppose you could traverse it from either end.

but the end they are traversing it from is better: you get rid of all the even numbers without recursing more than once. All the mults of 3 you get rid of on the next recursion, all the mults of 5 on the following, etc.

hm. array-based sieve you could. Not sure how you'd do that with the linked list

At some point, you are switching from algorithmic to implementation concerns.

Algorithmic idea: check all potential (prime) factors explicitly.

Algorithmic detail: iterate from 1 to N. Store all primes you find and iterate for every i over all primes found until now and check whether any divides i.

Implementation: Use lists/array/... and `mod`/... and so on.

Wandering Logic

traverse it the other direction? every iteration of filter.isPrime(i) returns a filter, either the same one you put in or a new one. Then you chain them together where the newest points to the one just older. But the way they do it (the right way) the oldest points to something a little newer (and thus a larger prime).

What @Raphael said. Linked lists, arrays, forward, backward, it's pretty much the same algorithm (perhaps with some small constant multiples different in runtime.)

9:39 PM

Ok, so it's just a different implementation of the classic sieve. I thought it might be different thus attributable to some other person.

Wandering Logic

The greek geometers are so awe inspiring that they don't need to share attribution. :-D

2

@Sukotto I actually think it's different from the sieve -- worse, in fact. The sieve touches every number once, assuming you start by "writing" them all in a linked list. The algorithm you link touches every number multiple times.

It truly is the "naive" algorithm which certainly does not require attribution (imho) no matter how convoluted the implementation.

oh yeah, it's clearly worse. :)

Wandering Logic

9:56 PM

@Raphael I'm not seeing how the sieve only touches each number once. If it's a linked list you need to iterate through the entire remaining list of not-known-to-be-composites and strike out the composites divisible by p. 77, for example, needs to be visited as you traverse the 3s and 5s and then doesn't get struck out until you traverse for the 7s.

Ah, I don't think my "analysis" of the Sieve was correct. It "touches" more like \sum_{i=2}^N N/i (about N log N) numbers (all multiples of all numbers in the interval). The linked algorithm performs \sum_{i=2}^N (#primes in [2..i-1]) checks; since the summand is about i/ln i this is properly less than the Sieve. My bad.

Wandering Logic

We hit enter simultaneously.

Indeed. *high five*

I rescind my judgement: the term "naive" does not apply to this algorithm. If a worse one has a name, so should this one. Which leads us back to step 0.

(But now, this makes a good question for the site: this is the algorithm, this is why it's better than a named one, so it should have a name -- which is it?)

Wandering Logic

I still claim that Greek geometers don't have to share credit.

A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore the latte...

Aaaand another data point in the growing list of evidence for my hypothesis, "Wikipedia sucks for algorithmic content".

10:08 PM

there is a slight difference between a recursive filter construction for sieve of eratosthenes.

eratosthenes algorithm marks off multiples more than once.

a filter construction might not do that.

in the sense that later filters work with more "compressed" chains of integers, only storing the "holdouts".

iirc abelson & sussman "structure & interpretation of computer programs" might have this construction in their study of lazy evaluation/"streams" etc.

Oh dear, I wrote crap again. Sieve has \sum_{i <= N, i prime} N/i which is more wicked to evaluate. Good thing there people who are not too tired to write down sums.

10:43 PM

user image

« first day (803 days earlier) ← previous day next day → last day (3622 days later) »

Transcript for

May '1419

Computer Science

General discussion for cs.stackexchange.com

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile