0
votes
0answers
7 views

Path optimization in a DAG: maximizing number of least cost links

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
-2
votes
0answers
8 views

Too few arguments in function, need help with program in C [migrated]

So I made a Celsius and Fahrenheit Converter in C but I have come across an error in my program. My functions seem to be not working when trying to output the conversion of the temperatures. Could ...
3
votes
1answer
67 views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
-1
votes
0answers
11 views

Lagrange's interpolation [on hold]

I have to make Lagrange's interpolation algorithm. Additionally, I have to know coefficients, and moreover I can get also derivatives on input. Please refer me how to do it.
0
votes
0answers
20 views

A question about algorithm and code [on hold]

I am a very new user and I would like to know how to calculate the following operations in Mathematica. Honestly this is not a homework. I am an french architect and I would like to be back in Math ...
0
votes
0answers
20 views

Is it even theoretically possible to invent coumputers that are more intelligent than humans? [on hold]

I've read an article recently where Stephen Hawking claims that in hundred years there will be computers, which are more intelligent than humans. Link: ...
-1
votes
0answers
21 views

How quickly can we generate a random integer (asymptotically)?

I'm looking for a RNG that either generates a random integer (from $-n$ to $n$) or generates $m$ random integers in this range. I'm mainly concerned with the speed of the RNG, although an even ...
-2
votes
0answers
23 views

Planning to study comp sci at undergraduate level [on hold]

I am planning to study comp sci as a undergraduate I wish to get some directions as what extracurricular activities I could do over the next two years. Further more I am unsure of what I should ...
0
votes
0answers
20 views

Design an algorithm to calculate the maximum amount of pairs $2a_i \le a_j$ that can be removed from a non decreasing sequence of n numbers

I am trying to solve the following problem: You are given a non decreasing sequence of $n$ unsigned integers $a_1 \le a_2 \le \ldots \le a_n$. You can modify this sequence using the following ...
0
votes
0answers
16 views

Proving that pairs of words in resp. not in a TMs language are neither semi- nor co-semi-decidable [on hold]

I have a homework assignment in which I am required to determine if $$L = \{ \langle M,x,y \rangle : x\in L(M),y\notin L(M) \}$$ is in $$R,RE-R,coRE-R \text{ or } \overline{RE \cup coRE}$$ Now, my ...
0
votes
0answers
13 views

How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in a undirected graph?

How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in an undirected graph ? I've seen it stated that one can apply a maximum flow ...
2
votes
0answers
27 views

How to use homomorphisms to prove irregularity [duplicate]

I'm a bit confused on how to use homomorphims to prove irregularity or to prove that a language is not context free. This is what I'm currently thinking: For example, lets look at: $L = \{ ...
-1
votes
0answers
19 views

How to transfer tsp to factorization?

So we know that travelling salesman problem is NP-Complete, that means if we solve it, we can solve factorization problem in the same amount of time. How do we do it though?
0
votes
0answers
8 views

Could not initialize Applet Error [on hold]

I have installed java version 1.7 on my ubuntu pc . I have latest iced tea web plugin installed on my firefox . I have installed java3d 1.5.2 api . I have set paths for both java and java-3d . Still ...
2
votes
1answer
30 views

Efficiently enumerating all paths from i to j of given length in a graph

I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) ...
0
votes
0answers
10 views

question about reference in Java [migrated]

When we insert a node to the head of a linked list, we can use the following code: ...
-4
votes
0answers
10 views

suffix automation for finding LCS [on hold]

Can any one please explain about the construction of Suffix automation with an example.Its getting very hard for me to understand
3
votes
1answer
55 views

Intuition for PH notation in Arora-Barak's Computational Complexity

For the definition of polynomial hierarchy: $x \in L \Leftrightarrow \exists u_1 \in \{0, 1\}^{q(|x|)}\forall u_2 \in \{0, 1\}^{q(|x|)} \cdots Q_i u_i \in \{0, 1\}^{q(|x|)} M(x, u_1, \ldots, u_i) = ...
-2
votes
1answer
38 views

Is the language given by this CFG regular? [duplicate]

S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc How can I prove that this language is regular or not? I need your help. It also has two ...
0
votes
1answer
19 views

How does augmenting linear bounded automata tape alphabets increase memory?

A linear bounded automaton is a Turing machine that is restricted by memory. How would augmenting the tape alphabet of a linear bounded automaton increase its memory? While the memory that the ...
3
votes
2answers
69 views

Undecidable problems limit physical theories

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...
0
votes
1answer
19 views

Hamming Distance, Bit message [on hold]

My professor told us to try and remember the equation used for an upcoming exam, however I'm struggling to fit the equation into the question: http://i.stack.imgur.com/RoPYG.png (need a high ...
0
votes
0answers
37 views

Variable argument placement in methods

Imagine that we have a base class number that has implemented a integer and floats, but not complex numbers and that we would like to extend it to also support ...
2
votes
1answer
27 views

What is the difference between “strict schedule” and “cascadeless schedule”?

In database transactions theory, what is the difference between a strict schedule and a schedule that is merely secured against cascade aborts? Could you give an example of a schedule that is ...
3
votes
1answer
25 views

Red-black tree. Adding a red child to a red node with a black sibling

