Computer Science

2:40 AM

Can I make this code better?

def reverse(str):
    if len(str) == 1:
        return str[-1]
    else:
        return str[-1] + reverse(str[:-1])

Because len() is called n length times.

vzn

3:40 AM

@overexchange write a loop! the code is correct & acceptable for a study in recursion...

fyi java has a string reverse built into StringBuffer/ StringBuilder!

CFP: Fifth Workshop on Social Computing and User-Generated Content / turing invisible hand blog

vzn

4:56 AM

wow! crowdfunded science. now how about in CS?

Crowdfunded science is here. but is it legit science? / wired

couldnt find cs stuff on walacea & petridish but experiment has 10 CS prjs!

huh! amazingly all 10 are over 100% funded!

example big data/ graphing/ visualization prj

Big data and the law: should we graph the entire justice system?

user2025998

12:23 PM

Can anybody check if my solution is correct?

i) FYa = {s0, s1, s2, s3}
ii) YFa = {}
iii) G(Ya->b) = {s1, s2, s3, s4}
iv) G(a->Yb) = {s2, s3, s4}

b)
G(a->Yb) EQUALS G(b->Xa)

The exercise is from an old exam for the course "Formal Methods".

user2025998

12:46 PM

ad iv) G(a->Yb) = {s2, s4}
s3 is not correct

Thomas Klimpel

1:13 PM

There's a proof in Section 17.3.3 of Computation Engineering: Applied Automata Theory and Logic by Ganesh Gopalakrishnan — Pål GD 2 hours ago

2

Q: Prove that it is undecidable whether a Deterministic LBA accepts an infinite number of inputs

Deterministic Linear Bounded Automaton (LBA) is a single-tape TM that is not allowed to move its head past the right end of the input (but it can read and write on the portion of the tape that originally contained the input). How can I prove that it is undecidable whether a Deterministic LBA ...

The first link turns up an earlier section of chapter 17, which seem to indicate that the emptyness problem for determinstic linear bounded automata is undecidable, by an argument closely related to the prove in the answer to the question in the second link.

Is this correct? Is the emptyness problem for deterministic linear bounded automata really undecidable? (Of course I could just ask this as a "real" question, but I just asked such a question with a well known answer today, so...)

It seems that it is really undecidable. On page 6 of research.cs.queensu.ca/home/cisc462/moni/m4.pdf, it says "If not separately mentioned, here a linear bounded automaton means a deterministic LBA.", and then proceeds to state (without proof) that the emptiness problem for LBA is undecidable.

user2025998

1:32 PM

ad b)
G(a->Yb) EQUALS G(b->Xa)
is not correct

I think the correct equation is:
G(a->Yb) EQUALS XaUb

vzn

4:57 PM

@ThomasKlimpel there is a great table in introduction to automata, languages & computation hopcroft/ ullman (1st ed, classic in the field) that covers most of these language undecidability questions, which were discovered in mostly early days & havent chged much. will look it up. unf its not so great on the refs/ citations to original proofs.

p 281. fig 11.5

LBAs are equivalent to the CSLs. the table gives a column for CSLs.

"L=∅?" undecidable for CSLs. thats the "emptyness" (empty set) problem.

but the question is on whether the language of an LBA is in/finite, not the same...?

this seems a bit tricky. is there something simple am missing? the table does not seem to cover "is [x] in/finite"? there is one approach/ angle that a regular language RL can represent any finite language, & one can do operations on languages with RLs, but it has to be a specific language...

the book is from 1979. interesting, it says that whether the complement of a CSL is computable is an open question. wonder if that is still the case. shows that there maybe/ are still some deep unanswered questions in the area.

Thomas Klimpel

5:27 PM

This is just the question whether deterministic LBA and nondeterministic LBA can recognize the same languages, i.e. the first LBA problem.

vzn

ideally somebody eg wikipedia would reproduce these excellent tables, with full refs! a job for someone enterprising... :) it would certainly relate to a lot of se questions... we have the massive/ well maintained complexity zoo, yet this table would seem even more basic. have wished for such a resource several times wrt se site Q/A, even have had Qs myself on this on the site.

Thomas Klimpel

Linear bounded automaton

In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. == Operation == A linear bounded automaton is a nondeterministic Turing machine that satisfies the following three conditions: Its input alphabet includes two special symbols, serving as left and right endmarkers. Its transitions may not print other symbols over the endmarkers. Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker. In other words: instead of having potentially infinite tape on which to compute...

vzn

@ThomasKlimpel youre confusing me, you are asking several different problems.

Thomas Klimpel

Sorry, this was an answer to your question "the book is from 1979. interesting, it says that whether the complement of a CSL is computable is an open question. wonder if that is still the case. shows that there maybe/ are still some deep unanswered questions in the area"

