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 ...
12 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)...
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, ...
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 ...
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.
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.
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 ...
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 ...
11 views

Logical characterization of $NC^1$

Morioka in his 2005 dissertation  referenced "On Uniformity within $NC^1$" by Barrington, Immerman, and Straubing. Using the following statement: Every $\mathbf{NC^1}$-predicate is computed by ...
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 ...
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$
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-...
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 ...
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 ...
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?...
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 ...
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?
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 ...
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?
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 ...
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 ...
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 ...
16 views

Why do we use worse-case when categorising problems?

Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis. Why don't we use the average case? I imagine we could have a problem ...
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 ...
29 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 ...
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, ...
13 views

Number of steps - Count Change Procedure

I don't know if this is dupp question, i've already seen some explanations on why the procedure below is equal to $\theta(n^d)$ in terms of time complexity, being $d$ the number of coins. My question ...
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 ...
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 ...
41 views

Maximum weighted matching for directed (non-bipartite) graphs

This post concerns mainly non-bipartite graphs. Edmonds (1961) have proposed the Blossom algorithm to solve the maximum matching problem for undirected graphs. The best implementation of it is due ...
34 views

How do I prove no algorithm exists for a given problem? [duplicate]

Is there a general framework for showing that a problem has no algorithm? For example, to show that two problems are equally as hard to each other, we use reduction. One example of where this was ...
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?
19 views

Linear programing, objective function. variable depending on the sign of another variable

I have the variable Si. How to express a variable Di in LP that satisfies: Di=100*Si if Si>=0 ...
37 views

Below I will list a concrete example and the confusion it causes. Let's first say we have a decision problem, which is: "Is X <= 400?" We define the alphabet as the set of natural numbers. The ...
23 views

Is Halting problem only applicable to infinite languages

Is the halting problem, only applicable for infinite languages? I assume that if the language is finite, then we can search over all words?
13 views

How does the Random Forest classification function

I was going the through Random forest classification trying to understand it and I stumbled on two equation and I was wondering if anyone knows their name. what are the names of the theorms or ...
7 views

Obtaining the dual variables of an optimisation problem with second order cone constraints solved using Gurobi

I'm solving an optimisation problem with linear and second order cone constraints, in other words the problem is convex and should have dual variables. I'm using Julia with JuMP to formulate the ...
28 views

Partitioning a set so both parts have sum at least $c$ times the total sum

Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$? If $c=1/2$, this is the famous ...
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)$...
5 views

What's real world binary CSPs problem can be solved with AIMA JAVA CSP framework?

I am testing AIMA CSP framwork and I want to implement real world CSP problems.I know that AIMA CSP framework with java can only solve binary CSP problems and most real world CSPs problems are not ...
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/...
20 views

A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
21 views

Multiway Cut question

I am trying to understand Multiway Cut, and basically how the Multiway Cut works. I am searching google many hours to find a good example to understand. A good example that I am trying to understand ...
19 views

are all problems solvable given infinite time?

Given a turing machine which has unlimited memory and time, can it solve all problems or are there a class of problems that cannot be solved even with unbounded power. Is there a way to prove this?
Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?
Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?