All Questions

0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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.
1
vote
1answer
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, ...
0
votes
0answers
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)...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
0answers
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[1] In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is ...
0
votes
0answers
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 ...
0
votes
0answers
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.
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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)$...
0
votes
0answers
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 ...
0
votes
2answers
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 \}$$
1
vote
1answer
36 views

Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

I was trying to solve the following question while reviewing master theorem. Which of the following asymptotically grows faster. (a) $ T(n) = 4T(n/2) + 10n $ (b) $ T(n) = 8T(n/3) + 24n^2 $ (c) $ T(...
1
vote
1answer
21 views

Reducing 3 SAT to 3 SET PACKING

I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise ...
1
vote
1answer
11 views

Logical characterization of $NC^1$

Morioka in his 2005 dissertation [1] referenced "On Uniformity within $NC^1$" by Barrington, Immerman, and Straubing. Using the following statement: Every $\mathbf{NC^1}$-predicate is computed by ...
1
vote
1answer
15 views

$NL^2 = NDSPACE(\log^2n)$ is closed under complement

From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement. From Immerman–Szelepcsényi theorem we have $NL = coNL$. Why then $NL^2 = coNL^2$
1
vote
2answers
47 views

Prove that this language is NP-Hard

Given $$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$ prove that $\mathrm{\#3SAT}$ is NP-Hard. I am currently stuck with ...
2
votes
1answer
26 views

Does a Non-Deterministic Turing Machine solve all problems in P in constant time?

If a non-deterministic Turing machine can just "guess" the correct answer to a problem, does it do this in constant time/immediately? Also, does this also apply to problems in NP too?
1
vote
3answers
54 views

Context free grammar for language with even number of $0$'s and $1$'s

I want to create a Context-Free grammar that generates the language $$ L = \{ w \in \{0, 1\}^* |\ \text{number of $0$'s is even, and number of $1$'s is also even} \}. $$ I came up with $$ S \...
1
vote
1answer
14 views

How to calculate point in 3D space from multiple perspective

I have multiple camera in different points. I have their position and rotation as $(x,y,z)$ , $(\alpha,\beta,\gamma)$ or $( roll, pitch, yaw)$ . And I have output like this : Feed from camera-1, I ...
0
votes
1answer
27 views

Compiler - Why is the grammar not suitable for shift-reduce

Consider this example: stmt => if (expr) stmt | if (expr) stmt else stmt | other Why can't we use shift-reduce on this? This is a compiler homework and I ...
0
votes
2answers
23 views

Are Linear Bounded Automatons Turing Complete?

Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape. But this causes them to not be Turing Complete? Why?
0
votes
1answer
16 views

What is a good example of a textbook on programming, using Python?

I am looking for a textbook (for a course I am about to teach) that introduces programming generally - with Python as the example language. That is, I am not looking for the many many books on "how to ...
8
votes
2answers
2k views

Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
0
votes
0answers
16 views

Categorising problems into complexity classes

Am I correct in saying that there are two ways to categorise a problem in complexity theory: Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-...
-1
votes
0answers
6 views

Complete AES code?bin C#? [on hold]

I have designed a new encryption routine and am learning to code to write it. If I was able to examine how AES is quite literally written in C# I could probably reduce a month of studying followed by ...
0
votes
1answer
13 views

Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language

Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular?...
0
votes
0answers
6 views

If NP was closed under complement, then what would be the consequences for error in terms of randomization algorithms?

My thinking was that maybe we could run a randomised algorithm on the problem A, then run a different randomised algorithm on the complement A'. Would this reduce the error term in anyway depending ...
1
vote
2answers
19 views

Set of steps that cannot be implemented on a Turing machine

Is there an example of a "set of steps" that we thought was an algorithm, but later was shown not to be an algorithm because it could not be implemented on a Turing machine?
1
vote
1answer
292 views

4-partition elements summation NP completeness

How can we prove that the following problem $A$ is NP complete? Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \...
1
vote
1answer
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-...
2
votes
1answer
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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/...
1
vote
1answer
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 ...
55
votes
12answers
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)....
0
votes
2answers
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 ...
0
votes
1answer
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 ...
3
votes
2answers
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, ...
4
votes
1answer
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
8 views

For a randomise Turing machine, why do we flip a coin? [duplicate]

What effect would it have if we said, we decided that our randomisation would come from rolling a fair dice? Is it possible for the coin flip to simulate a more complex situation like a fair dice ...

15 30 50 per page