All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
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$...
0
votes
0answers
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-...
0
votes
0answers
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 ...
0
votes
0answers
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 :)
0
votes
1answer
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 ...
0
votes
1answer
10 views

Probability of certain symbols in a mapping of symbol and code word

Let's say you have this mapping of symbols and codewords: $$ \begin{array}{cc} \hline \text { Symbol } & \text { Codeword } \\ \hline \text { A } & 101 \\ \text { B } & 100 \\ \text { C } &...
0
votes
0answers
7 views

Linear deterministic algorithm for finding spanning tree T with minimal maximum edge

Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ). I need to find a ...
0
votes
0answers
5 views

Information contained or received

In my lecture, the lecturer introduced without much explanation that the following applies: Given a discrete random variable $X$ $N$ possible values: $x_{1}, x_{2}, \ldots, x_{N}$ Associated ...
0
votes
0answers
7 views

How to count number of parse trees for a specific grammar

The task: You are standing in front of a gigantic forest of syntax trees. One tree looks more fascinating than the other. In front of the forest is a sign: "Every tree in this forest arises from ...
0
votes
0answers
33 views

Write functions that run in O(1) time

This Question can be found in the book: ODS: An Introduction (Chapter 6) Suppose we are given a binary tree with pre-, post-, and in-order numbers assigned to the nodes. Show how these numbers can be ...
0
votes
0answers
11 views

Expected linear-time algorithm for finding MST with probability for sampling an edge other than 1/2

I'm trying to understand this algorithm : https://en.m.wikipedia.org/wiki/Expected_linear_time_MST_algorithm As described in the wiki article, it works in 5 steps to find the MSF for a graph $G = (V, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 <...
1
vote
1answer
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, ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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?
0
votes
0answers
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....
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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]. ...
1
vote
0answers
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? ...
0
votes
0answers
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{...
0
votes
0answers
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 ...
0
votes
0answers
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: ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
22 views

Computational Complexity of an 'equivalent' 3SAT instance problem

Given a random $3SAT$ instance $(S_0)$ with $C_0$ clauses, $I_0$ variables. Objective: For any given value $C_1$ ($C_1<C_0$), create an 'equivalent' $3SAT$ instance $(S_1)$ with $I_0$ variables, $...
0
votes
0answers
13 views

Data structure for incremental KNN (IKNN) search over high-dimensional vectors

I have a database $D$ of n-dimensional numerical vectors, and I want to do an incremental KNN (IKNN) search over the vectors in $D$. More precisely, given a query vector $v_q \in D$ I need to find $k$ ...
-2
votes
0answers
16 views

While reading algorithm I came across this teminology of giving subscript to some array what does that mean?

I am reading solution of a some problem came across a term B0[] B1[] algorithm doesn't specify what it means please explain is it general algorithm writing term?
0
votes
0answers
37 views

Alu architecture of a Hack Computer

I'm currently studying the ALU architecture (of a Hack computer) and how it works. As part of my assignments, I have been asked the following question: If we want the ALU to compute the function y-1, ...
0
votes
0answers
7 views

Is there an entropy evaluation method with an unified length?

For entropy, the most common one is Shannon entropy, however, it ignores time series of data. For instance, data 0x00001111 and 0x01010101 are given the same entropy. It is obvious that the second ...
0
votes
0answers
11 views
10
votes
1answer
1k views

Optimal stacking of bricks

I need an algorithm to optimally stack a set of bricks in a 2D plane so that the resulting wall is as vertically short as possible. Bricks are defined as a pair of integers $(x_1, x_2)$ corresponding ...
-1
votes
0answers
25 views

Asymptotic relation between $x^2\log x$ and $x\log(x^4)$

Let $f(x) = x^2\log x$ and $g(x) = x\log(x^4)$. Choose the correct statements: $f(x) = O(g(x))$ $g(x) = O(f(x))$ Both I know $g(x) = O(f(x))$, but I don't know whether statement 1 is true or false....
3
votes
1answer
29 views

Algorithm to find the shortest path and its length for moving between many geometries

I have a set of 2D geometric figures in Cartesian space, as shown in the image. Each geometric figure has a start point and an end point (among other characteristics). For closed geometries, such as a ...
0
votes
0answers
12 views

Inverse DCT using inverse DFT algorithm [closed]

Say I have an inverse DFT function ready for use. I am struggling to find online or mathematically deduce the additional steps needed to compute an inverse DCT4 by using said inverse DFT function. If ...
0
votes
0answers
35 views

master theorem `case 3` counter example? [duplicate]

as far as i understood from the proof of the master theory in the introduction to algorithms book while proofing the third case we assumed that $af(n/b) ≤ cf(n)$ ...
0
votes
0answers
40 views

Does allowing a mutable transition function in Turing machine make it more powerful?

as the title says does having a mutable transition function make the Turing machine more powerful by mutable I mean we have a set of transition functions that we can choose one of them arbitrary based ...
0
votes
0answers
44 views

Algorithm to seat people at tables given who they would like to sit next to

I'm trying to devise an algorithm to seat people at a table. The basic premise is as follows: Given a list of $n$ tables, each with a different number of seats (e.g. $2, 4, 4, 5$), and a dictionary of ...
1
vote
1answer
129 views

A computable language with a non-computable language that is prefix-free

We say that a language $L$ is prefix-free if for every word $s\in L$ there does not exist a nonempty string $w\in\Sigma^*$ such that $sw\in L$ (i.e. no word in the language is a prefix of some other ...
0
votes
1answer
13 views

Are AVL&RB Trees without additional storage for balance information in each node feasible?

One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information. But can't ...
0
votes
0answers
32 views

Algorithm for the Minimal Vertex Cover that is a Subgraph [closed]

Puzzle: There is an archipelago whose islands are connected by a series of bridges. You are an anarchist who wants to destroy all these bridges. In order to due so, you plan to start a fire at one end ...
0
votes
0answers
26 views

What is the height growth speed of an AVL tree? [closed]

If the AVL tree has no balance at all, the height growth is always 0. If the AVL tree has a perfect balance, the height growth is always 1. What exactly is the analytic height growth function ...
1
vote
1answer
22 views

Embedding from $L^\infty$ space to $L^2$ space

I have a set $X$ of $n$ points in a $poly(n)$-dimensional $L^\infty$ space. Does there exist a way to map the points into $poly(n)$-dimensional $L^2$ space so that the distances between points in $X$ ...
2
votes
0answers
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 ...
-1
votes
0answers
41 views

AVL implementation example question

What is the fastest AVL algorithm to insert one new node to an almost perfect AVL tree with only two different heights. This tree has an almost perfect balance. Does the global height increase?
-2
votes
2answers
52 views

Prove that the class of regular languages is closed under three operation

We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...

15 30 50 per page
1
2 3 4 5
847