# All Questions

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 ...
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 ...
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 ...
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.
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
27 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
31 views

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} = ... 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 ... 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 ... 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 ... 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 ... 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, ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ??? 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 ... 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 ... 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" ... 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? 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 ... 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 ... 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 ... 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 ... 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 ... 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. 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 ... 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