All Questions

1
vote
1answer
26 views

Path of maximum value with bounded cost in DAG

Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is ...
0
votes
0answers
18 views

Multi-dimensional knapsack

Consider a multidimensional knapsack problem, and let $M$ denote the number of knapsack constraints. I am trying to solve a problem where $M$ is exponential in the number of $0-1$ variables in my ...
-1
votes
0answers
26 views

TypeError: 'float' object cannot be interpreted as an integer (using numpy in python) [closed]

test = np.random.randn(0, 0.25) I'm trying to generate a random number with a mean of 0 and variance of 0.25. When I run it I get this error: TypeError: 'float' object cannot be interpreted as an ...
2
votes
0answers
13 views

Best asymptotic randomized multidimensional index?

What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention ...
1
vote
1answer
29 views

Pumping Lemma vs Myhill-Nerode [duplicate]

I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much. Let us take the following as an example: $$ L = \{ a^n b^n \mid n \ge 0\} $$ ...
5
votes
1answer
35 views

“Functional dependencies” with cardinality constraints

Let us write $\{ A_1, \ldots, A_k\} \rightrightarrows^n \{B_1, \ldots, B_m\}$ for a relation $R$ if for all $\langle a_1, \ldots, a_k\rangle$ we have $\left\lvert \pi_{B_1, \ldots, B_m} \sigma_{\...
6
votes
0answers
105 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
0
votes
0answers
26 views

Show that the language L = {www : w ∈ {0, 1} ∗} is not regular [duplicate]

Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved? Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from ...
9
votes
0answers
111 views

How would a CPU designed purely for functional programming be different?

CPU's are to an extent designed with in mind the software that people will write for it, implicitly or explicitly. It seems to me that if you look at the design of instruction set architectures, ...
3
votes
1answer
263 views

Difference between sequential and parallel divide and conquer

In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy In divide and conquer, we ...
1
vote
1answer
26 views

Pumping Lemma on Language with subtracted length

My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given $$ L = \{ a^k b a^{m-...
0
votes
0answers
15 views

Looking for resources for coding skills [closed]

I'm a college student majoring in Computer Science and I've been learning the material for about 3 years now. I've taken most of my mandatory courses including Data Structures and Algorithms and ...
1
vote
1answer
36 views

Asymptotic relation between n! and (n+1)!

I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
-1
votes
0answers
15 views

How do you find DES algorithm encryption and decryption time? [closed]

I'm doing a project where I need to measure encryption time and decryption time for DES algorithm to compare it to modern standards, but I don't know where to find the most accurate algorithm. There ...
0
votes
0answers
56 views

By induction on the length of derivations prove that PR ⊆ P and R [closed]

Any idea on how to do the question? I only know that P = partial function, R = total function. I guess that PR = primitive recursive function, right?
0
votes
0answers
27 views

Find the smallest width annulus in O(n)

Given set of points (in the plane), find in a linear time the smallest width annulus (annulus is the region between two concentric circles) that contains all the points. Because of the time ...
0
votes
0answers
12 views

How to find equivalence classes for a regular language? [duplicate]

I was wondering if there is a formal approach to find equivalence classes for a regular language. My guess: Construct a minimal DFA based on given regular language. Based on states in DFA, we can ...
1
vote
1answer
33 views

If there is any sense of an optimal set of instructions in an ISA

So there are One Instruction Set Computers, having only one (complicated) instruction like addleq, "add and branch if less than or equal to zero". And then there ...
0
votes
0answers
8 views

Why is the size of a word limited? [duplicate]

In Chapter 23 of CLRS, the following quote appears: We also assume a limit on the size of each word of data. For example, when working with inputs of size $n$, we typically assume that integers ...
2
votes
1answer
19 views

Why are regular expression used in lexical analysis instead of grammars?

Even though grammars can do what regular expressions do, why are regular expression employed instead of grammars in lexical analysis?
2
votes
1answer
21 views

Fast multiplication with a full binary $n \times 2^n$ matrix

Let $A$ a $n\times n$ matrix, and X the full matrix of $n\times 2^n$ binary vectors (you can choose the order of the columns of X). What is the fastest way to compute the product AX?
0
votes
1answer
22 views

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$ I think this languages is regular. I write regular expression: $(1 + 2 + 0) ^ {*} (11 + ...
2
votes
1answer
38 views

How do I know which direction I should rotate a node in an AVL Tree?

I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL ...
1
vote
0answers
14 views

What if SAT Turing-reduces to a problem? [duplicate]

To show that problem is NP-hard, we take a known NP-hard problem and reduce it to the problem whose NP-hardness we want to prove. The reduction we need is polynomial time reduction. But If I take ...
0
votes
0answers
11 views

Denset-k-subgraph to ILP reduction [closed]

I have exercise: Show reduction Denset-k-subgraph to ILP (Integer Linear Porgramming). (Denset-k-subgraph is problem where there is graph G = (V, E) and two natural numbers k and t. We are ...
1
vote
1answer
15 views

What does it mean to take a union of a transition function with a starting state?

$$ \delta(q,a) = \begin{cases} \delta_1(q,a) & q \notin F_1 \text{ or } a \neq \lambda \\ \delta_1(q,a) \cup \{q_1\} & q \in F_1 \text{ and } a = \lambda. \end{cases} $$ Look at the second ...
0
votes
0answers
29 views

Contraction Hierarchies minimal distance proof

I am trying to implement "Contraction Hierarchies" algorithm and reading the white paper and watching video lectures [6,7]. But still I can't understand proof for the following lemma: Lemma 1. $d(s,...
1
vote
1answer
27 views

Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$

I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method: $$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$ First, we have: $a = 10,\ b = 2$ ...
-2
votes
0answers
28 views

What did my teacher tell me in machine learning? [closed]

So my teacher told me something along the lines of dependent and independent matrices related to Android and unpacking Android files to Java ones and checking dependent matrix or something of that ...
1
vote
0answers
11 views

3D registration for reconstructed surface

I use Meshroom (based on the framework AliceVision) to reconstruct a scene based on photographs (e.g. a bottle on a table in a room). The software captures the bottle, but also the table and the whole ...
2
votes
1answer
19 views

Is there an algorithm for selecting best matching data in a data set given a set of parameters?

What I am trying to do is for a diet app that I am planning to build. The goal is the users will input their desired macros (carbs, fat, protein) and the system should find all recipes that match the ...
1
vote
2answers
43 views

Why databases make the distinction between basic logical operations and functions

It just occurred to me that things like "greater than or equal to" and other "logical operators" are also just simple functions, such as gte(a, b) == a >= b. ...
1
vote
1answer
40 views

Shortest path from source to all vertices, but with some wildcards

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer). You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
2
votes
0answers
40 views
+50

Bottom up chart parser adding active arc step

I am following Bottom up chart parsing algorithm from Natural Language Understanding book by James Allen. It is I couldn't understand the 3rd step. I thought that when active arc is added the dot ...
5
votes
2answers
57 views

Identity types and universes

Let us consider Martin-Löf type theory with a cumulative hierarchy of universes $$ \mathcal{U}_0\colon\mathcal{U}_1\colon\ldots $$ If $A, B\colon \mathcal{U}_i$, we can form an identity type $A=_{\...
1
vote
1answer
13 views

For a given k-DNF formula, what is the size of the formula for the purpose of complexity?

I am currently in the process of proving some complexity bounds about k-DNF. However I am confused what the $n$ in the time complexity would refer to in this case (that is that I don't know how the "...
0
votes
0answers
19 views

When is a code vulnerability ok to leave alone? [closed]

I'm getting a minor vulnerability in one of my projects, which happens to be a discord bot. should I leave it alone, or remove the feature that introduced it, since it is a dependency vulnerability ...
2
votes
3answers
78 views

How does a computer “wait” time?

Me and a friend were discussing how programming languages can perform asynchronous tasks, like waiting 15 seconds before performing another task, and we started a debate. I know that computers have ...
0
votes
0answers
17 views

If you can have cyclic base types, or if they need to be infinite types

I am confused how to properly think about classes of classes. Basically, you can have a dog "filo" which is an instance of the dog "class". But the dog class is itself not an instanceof of "animal", ...
2
votes
1answer
41 views

Prove number of nodes in heap

Consider a variation of the normal heap which we will call the x-heap The x-heap of height $h$ has the following properties: It will have $2^h$ nodes A height of $0$ corresponds to the single root ...
0
votes
0answers
20 views

Church-Turing thesis and hypercomputation?

The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource ...
0
votes
0answers
20 views

Precisely when and where was Feynman's Computer Heuristics lecture given?

Feynman's Computer Heuristics lecture was apparently given at the Esalen Institute, Big Sur, California, in 1985. But I have no formal evidence of this. Has anyone ever cited this lecture that you ...
0
votes
0answers
23 views

Knapsack approximation algorithm (weights scaling)

I am trying to prove the following Knapsack approximation algorithm, the problem definition: Input: A set $S$ of $n$ objects that contains weights and values: $w_1,w_2,\ldots,w_n$ (weights) $...
0
votes
1answer
41 views

Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free

$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ In my opinion complement of the L language is $L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$ I choose to ...
0
votes
0answers
10 views

What's the difference between size ordering/ data ordering/ least recently used rule?

What's the difference between size ordering/ data ordering/ least recently used rule? I did lots of researches already, and most of the books say: Data ordering: Arrange all possible assertions in ...
1
vote
1answer
179 views

$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree

I'm having trouble making an algorithm to fit these specs: Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves. Reading the leaves from left to right makes a sequence of integers (...
3
votes
2answers
42 views

First half of context-free palindromes

If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise. Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
0
votes
0answers
11 views

Distributed maximal matching from vertex coloring

How to use a $\Delta +1$ vertex coloring to find a maximal matching in a distributed graph.
1
vote
0answers
20 views

Solve a 2D grid which is already connected

You are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output ...
0
votes
1answer
25 views

Algorithm comparison

I am learning Big O and Big theta notation and confused the certain case. I have two functions, function 1(f1) $$ n * n^{1/2} $$ function 2(f2) $$ 1.001^n $$ in smaller cases (10,000) f1 is much ...

15 30 50 per page