# All Questions

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 ...
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 => ...
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: ...
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 ...
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 ...
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 ...
19 views

### max flow algorithm

You are given a flow network G = (V, E) with integer capacities and a maximum
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 ...
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. ...
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 ...
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 ...
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?
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 ...
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, ...
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( ...
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 ...
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 !!
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. ...
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 ...
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 ...
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 ...
24 views

### Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?

Let f and g be two functions with integer range 0..m-1. They may keep state and interact ...
31 views

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 ...
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 ...
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 ...
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. ...
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!
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 ...
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 ...
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 ...
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 ...
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 ...