Computer Science

12:19 AM

Right, I'm off to bed

good night!

Same to you and Gilles :)

@AlextenBrink It does not have to be fast in two dimensions. I don't care,frankly, I just don't have an example for my thesis! :/

(Actually, it would be nice if all natural problems were case 1 and 2, but still...)

12:58 AM

@Raphael I posted an answer to the unipathic traversal question

I hope it's true. I didn't find any use for the weights.

I turned out not to use a bound on the number of edges, and I asked a question about that (I know the answer, if I haven't made yet another mistake)

in a minute

soooo, edited in links under all my images so far.

@Raphael Hit the possible vandalism lock yet?

Don't worry, it goes away after a few hours

@Gilles Captcha?

@Raphael no, blocked from edits

Maybe it won't apply to you, because your posts are recent

don't see anything like that

1:03 AM

If you edit a lot of old posts in a short time, the system flags that as possible vandalism

clever system

e.g. an angry user removing the content from all his questions (“ragequitting”)

I've had that when I was doing maintenance over a bunch of my old posts

Thanks a lot for providing these sources

I need to find better tools to draw the various kinds of graphs

What do you use for commutative diagrams?

MathJax can't cope, and pulling up xymatrix to make a pdf then a png is more work than it should be

you mean these category theory thingies?

never done one, but TikZ is probably my first choice

texample.net/tikz/examples/commutative-diagram-tikz

Q: How many edges can a unipathic graph have?

0

A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex. Unipathic graphs can have cycles. For example, a doubly linked list (not a circular one!) is a unipathic graph; if the list has $n$ elements, the graph has $n-1$ cycles of le...

graphs

A: Non-trivial tractable properties of triples

I'll publish my tikz2png later this week

0

Let $S \subseteq \mathbb{N}^3$ with $|S| < \infty$ and $P_1(S)$ where $\quad \displaystyle P_1(S)\ \ :\Longleftrightarrow\ \ \forall (i,j,k)\in S. i,j,k \text{ mutually coprime }.$ $P_1$ is clearly non-trivial as requested. We say furthermore $\quad \displaystyle P_2(S)\ \ :\Longleftrightar...

what do I do with this guy?

1:13 AM

@Raphael I have no idea what he was asking

He's a regular on CSTheory, isn't he?

jup

I understand his question and even what he is aiming at with it, but it does not make a lot of sense. Nor do his feedback questions.

Was the diagram what you were looking for?

@Raphael which diagram?

oh, the tikz example? Yes, that's the kind

I used xymatrix in the past, and maybe others (I haven't used latex in the last few years, since I switched to industry)

tikz does look nice though

never used xymatrix

tikz is awesome, once you get the hang of it. The manual is very comprehensive.

Q: Delimited Continuations + Dataflow Unification = Arbitrarily invertible (pure, nonrecursive) functions?

4:53 AM

0

Assume we are working in a Turing-complete, referentially-transparent, higher-order language that supports arbitrary dataflow unification. Shouldn't it then be possible to construct the following function (using Haskell-like syntax, because that's what I'm most familiar with)? -- Takes an arbit...

programming-languages

CS Meta

5:47 AM

1

Q: rename tag: randomized-algorithm -> randomized-algorithms

the tag was created, deleted(?), and then re-created with a typo, and it does not let me change it. (it says something alike 'the randomized-algorithms cannot be created since randomized-algorithm already exists.. raise this issue in meta')

discussion tags

Q: How can we express this NFA as regular expressions?

9:32 AM

0

If I understand well, NFA has the same expressive power as regular expressions. However, Consider the following NFA. Its intial states is its leftmost node, terminating states are all the other. Its transition rules are expressed by te arcs. This NFA recognizes words like x f g i f g h j g i f g...

automata regular-languages

10:32 AM

@Raphael the question was: k-way-mergesort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, and so on until you merge in the final (kth) input array.

What is the time taken for this strategy, as a function of k and n ? (Optional: can you think of a faster way to do the k-way merge procedure ?)

That is going to be \Theta(n^2), and it can be done faster, yes.

but it is a nice question

It was multiple choice between:

- O(nk)
- O(n^2k)
- O(n log(k))
- O(nk^2)

but best not to spoiler the answer

n log k sounds about right

I ended up getting it right with trial and error, but I don't like that approach

btw, the question is posed stupidly. O(n^2 k) subsumes all the other classes, so can always check that

10:46 AM

hehe, indeed it can :P

> Let 0<α<.5 be some constant. What is the probability that on a random input array, PARTITION (for quick sort as explained in lectures) produces a split in which the size of the smaller subarray after the PARTITION subroutine is ≥α times the size of the original array?

you might have to argue so they accept it ;)

I have a hard time parsing this question

I think you should post the k-way merge question on the site.

then an answer is accessible for others

the options are
1-alpha
alpha
1-2*alpha
2-2*alpha

@Raphael well, we'd have to rephrase it, we don't want to ruin the quiz for everyone

so the answer would have to explain how to come to your conclusion, rather than outright telling it

(who does multiple choice for algorithmics?! stupid/lazy teachers...)

@IvoFlipse of course

10:47 AM

@Raphael yeah, I wouldn't have had an idea without the choices

the question can be properly motivated: assume you have k cores, then k-way split is useful. how to merge efficiently?

@IvoFlipse exactly. they should teach how to solve problems, not check the correct answers

I learned more from programming quicksort myself than from trying to do the quiz

we had to calculate the number of comparisons if you take different pivots

obviously

hehe, that can be hard

well just because you get a sorted array doesn't mean you're doing it right :P

I learned that the hard way

thank god shifting the pivot uncovered several errors in my implementation

with that probability question, should I expect the probability to get smaller when alpha get's larger? I mean the alpha ensures that we always pick a pivot in the first half of the array, so how can the subarray after the pivot be shorter :S

regarding quicksort, a smart person once said that every version you find in a textbook contains at least one bug. A colleague even found bugs in Sedgewick's thesis

10:53 AM

Hehe, didn't Knuth say he only proved they were correct

exactly :D

@IvoFlipse your pivot depends on alpha?

the question is: how unbalanced can your split be?

if your pivot is random, the expected length should be n/2, therefore small alpha should mean high probability

or the reverse, yes

I guess I should have paid more attention when he explained it, but watching 3 hours worth of algorithms discussion get a bit boring at some point

@Raphael If that were true, it would be 1-alpha, which was incorrect

Since the pivot is chosen uniformly at random from A[p::r ], the
return value of the rst call to Randomized-Partition(A; p; r )
is distributed uniformly at random in the range p; : : : ; r . Thus if k
is the size of the left-hand list (the size of the right-hand list then
being n 􀀀 k 􀀀 1), its possible values range from 0 to n 􀀀 1,
inclusive, with each size occurring with the same probability 1=n.

Hmm wrong again :\

11:16 AM

@IvoFlipse why not 1-2\alpha?

sorry, I can't do this kind of debugging right now

@Raphael I have no idea, well it must be the right answer, because the others are wrong or not plausible

2-2*alpha = larger than 1

If you are honestly puzzled and have no idea how to get a result in a constructive way, please write up a question for the main site.

these questions are not trivial for somebody in an algorithms course; it just does not make sense to examine them like that

11:43 AM

@Raphael Well I've been thinking about how to ask the k-way mergesort question, but can't find the right words

mostly because I probably don't understand the problem well enough :\

I'll first try and read the relevant chapters from CLRS

then ask as best you can, we'll help you

that is also a good idea

12:31 PM

@IvoFlipse I've only just arrived - what is the question you're working on?

k-way-mergesort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, and so on until you merge in the final (kth) input array.
What is the time taken for this strategy, as a function of k and n ? (Optional: can you think of a faster way to do the k-way merge procedure ?)

I skimmed the conversation, but I have probably missed something

I don't think I understand how they got to the answer, but I'm not sure how to phrase it so I can ask it

You can merge two arrays of size n1 and n2 in O(n1+n2) time, right?

yeah its just O(n) time

12:34 PM

And your i-th merged array has size i*n

So it takes \sum_{i=1}^k O(i*n + n) time

if only that mathjax would render ;)

