All Questions

31,082 questions
3 views

Forcing an edge to be in S-T min-cut

Given a Flow-Network N=(G,c,s,t) and an edge e=(u,v), i am trying to build an algorithm that finds a minimum (S,T) cut in the given network, that includes e. So, I tried couple of steps, first, I ...
3 views

Mistake in a proof of termination phase of Simplex algorithm in CLRS?

There is a pseudo-code for Simplex algorithm in CLRS: The proof consists from three-part loop invariant: Proof We use the following three-part loop invariant: At the start of each iteration ...
6 views

Where does fact constellation schema differ from star and snowflake schema?

In the 3 main (for my level) schemas for data warehouse modelling are the star, snowflake and the fact constellation schemas. I understand that the star schema is a purely denormalized schema as the ...
27 views

How to give a context-sensitive grammar for words like $a^nba^nba^nb$?

i am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$ i have to give for this language a context-sensitive grammar.
21 views

Assigning $m$ balls to $n$ buckets - recursive algorithm

I came across the following problem and the answer to that problem: Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, ...
13 views

counting the integer solutions to 1000a + 100b + 10c + d where 0 < x,y < 20 [on hold]

I am trying to figure out the integer solutions to 1000a + 100b + 10c + d where 0 < x,y < 20. I can print out the solutions by replacing n = n + 1 with 'print(a,b,c,d)' and removing the 'print(n)...
28 views

Given price and number of pages of each book, What is the maximum number of pages you can buy?

You are in a book shop which sells n different books. You know the price and number of pages of each book. You have decided that the total price of your purchases will be at most x. What is the ...
20 views

Algorithm for deducing values

I have a group of logical conditions and need to deduce values that would NOT satisfy them. For example: City != New York && Location = Museum ...
11 views

Are the languages recognized by one-counter machines equivalent to deterministic context free language?

When learning automata theory, I notice that John Hopcroft mentioned In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is ...
9 views

Overlay two Voronoi Diagrams and calculate membership and areas of intersecting polygons

I would like to generate a composite diagram of two Voronoi diagrams. I'm currently researching the cgal library for options, but I'm not sure if my precise application is covered. Basically, I have ...
20 views

How to prove that extended euclidean algorithm has time complexity log(max(m,n)) ?'

I tried to search on internet and also thought by myself but was unsuccessful. Intuitively i think it should be O(max(m,n)). can someone give easy explanation since i am beginner in algorithms.
40 views

Is there any relationship between time complexity and space complexity of an algorithm?

For example: If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1) Is there a way to increase the space complexity to something like O(n^2) that ...
26 views

Acceptance problem for CFGs is not regular

Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars. It ...
36 views

Intersection of two deterministic parity automata

Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
17 views

I need advices and guidance! [on hold]

I have a lot of questions and a lot of doubts of what should i do with my life. The thing is, i finished IT college in Bosnia and Herzegovina ( 3 year bachelors degree). I didn’t master any IT skills ...
49 views

DSPACE(f(n)) closed under complement

I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$...
25 views

Longest simple circuit and P=NP relation

Given the following function: $$\:f\left(G,v\right)\:=\:size\:of\:the\:longest\:simple\:circuit\:in\:a\:directed\:graph\:G\:that\:contains\:v$$ Output: Function returns a natural number or 0, which ...
35 views

Help: Context Free Grammar [on hold]

Construct the CFG given the following language: $$\{a^i \; b^j \; c^k \;|\; i = j \; or \; j = k \}$$
36 views

511 views

Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARD

I'm studying some of computation theory and i encounter a big question mark. I have an optimization problem and i have to proof that is NP-HARD. I know that my problem can be reduced to another np-...
175 views

Proving there is no polynomial algorithm for independent set

I need some guidance in an assignment I'm doing. I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
98 views

Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?

I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite ...
38 views

Dealing with test condition '=' for a while loop when determining a bound function/loop variant

The following is the definition of what a bound function for a while loop must satisfy: The bound function is an integer-valued, total function of some of the inputs, variables and global data that ...
38 views

Binary search uneven split number of queries?

For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/...
26 views

Given a randomised algorithm for a problem, is there a corresponding deterministic algorithm?

Does every randomised algorithm have a corresponding deterministic algorithm solving the same problem? I'm going to guess that the deterministic algorithm will take more time, while the randomised ...
23k views

Does a byte contain 8 bits, or 9?

I read in this assembly programming tutorial that 8 bits are used for data while 1 bit is for parity, which is then used for detecting parity error (caused by hardware fault or electrical disturbance)....
30 views

Why do P-class problems not require a witness like NP?

If I am given a problem in P, to claim that I have solved it, I would need to give proof, right? For example, to show a number is not prime, if I use some deterministic algorithm, I can return the ...
21 views

Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time

So, if I were using a black-box decision algorithm, PATH in which I could say, "does a path of weight k exist in this graph from ...
59 views

How much can we trust mathematical software when working with large numbers, and how much memory it needs to work with these numbers?

For example, I want to evaluate the expression: $3^{3^{{3}^{3}}}$ so I used wolframalpha.com (it's free, and I don't own any software), which returned the scientific notation of the number above, ...
51 views

Heuristics vs meta-heuristics vs hyper-heuristics?

The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic". The wikipedia page on hyper-heuristics states that they are "heuristic ...
25 views

How do i make a percentage based loot system C# [on hold]

so i have been trying to figure this one out on my own for a little while now for my game i am creating, but i am not able to get my head around it. I basically would like too know how to create a ...