All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
3 views

Find $k$ shortest paths in linear time

Suppose given number $k$ and undirected unweighted graph $G=(V,E)$, also given two vertices $s$ and $t$. Can we find $k$ shortest paths between $s$ and $t$ in $O(n+m)$ without term $k$? I read this ...
user avatar
0 votes
0 answers
4 views

The Language of All Palindromes - Is it CFL?

Regarding $L=\{ww^R~|~w\in\Sigma^*\}$ - The language of all palindromes. Is it a CFL? I think it is, because if we take any $\Sigma$, for example $\Sigma=\{a,b\}$, then it certainty is. CFL are closed ...
user avatar
0 votes
0 answers
18 views

Formal mathematical resolution for Recurrence Relations

let's suppose we've got a simple Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases} $$ At lesson we've resolved it, but I ...
user avatar
0 votes
1 answer
23 views

Cosine distance in a space, and cheating?

I read an example of using cosine distance in RGB space, and it pointed out that (eg.) dark red and light red have a cosine distance (CD) of zero because CD only gives you the angle between vectors ...
user avatar
0 votes
0 answers
9 views

Can you safely use the remaining space on a an external hard drive used for a recovery drive? [closed]

I created a recovery drive with the Control Panel's Advanced Recovery Tools, on an external hard drive. Is it safe (for the purposes of retaining a functional recovery drive) to create a new simple ...
user avatar
0 votes
0 answers
27 views

Undirected unweighted sub-graph enumeration with threshold on node value

I have an undirected, unweighted graph $G=(V,E)$, and a function $f:V\to [0,1]$ where $[0,1]$ denotes the interval of real numbers from $0$ to $1$ inclusive. Given an input threshold $t\in [0,1]$, I ...
user avatar
0 votes
0 answers
23 views

Tight bounds for expected maximum of k binomial(n,p) IIDs

What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables I tried to derive it : $$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^...
user avatar
1 vote
1 answer
37 views

How many different boolean functions exist up to permutation of its $n$ variables

i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
user avatar
0 votes
0 answers
14 views

How do I determine how many blocks have been replaced and what the hit ratio is of the following direct-mapped cache?

I have a direct-mapped cache with the following properties: Address size = 32 bits Cache block size = 8 words Entries = 32 So we can see the cache as a 32 by 8 table where the index selects the row ...
user avatar
  • 121
1 vote
2 answers
41 views

Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ $E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$ The standard proof for the undecidability of $E_{TM}$ is given in this ...
user avatar
-3 votes
0 answers
26 views

Fixed parameter tractability Big O

Was wondering if anyone had some guidance as to whether the following big-O expressions are fpt and what the smallest possible set of parameters would be to make them fpt.
user avatar
  • 1
0 votes
0 answers
34 views

Binary compression algorithem with decompress by index

I have a list of 256-bit data to store. How to compress it losslessly so that I can retrieve an entry by its index without decompressing the whole data. I will also need to code this algorithm ground-...
user avatar
0 votes
1 answer
15 views

Multi Objective Optimization Using Only Single Objective Optimization Algorithms

Let's say there is a single objective optimization problem SP (e.g. a linear program) and an optimization algorithm SA for it (e.g. simplex). Then applying SA to SP yields an optimal solution ...
user avatar
0 votes
2 answers
45 views

A little confusion with Big Theta time complexity

I came across one Big Theta expression: Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function ...
user avatar
1 vote
0 answers
23 views

Dot symbol in set-builder expressions in CRDT literature?

In Conflict-free Replicated Data Types: An Overview and other CRDT-related publications by Preguiça's group, a dot symbol often appears without definition. What does it indicate, how standard is it as ...
user avatar
  • 11
-3 votes
0 answers
25 views

Its about automata [closed]

Find regular expression for language that accepted exactly one double letter then find NFA and convert to DFA, find CFG for this regular expression?
user avatar
1 vote
1 answer
57 views

Are reversed reverse preorder traversals equivalent to a postorder traversal?

I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse ...
user avatar
  • 113
0 votes
1 answer
52 views

Why is there a 'true' statement as precondition in the following loop invariant

Precondition: true int i = 0; while (i < a.length && a[i] != x) { i++; } Postcondition: (∀ j : 0 ≤ j < i : a[j] ≠ x) ⋀ (i = a.length ∨ a[i] = x) } As I read it, the program has no ...
user avatar
  • 115
-1 votes
0 answers
39 views

Implementing multidimensional integral for a custom function in C++ [closed]

I am not an expert with C++, but I am trying to implement a 4-dimensional integral using GSL numerical integration approach. The code below shows the whole algorithm. Although it seems correct what I ...
user avatar
-1 votes
0 answers
20 views

How can I calculate the computational complexity of an equation composed of $2n$ multiplications and $2nm^2$ additions? [closed]

I want to calculate the computational complexity in term of the big ($\cal O$). My equation is: It composed of 2n multiplications and $2nm^2$ additions. The complexity of this equation is it ${\cal O}...
user avatar
0 votes
0 answers
14 views

What is the Parse tree for example 2.6 from Aho's Compiler Dragon Book? [closed]

I am very sorry to screen readers for the image but I want parse trees for 9 + 5 * 2 and 9 * 5 + 2. They have a grammar: ...
user avatar
0 votes
0 answers
23 views

Is copying and pasting a sort of object embedding?

