# All Questions

4 views

### Tensorflow understanding tf.train.shuffle_batch [migrated]

I have a single file of training data, about 100K rows, and I'm running a straightforward tf.train.GradientDescentOptimizer on each training step. The setup is ...
27 views

### What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
9 views

### Is the language $L=\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR($k$)?

I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar:  S \...
15 views

21 views

### System f-sub, how to do type checking?

I was reading that system f-sub (polymorphic lambda calculus with sub-typing) and I was quite confused with its one checking rule called "T-TAPP". This rule as following (ctx denotes the typing ...
30 views

### Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ...
15 views

### Online sorting without modifications

There is an array with $n$ places. There is a stream of $n$ numbers that arrive at a random order. Whenever a number arrives, we must put it somewhere in the array, and we are not allowed to move it ...
35 views

### L ={a^n.b^n | n>=0} , what is difference between L^2 and L.L?

which option is correct? please explain why other are wrong if any one is correct
20 views

### Find orientation graph of undirected graph that mimimizes absolute difference of in-degree and out degree

Here's a question from our uni's ICPC programming competition selections. I'm stating it in simpler terms here. Given an undirected graph, orient the edges of the graph in such a manner that the ...
21 views

### Generation of chords through a computer program [on hold]

This question is about generating chords through a computer program. Let us say we have generated C, E and G notes using a program. Now if we generate a new note by simply adding these 3 notes the ...
27 views

### Give a regular expression for L = {set of all strings in which number of a's are multiples of 3} ∑={a,b,c} [duplicate]

Give a regular expression for L = {set of all strings in which number of a's are multiples of 3} ∑={a,b,c}
59 views

### How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
28 views

### What problem to give to check a person's problem-solving capability? [on hold]

Suppose, you are a lead of a team who solves problems through the use of different problem-solving techniques and algorithms. You were tasked to pick a new member for your team from a pool of junior ...
20 views

### Converting pseudo code to a recurrence relation equation? [duplicate]

The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series. Pseudo code is below. I have so far T(...
23 views

### Grammar for concrete syntax [on hold]

It is given concrete syntax: data Stmt = SExp Exp | String := Exp | SBlock [Stmt] ...
13 views

### Trouble extracting only related text from the pdf file? [on hold]

The use of Beautiful Soup is not needed here. I have created pdf file and now trying to use pdfminer to extract only text. The problem is how to remove additional text which is the part of ...
9 views

### Trouble proving Big Theta Statement [duplicate]

I am browsing through MIT CS exams. For the task State whether each of the following claims is True or False and prove your answer. I found the following statement: n! is Θ (n^n) Seems easy to me ...
20 views

### Bootcamp or self-teach? [on hold]

Who out there is experienced a little bit with both and might be able to provide an answer here? I'm finding it very difficult to self-motivate at home, push through the walls, and even though it's a ...
89 views

### Why doesn't subset sum solution violate Exponential Time Hypothesis?

The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can ...
38 views

### Is it okay to select the best performers of test cases for scientific publication in neural network machine learning

If I split my data properly into 75% train, 15% test, and 15% validation, and there are over 100,000 samples, is it appropriate for me to train 100s of neural networks then select only a couple based ...
24 views

### Knuth Yao DP Speedup - Cutting Sticks

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost. ...
25 views

### Project to nearest point in convex polytope

Is there a reasonably efficient algorithm for the following task? Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$ Find: a point $y \in \mathcal{C}$ that is ...
34 views

### Shorten Length Reduction

I've stumbled upon this Question: We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $n\in N$ s.t for every $w\in A$, s.t ...
101 views

### What is the compleixty of this algorithm?

The algorithm is as follows: a = rand % a random number between 0 and 1 b = a while b == a b = rand end Here rand is a ...
17 views

### which of the folowing statements is correct about the C program given below? [on hold]

include int main() { int x=10; int y=100%90; for(i=1;i<=10;i++); if(x!=y); printf("x=%d y=%d\n",x,y); return (0); } A.the printf function is called 10 times. B.the program will produce ...
12 views

### Complex Network Betweenness Centrality algorithm [on hold]

I am writing a function in VB.net to calculate the betweenness centrality given in this paper Betweenness Centrality in a directed network. I have written the following code to do so. Please aware ...
14 views

### Which combination of the following features will suffice to characterize an OS as a multi-programmed OS

Which combination of the following features will suffice to characterize an OS as a multi-programmed OS? More than one program may be loaded into main memory at the same time for execution. If a ...
9 views

### Difference between the definitions regarding distribution of prime numbers [migrated]

Following are the two theorems that Hardy and Wright state in their book Theorem A: The number of primes not exceeding $x$ is given by $\pi(x) \sim \frac{x}{\log{x}}$. Theorem B: The order ...
25 views

### Number of ways to join n distinct trees

I have been trying to solve a problem in which i need to join N distinct trees with disjoint set of nodes. After searching a lot I came across this formula but i am not able to understand it. Please ...
41 views

### What is an example for a decidable language not in P?

I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?...
25 views

### calculate minimum wrapping surface area required for packing boxes

I can't get this question out of mind and can't come up with a algorithm to solve this Problem Given a set of N boxes, all of which have identical w x l x h dimensions, print the minimum ...
41 views

### Problems that are hard in the best case?

Are there any problems that are hard in the best case? In particular, I was wondering if there are problems that are NP-hard or #P-hard in the best case.
43 views

### Efficient algorithms for checking non-emptiness of the language of a Turing machine

I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?
This is really puzzling me! A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$. A ...