Which is n * \sum_{i=1}^k i

Which is n*k^2

O(n*k^2), that is

Is that one of the allowed answers? :)

It is

@AlextenBrink ith merged array? how many i's would there be?

In the first step you merge array 1 and array 2 into 'merged array 1' (let's call it that)

In the second step you merge 'merged array 1' and array 3 into 'merged array 2'

And so on

So you'd have k or k-1 merged arrays, I think k-1, but that's not very interesting

Yeah, I can see that part

12:38 PM

Merging an array of size n1 with an array of size n2 takes O(n1+n2) time

And the i-th merged array has i*n elements (by induction)

And then my analysis follows

@AlextenBrink the number of merged * the size of each slice of the input right?

Yep

@AlextenBrink so how do I read this part, because I'm not really familiar with the raw formula like this

You mean my \sum_{i=1}^k O(i*n + n)?

yeah

12:41 PM

Sorry: you sum over all i in 1, 2, .., k the expression O(i*n+n)

So O(1*n+n) + O(2*n+n) + O(3*n+n) + ... + O(k*n+n)

You add up the running time of all k merges

I think it's k-1 merges btw, but that doesn't matter in the asymptotic analysis

and the sum of all those k-1 merges is k-1 * (n * k)

Times a constant, actually, but the O notation takes care of that

Sec, changing rooms

Summation

Summation is the operation of adding a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum, or running total of the summation. The numbers to be summed (called addends, or sometimes summands) may be integers, rational numbers, real numbers, or complex numbers. Besides numbers, other types of values can be added as well: vectors, matrices, polynomials and, in general, elements of any additive group (or even monoid). For finite sequences of such elements, summation always produces a...

Fourth identity in that list

That's just gibberish to me :)

This one?

Yep

Essentially, n + n + n + n + ... + n (so n times '+n') grows about as fast as 1 + 2 + 3 + 4 + ... + n

I have a feeling I simply haven't 'studied' the right material yet, if you guys can solve it so trivially

though looking at the algorithms-class forums, I'm not the only one struggling with the question :P

12:54 PM

That is possible: after I passed the algorithms course at my university, I would have solved this without issues I think

Then again, that was 3 years ago, and I've basically been continuously practising ever since

But you do need to get practice in these things: I don't think I would have gotten this one right before I had done my algorithms course

yeah I'm not sure if it would make for a great question, unless its to show the basics of these kind of calculations

That image you linked is a very useful trick that bites a lot of people who haven't seen it yet

For instance, it tricks people into thinking that Insertion Sort is more efficient than Bubble sort - it is, but not asymptotically so

1:11 PM

@IvoFlipse Did you find the answer to the second part of the question? The part about doing better than that merging strategy?

@AlextenBrink I didn't bother yet

Ok

Ah, it's optional

yeah, I have more courses to work on, so I'll have to revisit this 'later'

Well, if you're interested, I know the answer to that one as well :)

hehe, I'm still interested, but I'll first try to read up on it some more

1:20 PM

Ok, that's fine :)

1:41 PM

Don't sum O-Terms!

@IvoFlipse tug.org/texshowcase/cheat.pdf

my boss looked over my shoulder, saw Gauss formula up there and was like "Awwww..." :D

once you have seen it 200 times...

@Raphael Wow, that is one huge cheat sheet...

@AlextenBrink cs.stackexchange.com/a/695/98 <-- I wanted to avoid that explicitly

the OP has no problem applying a technique, he does not know a technique.

@AlextenBrink You don't know it?! O.o

I think seeing a technique in action usually greatly helps with understanding what is going on

A lot of times, I only see a general theoretic treatment, where one simple example can give the insight needed to understand the theory

@AlextenBrink my link contains a full example. the OP should at least try to apply it to the given automaton

Oh, I missed the second page of that pdf >.<

Then my answer is indeed not pedagogically responsible

1:53 PM

Sorry for invalidating your hard work. You should probably keep the source even if you retract the answer; the OP might come back.

btw, if the commentor is correct (in the sense that the image conforms to your result) I think you made a mistake. The loops do not seem to be overlapping

@Gilles the document is hosted on my own server so barring catastrophe or my complete withdrawal from SE, I have control over the link. But I see your point.

If you merge the top state of that image with the second state from the left, the DFAs are isomorphic

yea, I see

Fix't

:)

