0
votes
0answers
3 views

Is Not-STCON is NL-Complete?

$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$ $Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$ I've tried the following proof: Let $S\in NL$, and ...
0
votes
0answers
9 views

Complexity class for loop with two inner loops

I have an algorithm like the following for(int k) { statement1; for(int j) { statement2; } for(int m) { statement3; } } j => ...
0
votes
0answers
9 views

Branch and Bound - Transform a into b

I'm trying to design an algorithm which will accept two natural numbers: a and b. Its purpose is to get b from a by making the following operations: *3 and /2. For example, if a = 10 and b = 7, then: ...
1
vote
0answers
13 views

$\{\langle D,R\rangle \ | \ \text{D is a DFA, R is a regular expression and L(D) = L(R)} \}\in\mathcal{R}$

Prove/Disprove: $L= \{\langle D,R\rangle \ | \ \text{D is a DFA, R is a regular expression and L(D) = L(R)} \}\in\mathcal{R}$. I managed to prove that $L$ is in $\mathcal{co-RE}$ but It seems hard ...
-1
votes
0answers
14 views

How find errors in the usage of brackets in the code

Problem Description Your friend is making a text editor for programmers. He is currently working on a feature that will find errors in the usage of different types of brackets. Code can contain any ...
1
vote
0answers
23 views

Common subset sum fast algorithm

Suppose of I two sets of $n$ integers bounded in $[-B,B]$. The integers are $$a_1,\dots,a_n$$ $$b_1,\dots,b_n$$ I want to find if there is a common subset $I\subseteq\{1,\dots,n\}$ such that ...
0
votes
0answers
19 views

max flow algorithm

You are given a flow network G = (V, E) with integer capacities and a maximum
1
vote
0answers
11 views

What is the difference between the research area of “ad hoc networks” and “device-to-device communication”?

I wonder what "device-to-device communication" (from a research perspective) covers what "ad hoc networks" don't. To the context of this question: I am reviewing papers which deal with ...
1
vote
0answers
13 views

How to make LALR(1) directly?

I studied LR(1) parsers and then LALR(1) and noticed that if we wanna construct LALR(1), We should FIRST construct the LR(1) parser and then by combining states we can go ahead for LALR(1) parser. ...
0
votes
0answers
19 views

bitvector supporting rank and select

I am trying to understand how to code Raman, Raman, and Rao, I have found a lot of explanations, but almost everything say the same thing, can someone guide in how can I can code the part of the ...
2
votes
1answer
20 views

Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?

I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum ...
6
votes
1answer
238 views

What is the difference between oblivious and non-oblivious merging, sorting etc

Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?
0
votes
0answers
13 views

Filter bubble algorithms for presenting related video lists

In a filter bubble, what are some of the techniques and best ways to determine the relationship between a video that is watched or liked, and the list of related videos to be presented to the browsing ...
1
vote
1answer
184 views

Number of possible programs in a language

Is the number of possible programs usually finite or infinite? I'm playing with the idea of generating all possible programs for a language - is that even a finite number or must we be more specific, ...
1
vote
0answers
38 views

