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 ...
0
votes
0answers
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)...
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, ...
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 ...
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.
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.
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
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 ...
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 ...
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 ...
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$
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
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 ...
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 ...
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
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
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?
-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 ...
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 ...
1
vote
2answers
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 ...
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 ...
0
votes
2answers
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 ...
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, ...
0
votes
0answers
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 ...
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 ...
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
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
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 ...
0
votes
2answers
37 views

Questions about Turing Machine

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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
4
votes
1answer
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 ...
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
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 ...
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
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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?
1
vote
1answer
23 views

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$?
0
votes
0answers
21 views

Efficient algorithm to prune a graph [on hold]

I'm faced to a problem I don't know the name, and for which I'm searching an efficient algorithm. From two list of nodes (without shared elements), the aim is to remove edges between element of the ...

15 30 50 per page