If I copy a picture and paste it into Microsoft Word, would there be the difference if I embedded the same picture into another Word file ? Are they both object embedding?(As the object is saved in ...
user avatar
0 votes
0 answers
57 views

Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
user avatar
2 votes
3 answers
102 views

Find the smallest difference between two numbers in a DS in O(1) time

I got an assignment to create a new data structure, with the following rules: Init - O(1). Insert x - O(log$_2$n). Delete x - O(log$_2$n). Search for x- O(log$_2$n). Find max difference between two ...
user avatar
0 votes
0 answers
17 views

Considering definitions as equalities, what would happen if you continually substituted a word’s definition?

I’ve had this question for several years now but have next to no programming experience, nor good connections to anybody who does. So I decided to see if stack exchange had an answer. The idea is to ...
user avatar
1 vote
0 answers
17 views

Relation between left derivations, right derivations and number of parse trees?

I saw this question on a test-prep site Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees? ...
user avatar
1 vote
1 answer
16 views

Efficient search of a large set of documents to find documents that only contain a particular set of words

Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language. Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
user avatar
2 votes
1 answer
510 views

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

The problem concerns finding shortest paths in graph from a single source to a single destination. So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
user avatar
0 votes
0 answers
29 views

Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized

Given a graph with $V$ vertices and $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $...
user avatar
3 votes
2 answers
1k views

Length of a regular expression

What is the definition for the length of a regular expression? This question might sound simple, yet I cannot find a definition. Do I only count letters from the alphabet? Do * and $\cup$ count? For ...
user avatar
-1 votes
0 answers
25 views

Work out corresponding logical address

this should be a simple question but I don't quite understand how to work out the logical address from the information given. Question: Suppose a program is running on a system with a simple base ...
user avatar
  • 1
0 votes
0 answers
13 views

Can you a push multiple symbols on simplified PDA stack in one transition?

I encountered this problem when I was converting a PDA to a CNF and I was looking for two transitions that push and pop the same symbol(one pushes and one pops). The PDA I was converting had this ...
user avatar
  • 61
0 votes
3 answers
70 views

How is pipelining possible?

As far as I understand pipelining is a way to excecute a instruction every clock cycle. It is a process performed on single cores. My question is how does the control unit handle this, at some point ...
user avatar
  • 1
1 vote
1 answer
22 views

Can Boolean circuits of polylog depth represent all Boolean functions?

Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to ...
user avatar
  • 258
0 votes
1 answer
18 views

Switching between doing something and not doing it within $k$ steps in LTL

Imagine that we are designing a system in which we have the action to brake or not brake. How can we write an LTL specification that guarantees that we cannot switch between braking and not braking ...
user avatar
0 votes
0 answers
20 views

Time complexity of find() operation for a Merge-Find Set

Given a Merge-Find Set implemented using a set of linked-lists, my professor says that the time complexity of find() operation is O(1). Each element of the lists ...
user avatar
  • 315
0 votes
1 answer
73 views

I think I have discovered a new sorting algorithm using binary search tree [closed]

If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
user avatar
-1 votes
0 answers
23 views

Time complexity of a dynamic programming algorithm?

$$a_1,\dots,a_n$$ $$b_1,\dots,b_n$$ are integers bounded in $[-B,B]$ and we want to find a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{i\in I}a_i=\sum_{i\in I}b_i=m.$$ This problem is $...
user avatar
  • 2,820
3 votes
1 answer
61 views

Allocating m rooms of varying capacity to n booking requests of varying sizes

I am developing a system which performs automated room allotment. We have finite number of rooms, each with varying capacity. Each booking request is also of varying size. The goal here is to minimize ...
user avatar
1 vote
1 answer
52 views

How to convert AFA to ε-NFA / NFA / DFA?

Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and ...
user avatar
1 vote
1 answer
78 views

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis: Imagine that the following big-O expressions ...
user avatar
1 vote
0 answers
17 views

RP with very small error = P

I was asked to show the equality $ RP(1 − 2^{-2^{n}}) = P $, which seems wrong to me (?). The $ \supseteq $ direction is obvious, and I want to show the other direction. My first intuition was to run ...
user avatar
  • 111
2 votes
1 answer
109 views

Disprove: if L is decidable then Prefix(L) is decidable

The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
user avatar
1 vote
0 answers
28 views

Split Bipartite Graph

I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
user avatar
  • 143
0 votes
1 answer
70 views

Finding a Hamiltonian Cycle in a directed graph - graph problem

$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
user avatar
  • 29
1 vote
1 answer
37 views

Is finding the union of all minimum hitting sets NP-hard?

Let's start with the well-known minimum hitting set problem (known to be NP-hard): given some collection of sets: $U = \{S_1, S_2, S_3\} = \{\{1, 2, 5, 9\}, \{1,2,7\}, \{42, 13, 23, 1, 2\}\}$ for ...
user avatar
  • 13
0 votes
0 answers
19 views

Entropy of a single Hint

Assume that the probability that a woman is above 80 years old is 3 times that of a man. How much information (in bits) do you get if you are given that a 80 year old person is a male? How should I ...
user avatar
0 votes
1 answer
17 views

Is there an algorithm for mapping two ambiguous and unrelated data sets?

I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets. So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac ...
user avatar
  • 1
0 votes
0 answers
22 views

What kind of CNF and DNF are in P [closed]

could anyone help me to prove which languages are in P? I will present my thoughts but I do not know how to go from there. Thank for any help l1 = {L | L is on CNF and is satisfiable} l2 = {L | L is ...
user avatar
  • 103
1 vote
1 answer
18 views

Max matching algorithm lemma approximation algorithm

We have this algorithm which is supposed to find max matchings. ...
user avatar
  • 25

15 30 50 per page
1
2 3 4 5
885