2:38 PM

cs.stackexchange.com/a/696/98 what's this? Jukka has high networ rep, I wonder what he was thinking.

2:55 PM

Ahhh

sam

3:54 PM

Hello everybody, I have question on 'Is it suitable to ask AI questions on Computer Science board?'

Thank you.

1

Q: How does a 2 way pda work?

Note: I mean a Push Down automata that can move it's reading head two ways on one stack. I recently had the question of determining the computational power of 2 way PDAs in the chomsky hierarchy. I don't entirely understand 2 way PDAs, but I can see how giving the machine just slightly more powe...

pushdown-automata

@sam Definitely! AI is a sub-field of CS, right?

@sam As long as it is not something like "When will machines take over?"

There is even a tag "artificial-intelligence" that suits such questions.

it's kinda slow today, ain't it? And the weekend does not seem to be better.. ):

sam

4:16 PM

@RanG Thank you for answering my questions.

@Raphael Thank you for hint.

@sam Sure! welcome.

@RanG unfortunately, yes :|

I want to write some question about coding-theory. Maybe during the weekend I'll have the time

@RanG that would be good!

5:23 PM

@sam What would the question be?

Q: Restricted versions of the PCP

0

The Post Correspondence Problem (PCP) is undecidable. The bounded version of the PCP is $NP$-complete and the marked version of the PCP (the words of one of the two lists are required to differ in the first letter) is in $PSPACE$ (1). Question 1: Are these restricted versions used to prove some...

complexity-theory

7:22 PM

Hi

Anybody?

7:37 PM

@PratikDeoghare Hello

hi @MichaelMrozek

are you interested in computational complexity theory?

I have 1 rep here, so let's assume in all such cases I'm not smart enough to even know what you're talking about

But have you the basic idea? My question is non-technical :)

I know what it is, yes