is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance! Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( ...
-2
votes
0answers
13 views

How to install RevoScaleR package in R in ubuntu [on hold]

when i try to install that package using install.package("RevoScaleR") it showing an error message "package ‘RevoScaleR’ is not available (for R version 3.3.0)" but i tried with various versions of R ...
-2
votes
0answers
16 views

prove that if NP-Complete intersection Co-NP-Complete not empty then P=NP? [on hold]

prove that if NP-Complete intersection Co-NP-Complete not empty then P=NP ? can someone help me !!
0
votes
0answers
11 views

Flaw in linear programming solution for multi-commodity flow problem?

The multi-commodity flow problem problem statement - wiki According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ...
2
votes
1answer
51 views

Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
-2
votes
0answers
36 views

how this algorithm works [on hold]

I don't understand how this algorithm works... But seems amazing! It can compress itself from (2027 Byte to 214Byte!!) Download the compiled file here and test: http://www.filedropper.com/rancom ...
-3
votes
1answer
20 views

WHAT'S THE BEST SPECIALIZATION FIELD FOR MS IN COMPUTER SCIENCE? [on hold]

please any one can guide me that which specialization field should I choose for my MS in computer science program,I am living in pakistan...... I really need guidance for this issue as there are so ...
4
votes
1answer
24 views
1
vote
0answers
31 views

Decrease distance between max and min

Let $a:=(a_1,a_2,\ldots,a_n) \in \mathbb{Z}^n $ and $k \in \mathbb{N}^*$, with $$f: \begin{cases} \hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\ \hfill ...
0
votes
0answers
11 views

Is there a broader class of total functions than $PR$?

In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann ...
0
votes
1answer
12 views

Computing a subproduct tree

Consider the following description of a subproduct tree. We define a tree T for some points x[0] to x[n-1], and define m = log_2(n). Tree T is represented as a matrix where each row-column entry i, ...
6
votes
1answer
75 views

Is EXPTIME “solvable” or “checkable” in exponential time?

According to this video, EXP has problems that are exponentially difficult to check. But according to this video, EXP are problems that are exponentially difficult to solve. It would make sense to ...
2
votes
2answers
33 views

Check whether an undirected graph contains a simple cycle of length four using the “Squares” method

The following problem is exercise 4.3 of the book "Algorithms" by S. Dasgupta, C. Papadimitriou, and U. Vazirani. Squares. Design and analyze an algorithm that takes as input an undirected graph ...
0
votes
0answers
17 views

Demand Paging and File System Shared and Segregated Cache - Differences, Advantages?

This is from a computer science class, so I suppose it could be considered a computer science question... I have a final in a few days, and I'm preparing for it. We were given a review sheet, and one ...
1
vote
1answer
21 views

Maximum cost path in integer matrix

In preparation for my design and algorithms exam, I encountered the following problem. Given a $2 \times N$ integer matrix $(a[i][j] \in [-1000, 1000])$ and an unsigned integer $k$, find the ...
0
votes
0answers
21 views

Structural induction hypothesis on derivations

I am relatively new to the field of language semantics, however i am a bit confused about using operational semantics and structural induction on Derivations. If I have two languages $L1$ and $L2$ and ...
0
votes
0answers
4 views

Blocking in two phase commit protocol

Blocking is a disadvantage in 2 phase commit protocol. But I read a statement that "Blocking in a 2 phase commit protocol can't be completely eliminated EVEN when participants/COHORTs select a new ...
1
vote
1answer
11 views

Computing gaussian kernel for image blurring

When I compute a gaussian kernel for image blurring should I normalize the 1D vectors? Because when I apply the raw values sometimes the image gets lighter or darker. The function I'm using is $f(x) = ...
5
votes
2answers
58 views

Why is BNF considered an unsatisfactory technique for describing a language?

I was reading the paper Fundamental Concepts in Programming Languages by C. Strachey the other day, wherein I read something that was quite strange to me. Quoting directly (with the strange part ...
-1
votes
2answers
24 views

How to prove the following xor equation?

In a test paper, a question is given as : ...
-4
votes
0answers
16 views

Is a union of any TM language and the halting problem language decidable [duplicate]

I need to find if the following language is decidable (in $R$): $L=\{ \langle M \rangle \mid M \text{ is a TM}, L(M)\cup H_{TM}\in RE\}$ Where $H_{TM}$ is of the halting problem. My intuition is ...
-2
votes
1answer
24 views

All output functions of a truth table

http://www.cim.mcgill.ca/~langer/273/3-notes.pdf I can name one more: XNOR. But besides these, what other output functions are there?
3
votes
2answers
68 views

Number of winning combination in Nim

I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are ...
-1
votes
0answers
27 views

Edit option is gone after sometime for comments [on hold]

Under answer in stack exchange we can start adding comments. But that comment is editable for only for few minutes. After that it will be read only mode for even the owner of the comment. I have seen ...
0
votes
0answers
34 views

Classify the set of all TMs whose languages from the accepting problem

Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM} \leq_m L(M) \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in ...
3
votes
1answer
29 views

Hadamard gate on entangled qubit

TL;DR: If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why? I am trying to understand ...
-3
votes
0answers
25 views

Number of ways to construct a Regular graph

For a regular graph (each vertex has same degree k), a part of graph upto level l is given, how to compute the total number of ways in which the graph can be completed given that m edges and n ...
3
votes
0answers
11 views

Set of vertex-disjoint cycles maximizing different colored vertices

Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$. I am looking to find a set of vertex-disjoint cycles that: First maximizes the ...
-2
votes
1answer
18 views

How can time complexities be elements of others? [duplicate]

I have a problem that I solved, but I'm unsure if my answers are correct or not. I've never seen the implementation of time complexities as elements of others. ...
-1
votes
0answers
13 views

Tarjan's Bridge Finding Algorithm Psuedocode? [on hold]

I was looking for a verbose and well-constructed psuedocode for finding Bridges in an undirected Graph. If possible please share any psueodocode, thank you!
-2
votes
1answer
22 views

Complexity and number of bits of square root number

Let an integer a, and b is the number of bits a. 1) If I have a number ...
0
votes
1answer
43 views

AI : how can i study it by myself? [on hold]

Peace for All I'm interested in studying artificial intelligence, i bought a book "artificial intelligence Modern Approach " But I could not begin to delve into it for some reasons So I need your ...
1
vote
2answers
35 views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
3
votes
2answers
110 views

Searching the best trading route - algorithm

Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount a of good b for amount ...
3
votes
0answers
67 views
+100

How to compute the sum of this series involving golden ratio, efficiently?

Definitions Let $\tau$ be a function on natural numbers defined as $\tau(n)=\lceil n*\phi^2\rceil$ where $n$ is some natural number and $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. This series ...
0
votes
0answers
16 views

Complexity of choosing a suitable Boolean algebra domain for program analysis

Do you know the complexity class of the following problem? Input: A sequential non-deterministic program over integer variables, equipped with initial values of these variables. The exact ...

15 30 50 per page