Oh, I see, my answer was wrong. Your question/observation was in fact the second LBA problem, which has been solved in the meantime by the Immerman–Szelepcsényi theorem

evinda

7:07 PM

@vzn @YuvalFilmus Hello!!!
I want to write an algorithm that finds an optimal vertex cover of a tree in linear time $O(n)$, where $n$ is the number of the vertices of the tree..

A vertex cover of a graph $G=(V,E)$ is a subset $W$ of $V$ such that for every edge $(a,b)$ in $E$, a is in $W$ or $b$ is in $W$.

In a vertex cover we need to have at least one vertex for each edge.
If we pick a non-leaf, it can cover more than one edge.
That's why I thought we can do it as follows:
We visit the root of the tree, then we visit one of its children, a child of the latter that we visited and so on..

evinda

8:53 PM

Do you have an idea @vzn ?

vzn

9:15 PM

@evinda are you an undergrad? suggest converting the formalism to using your own words. study breadth-first vs depth-first traversal of a graph. ponder how a optimal vertex cover on a tree is different than one on a (general) graph. personally like sedgewicks book "algorithms" on this stuff.

@ThomasKlimpel what do you mean 1st & 2nd LBA problems? cant keep track you seem to be talking about several & mixing them up.

evinda

@vzn Yes, I am.. I wrote the description of the algorithm by my own.. Is it wrong? I have studied breadth-first vs depth-first traversal of a graph.
So have I calculated the time complexity wrong?

vzn

ev can you describe a vertex cover in english rather than math language defn?

Thomas Klimpel

@vzn The first LBA problem is whether the class of languages accepted by LBA is equal to the class of languages accepted by deterministic LBA. The second LBA problem is whether the class of languages accepted by LBA is closed under complement. The second LBA problem has an affirmative answer, which is implied by the Immerman–Szelepcsényi theorem proved 20 years after the problem was raised. As of 2014, the first LBA problem still remains open.

evinda

@vzn Suppose that we have a graph G=(V,E). E is the set that contains all the edges, i.e. pairs of vertices. If we have a vertex cover, that means that at least one vertex of each pair of vertices is contained in the set of vertices we are looking for.

vzn

9:35 PM

ev try doing a vertex cover of a tree by hand, do 1 example. think it will have a "special property." what is it?

what country are you in?

hint: the proof of correctness of your algorithm will be nearly the same as the algorithm. what is the proof that your algorithm gives the optimal cover?

evinda

@vzn Suppose that we have for example the following tree:

@vzn An optiman vertex cover contains the following red vertices, right?

So we go through all the vertices, till we reach the first leaf and then we take the father of the leaf because a non-leaf can cover more edges. Then the edge that connects the vertex that we chose with the father of the vertex that we chose is covered and so we check if the father of the father of the vertex that we chose has not been taken, and if it is the case, we pick it and so on, right? @vzn

vzn

9:51 PM

think this is probably an exercise in filling out this statement: "for a tree, the optimum vertex cover always..."

in other words, simple english language, in a vertex cover, every edge in the graph is incident onto one of the vertices in the cover right?

huh look at this

6

Q: Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover). For each internal node: if any of its children is not selected, then select this node. How do I prove th...

algorithms trees greedy-algorithms

evinda

@vzn Yes.. The algorithm is the same as the one I have written, right?

   DFS(node x){
      discovered[x]=1;
      for each (v in Adj(x)){
          if discovered[v]==0{
             DFS(v);
             if (v->taken==0){
                 x<-taken=1;
             }
          }
      }
    }

@vzn But isn't its time complexity T(n)=Σ_{i=1}^{|V|} O(|V_i|+|E_i|) <= Σ_{i=1}^{|V|} O(|E_i|) <=Σ_{i=1}^{|V|} O(|E|)=O(|V| * |E|)

Or am I wrong?

vzn

