# All Questions

42,330 questions
Filter by
Sorted by
Tagged with
4 views

### Certificate based definition of class NL

NL is defined using certificates as follows: A language $L$ is in $NL$ if there exists a deterministic turing machine $M$ (verifier) with an additional read-once input tape and a polynomial $p:N->N$...
16 views

### How to prove the correctness of the algorithm to find longest path from root to leaf in a binary tree?

I found an algorithm to find a longest path from the root to leaf using recursion, but I'm not sure how to prove it's correct? https://www.geeksforgeeks.org/print-the-longest-path-from-root-to-leaf-in-...
7 views

### Generality of a coin system in coin-change problem

For the coin-change problem, Is there a general property such that if a set of values satisfy then the greedy algorithm works for them? I went through this and this. I barely understood anything. I ...
10 views

### Explain it to me like I am 5 - Membership Problem

I would like you to explain what the membership problem in formal languages is about and what the difference is between the membership problem and the inclusion problem. Thank you :)
8 views

### Find a regular expression that satisfies na(w) mod 3 > nb(w) mod 3

w is a string over {a,b}. Find a regular expression that satisfies na(w) mod 3 > nb(w) mod 3. Note that ...
10 views

21 views

### CS student but don't know how to code projects, how do I learn this?

Really worrying situation. I do well with CS subjects but at the end of day it is all useless as I don't know how to code. How do I learn to code to make projects? I can make small programs easily. I ...
14 views

### Descriptive language to generate real code

This question may be silly but would still like to know a response. Is there some descriptive language through which one could define a functionality of a class or function and than generate working ...
18 views

### Fast calculations using fast-Fourier convolution

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$. We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
21 views

### Finding the number of ways to reach a particular position in a grid from a starting position (given some cells which are blocked)

I came across this question in a job interview and I couldn't solve it. In a n*m matrix some cells are blocked.The robot can only move in direction of (x-1,y+2) or <...
30 views

### Is language $a^mb^nc^n, m \not= n$ context free

I need to say Is language $a^mb^nc^n, m \not= n$ context free I managed to find a grammar for $L1 =$ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, ...
12 views

### Pre-computing min/max for interval queries?

I'm basically trying to figure out if the following problem has a common name and/or a standard solution in computer science. Let assume we're given $N$ two-dimensional tuples $(x_i, y_i)$. This data ...
11 views

### In Redox OS filesystem is in kernel or userspace?

In Redox OS filesystem is in kernel or userspace? I find in kernel initfs "initfs: - a readonly filesystem used for initializing the system" But not correctly understand, is it only forinit ...
9 views

### How to show etm is turing reduicble to halt_tm

I am new to the world of turing machine, decidability, In HALT_TM when the turing machine enters reject state does it produce any string or not?
22 views

### Dynamic programming to find number of ways to divide string into primes

I am studying for final algorithms exam and saw this question: Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers >= 2....
12 views

### Minimum General Routing Problem

I have been researching about general routing problems and came across a type TSP problem as: "Find a minimum cost cycle in a graph G = (V, E) which visits vertices in a required subset V′ ⊂V ...
12 views

### Simple Peer to Peer Computing coding challenge [closed]

I came across this p2p computing challenge and would like your insights on the best way to work it out. Thanks in advance! The Challenge: Atim is trying to add the first 100 Trillion counting numbers ...
26 views

### Write n in terms of multiplication of numbers from A=[1,...,n] such that the total cost of chosen number is maximum

We want to write n in terms of multiplication of numbers from A = [1,...,n] such that the total cost is maximum. The cost of choosing the ith number is cost[i]. ...
36 views

### Smallest 3-SAT problem that no one has been able to solve?

In number theory progress is sometimes guided by people stating a specific Diophantine equation that they don't know how to solve. Is there anything similar in the field of Boolean satisfiability? ...
13 views

### What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$

Given the following language:  L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{...
14 views

### calculate the VC-dimension [closed]

I'm new here in the forum. I started learning machine learning independently and I have a question. I have a question about VC-dimension. I have this claim and I need to find out what its VC-dimension ...
19 views

### How do I visualize my CNN Keras mode? [closed]

I have a Keras CNN model and am having trouble trying to visualize it. I am using Jupyter Notebook on Windows. Here is my model: ...
23 views

### reference that minimum makespan on identical machines is NP-hard?

I need to cite a reference that the minimum makespan problem on ($>2$) identical machines is NP-hard. I've seen Garey and Johnson cited as a reference, but it I'm not sure which of the problems is ...
16 views

### Check if the given satisfying assignment of CNF formula is lexicographically the first

If there is a CNF Boolean formula in $n$ variables then the potential satisfying assignments are the binary strings of length $n$. Given a CNF Boolean formula and a satisfying assignment how ...
22 views

40 views

### How does the Bitcoin Algorithm for Converting to Base 58 Work?

I've been trying to create a function in TypeScript for converting to and from base58. I'm pretty familiar with base conversion generally: divide a number by a target base, and take each remainder as ...