According to my lecture notes, adding a red child to a red node with a black sibling in a red-black tree, is equivalent to changing a 3-node into a 4-node in a 2-3-4 tree. I've built several red-black ...
2
votes
0answers
33 views

What is a “trap” in the context of system virtualization?

My professor's notes on system virtualization refer a lot to the term "trap", but don't seem to explicitly define it. I can't seem to find any definition on Google either, other than a small article ...
4
votes
1answer
31 views

Average vs Worst-Case Hitting Time

Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can $$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to $$ H_{\rm ave} = ...
2
votes
1answer
16 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of ...
0
votes
0answers
35 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [on hold]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
1
vote
0answers
25 views

How much calculus do you actually use (not counting use of a graphing calculator)? [on hold]

I'm wondering if it's worth it to pursue some deep study into calculus. Already, I have some familiarity with derivatives, limits, and integrals. Though, I also have a graphing calculator that's ...
1
vote
1answer
71 views

Intuition behind F-algebra

I looked at here for getting an intuition about F-algebra, but I am still left with some questions. Suppose I have a group signature as $\Sigma= (* : X \times X \rightarrow X, \thicksim: X ...
1
vote
1answer
18 views

Unambiguous but nondeterministic context-free language?

Whenever deterministic context-free languages are discussed, the webpage/textbook would always give a side note saying that although deterministic context-free languages are never ambiguous, ...
1
vote
1answer
72 views

Can Circuit Value Problem or HORN-SAT be reduced to PATH problem?

PATH = {(X,R,S,T) | exists an x in S that is admissible} Where R is a relation of X x X x X, S is a unary relation of X and T is a unary relation of X aswell. An x element of X is admissible if it is ...
1
vote
1answer
24 views

Local Cache miss using MESI Coherence Protocol

My notes on MESI state that there are a few courses of action when we experience a local cache miss on read, depending on the global state of the data (whether other copies already exist, and the ...
3
votes
0answers
21 views

What happens when the words transfered on the bus are smaller than its width?

So what happens if we're transfering lots of 8 bit words in a 32 bit bus? Does each bus cycle only transfers 8 bit at the time, wasting the other 24 lines of the bus? Or does it transfer 4 words in ...
1
vote
0answers
16 views

Soft real time operating system

i know the basic idea and difference between hard and soft rtos. i wanted to know large scale and specific example of soft rtos. and i read in this site that even LINUX is a soft rtos. is the ...
1
vote
1answer
43 views

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$ My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such ...
1
vote
0answers
14 views

what is correct maximum number of subnetworks? [on hold]

ip: 10.5.2.1 subnetmask: 255.255.255.240 {10.5.2.1/28} what is correct maximum subnetworks ???? what is different between classful subnet and CIDR subnet ???
1
vote
1answer
38 views

Dijkstra function for navigation for disadvantaged

Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be ...
1
vote
0answers
12 views

Find maximum scoring characters with non overlapping occurrences from a string

I have a problem related to Episode Mining in which I need to find the maximal utility of a episode given its occurrences in an event sequence.But I am presenting the question in a different form so ...
1
vote
1answer
61 views

How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? [on hold]

As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable? This is not a "technical" ...
-1
votes
1answer
34 views

Use the pumping lemma to show that the language is not regular [on hold]

I am working on this problem : Use the pumping lemma to show that the language $\{0^n 1^{n} \mid n ≥ 1\}$ is not regular. May someone give me some suggestion about how to solve this problem?
0
votes
2answers
59 views

Draw a DFA that accepts ((aa*)*b)*

A homework question asks me to a draw a DFA for the regular expression $((aa^*)^*b)^*$ I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s ...
-2
votes
0answers
19 views

User input is entered vertically and not horizontally in C++ Need help [on hold]

So recently I've been practicing C++ and I've noticed that when I do a printf and scanf in C, then the user input is entered horizontally. But as soon as I do that in C++ (cout and cin) then it's ...
1
vote
1answer
46 views

Better algorithm for determining if a vertex is on any cycle in a graph

The problem I'm facing is the following: Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$. The algorithm I can think of is to remove an ...
2
votes
0answers
23 views

When there's no memory, should malloc or read/write fail?

To my surprise, I recently found out that Windows would fail a large memory allocation even if little of said memory is to actually be used, e.g. even if you don't want the swap, you better not ...
4
votes
1answer
39 views

What usage is the delta defined in the polynomial hierarchy?

At the Wikipedia page, the polynomial hierarchy also defines the following: $\Delta_0^\text{P} = P$, $\Delta_i^\text{P} = \text{P}^{\Sigma_{i-1}^\text{P}}$ However, the only usage of this anywhere ...
-2
votes
1answer
47 views

Dijsktra's algorithm example [on hold]

In the following example, how does Dijkstra's algorithm find the shortest path? I think we'll get abedz, while the shortest should be acedz.
1
vote
1answer
33 views

Converting reality to Petri net

I'm autistic and I think a bit differently. I have superior memory and visual thinking, but I have a problem with converting real thing to abstract. I'd like to model reality processes with Petri ...
8
votes
2answers
164 views

Regularity of unary languages with word lengths the sum of two resp. three squares

I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$ ...

15 30 50 per page