ev you seem to have endless questions for me but wont answer some of mine. :(

evinda

This was my main question.. @vzn

vzn

10:11 PM

ev and what about my question(s)?

wow am surfing & just ran across this

girlswhocode.com

some startling statistics

> Women represent 12% of all computer science graduates.
In 1984, they represented 37% of all computer science graduates.

evinda

@vzn Which are your questions?

vzn

@evinda the sentences that end with "?"

> In middle school, 74% of girls express interest in Science, Technology, Engineering and Math (STEM), but when choosing a college major, just 0.3% of high school girls select computer science.

evinda

I answered this: in other words, simple english language, in a vertex cover, every edge in the graph is incident onto one of the vertices in the cover right? with yes.
So you mean the following?

what country are you in?
hint: the proof of correctness of your algorithm will be nearly the same as the algorithm. what is the proof that your algorithm gives the optimal cover?

vzn

are you undergraduate? what country? what major?

evinda

@vzn Yes, Greece, applied maths

vzn

10:18 PM

ok what yr class is this for? 1-4?

@vzn 3

is it a CS class?

Yes @vzn

the complexity of the greedy algorithm is trivially linear. try to figure out why.

is there any online material for the class? eg class syllabus/ notes etc

applied math, cool major :) ... was recently admiring some (potentially revolutionary) applied math (by MIT phd, on solitons/ fluid dynamics) that the physicists were heavily criticizing :(

evinda

@vzn That's the point I got stuck.. I don't know how we deduce that the algorithm is linear.. Could you give me a hint?
Here is the online material that the prof uses: http://www.ics.uci.edu/~goodrich/teach/cs161/notes/

vzn

10:33 PM

ok so what school are you going to? hint: take any other linear time algorithm, try to understand/ explain why it is linear time. then do the same for this one.

evinda

@vzn Guess :p
We have the function DFS(node x)
and then we call it recursively in the for-loop: for each (v in Adj(x)){ ... }

How can we find the time complexity?

vzn

what school? can you answer?

you seem to get overwhelmed by more than 2 sentences at a time :(

Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes. == Properties == The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time...

huh look at that, 4th sentence:

> The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time Θ(|V| + |E|),[4] linear in the size of the graph.

Thomas Klimpel

10:49 PM

@vzn I really admire your depth of knowledge in CS, the vast amount of fundamental knowledge and historic background, but also all the recent and relevant results and breakthroughs that you know about. But with respect to Anderson, I'm unsure what makes you admire his non-revolutionary results, or his heretic writings.

evinda

@vzn Why are you so curious? :p I agree that DFS requires linear time, but we call it in the for loop.. So isn't the time quadratic?

vzn

@evinda why are you so evasive? :p personal details/ rapport is my small distraction from tedious math/ tutoring

how is your algorithm for the tree vertex cover different than DFS?

@ThomasKlimpel wow, thats probably the most complimentary thing anyone has said to me in 3+ yrs on this site & maybe in decades of cyberspace o_O =D ... was actually thinking of/ alluding to Bush. (but with anderson close 2nd...) which btw iirc dont think you reacted to yet. have you seen it (Bush latest)?

evinda

@vzn At the DFS algorithm we call an other function (DFS-VISIT) and not the fuction itself recursively.

vzn

@evinda sigh, reading your own pseudocode. there is no such ref to any other function DFS-VISIT is there?

do you know any programming languages?

have you done any programming assignments? maybe you have one of those @#%& "teachers" that "teaches" or thinks they can "teach" CS without having students ever code/ test/ run stuff?

saw a quote like that by somebody-or-other, some supposed "authority"... should have saved it...

youre aiming to be an applied mathematician right?

so why wont you tell me your school?

teaching coding without ever code/ test/ running it is like... uh... (the mind reels...) "teaching" physical fitness in a classroom....

← (ages ago, in galaxy far away, once took a linear eqns course in math with coding & the teacher admitted he passed students with wrong code, because otherwise too many would flunk! wow!)

lol! aha!

17

Q: How can I teach computer science without using computers?

In some places in the world, people don't usually have access to (and hence little knowledge of) computers, and even if they have, hard- and software are outdated and usage plagued by power outages and such. Access to (good) books also tends to be lacking. How can I teach computer science under s...

education

Thomas Klimpel

11:19 PM

@vzn I hadn't seen it (Bush latest). I have taken a short look now. It reads much better than Anderson, so my guess would be that it is a good paper. I guess you won't find exaggerated claims of a big breakthrough in this paper, and also no allusions that physics books will have to be rewritten.

vzn

@ThomasKlimpel lol ofc, hes a phd who has to get grants, what do you expect... phds are not really interested in rewriting books, only writing them :p ... (& are conditioned to fear/ suppress revolutions just as much as "govt-owned" citizens...)

so you are in a feisty mood today lol... maybe some spicy guacamole for lunch? :p

Thomas Klimpel

@vzn But for people from Europe, it's unclear which govt is the owner.

vzn

lol yeah it gets complicated (& hard to keep track). germany owns greece right now. & cyprus went bankrupt & the govt confiscated savings. etc

a "revolutionary" (spking of that) new concept in the history of finance (aka dismal science), so called "bail in"

user159870

Hello everyone!

I hope someone of you can help me at my question:

0

Q: The output of Kruskal's algorithm is a spanning tree

I want to show that the output of Kruskal's algorithm is a spanning tree. Let $G$ be a connected, weighted graph and let $S$ be the subgraph of $G$ which is the output of the algorithm. $S$ cannot form a cycle and $S$ must be connected, since the first edge that unite two components of $S$ woul...

graph-theory algorithms computer-science

vzn

11:35 PM

Kruskal's algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm where the algorithm finds an edge of the least possible weight that connects any two trees in the forest.It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). This algorithm first appeared in...

Transcript for