my problem is I am not enjoying complexity theory(CT) much but every other paper published proves this his that-hard and stuff like that

i wanted to ask someone if I could get by without complexity :D

I like algorithms design. I like proving things. Solving problems but not merely proving that problem is hard.

whats the use? :D

7:44 PM

Get by while doing what?

I mean bypass complexity theory

to become a computer scientist without complexity theory

so I am waiting for some prof to turn up here :D

Q: How can wireless router password encrypts data using WEP and WPA

0

I am not sure if this site is a good site where I can ask questions about wireless networks. Please if it is not a good site and you know good one give it to me so I can you use it in the future. My question is I want to know how the password that we enter (to connect to a wireless network) encr...

computer-networks encryption

9:09 PM

@PratikDeoghare I may get some flak for this from certain people here, but yes, it is possible

Program verification (semantics) hardly ever uses complexity theory

Even basic verifications tend to be superexponential, but no one writes worst-case programs

We're happy when we find an interesting decidable property

That isn't to say complexity theory never comes in handy, but you can go a very long way without encountering it

Q: Finding exact corner solutions to linear programming using interior point methods

3

The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior point methods walk the inside of the polytope. As a result, when a whole plane of the polytope is ...

algorithms optimization

On the other hand, algorithm design involves a lot of it

9:46 PM

@Gilles what about computational geometry? When I looked at some papers by JeffEricson there is no mention of complexity classess?

@PratikDeoghare no idea, I know nothing about CG

What do you mean by 'complexity theory'? General algorithms analysis or rather NP-hardness results and the like?

NP-hardness results and results about relations between different complexity classes

Just so I know we're talking about the same thing before I try to give an answer :)

@PratikDeoghare Many times, you are busy with polynomial problems,anyway. Look at all the questions of @AlextenBrink

9:47 PM

Goes to check his own questions

37 mins ago, by Gilles

Even basic verifications tend to be superexponential, but no one writes worst-case programs

:p

you should know about P, NP and NPC (including reductions); the rest of complexity theory can be ignored for many purposes.

Ah, yes, it seems you're right

@Raphael thats very helpful!

:)

this minimum can not be ignored,however;you have to be able to recognise a "hard"problem when you see it.

9:49 PM

Another question: what kinds of fields are you interested in?

@Raphael you realise them by gut feeling anyway ;)

It varies from field to field a bit

algorithms

?

@PratikDeoghare Sometimes hardness results can be surprising

@PratikDeoghare Yea, but where does a good gut feeling come from?

9:50 PM

For instance, geometric algorithms usually are about getting an O(n^2) or O(n^3) down to O(n log n) or O(n)

@Raphael solve a lot of programming competition problems

an interesting one: 2KNF-SAT is in P, 3KNF-SAT is NPC, 3KNF-MAX-SAT ist NPC -- what is 2KNF-MAX-SAT?

@Raphael this is exactly what I don't like or care about! :D

@PratikDeoghare wrong answer. I guess; never did such competitions

If however you are trying to build a compiler, you can easily be tricked into trying to tackle hard or impossible problems

9:51 PM

but you have toknow,as a programmer,what patterns ofproblem to be wary about.

hummm

For programming competitions you don't need to know anything about complexity

Just about running times

@AlextenBrink good point

I've participated in several programming competitions

@AlextenBrink Yes. For a long time I was thinking that I knew CT then cstheory.SE cleared my head.

9:52 PM

In fact, a few people I know got into the world competition

I guess CT is unavoidable but what is absolute minimum required complexity theory?

@PratikDeoghare There's hardly any subfield of CS you can even get close to knowing a lot about

The most practical are NP hardness, undecidability and approximation ratios

Be able to recognize if something is hard or impossible

@PratikDeoghare haha, that is like taking a duckling to a NASCAR race

:)

@AlextenBrink That.

And: know where tolook

Garey-Johnson on your shelf, you can always find out.

9:55 PM

And it also helps to know a bit about approximation algorithms and have some intuition there

In case you can't avoid solving an NP-hard problem

@AlextenBrink Jup, some "hard" problems can be approximated very well,others resist such attempts.

parametrised complexity is also relevant for practice.

@Raphael I don't mind not solving such problems.

For instance, Knapsack is NP-hard, but you can approximate it extremely well and can compute most of the typical instances very quickly

On the other hand, general TSP is completely impossible to approximate and you can't really do better than O(n^2 2^n) for the exact answer

Vertex Cover can be done in something around O(1.3^n)-- way faster.

This is a good link to bookmark: nada.kth.se/~viggo/problemlist/compendium.html

2

9:59 PM

@AlextenBrink is it in the tag wiki yet?

No idea :P

one more question

@AlextenBrink well, put it there! No one will find the link in the chat.

@Gilles +1

@Gilles Ok

@PratikDeoghare Go ahead