All Questions
47,739
questions
0
votes
0
answers
11
views
Singleton is not well-defined, is it?
The Singleton design pattern is designed with references of itself:
...
- 1
0
votes
0
answers
11
views
Which of the following statements about computable functions is true?
Assume that $f: \mathbb{N} \to \mathbb{N}$ is total and $g: \mathbb{N} \to \mathbb{N}$ is primitive recursive and $h: \mathbb{N} \to \mathbb{N}$ is Turing computable. Which of the following statements ...
- 463
1
vote
0
answers
12
views
Why Is Inverse Quantization and Inverse Transform Taken Before Motion Estimation in H.264?
Here is the block diagram of the pipeline for the H.264 encoder (Fundamentals of Multimedia by Ze-Nian Li, Mark S. Drew and Jiangchuan Liu).
The feedback loop is used for motion estimation, but why ...
- 111
0
votes
1
answer
7
views
Name of class of errors where the real state differs from the recorded state?
Is there a name for the class of software errors that arise from the fact that the software believes something wrong about the state of the world?
(Allow me a bit of anthropomorphization of software, ...
- 101
0
votes
0
answers
19
views
Potential method: prove that dynamic table compaction runs in amortized constant time
Suppose we are given a dynamic table $T$. After the $i$th operation, $num_i$ is the number of elements stored in $T$, and $size_i$ is the capacity of $T$. Let
$$
\alpha_i = \frac{num_i}{size_i}
$$
be ...
- 52
0
votes
0
answers
3
views
Identifying peaks at every cluster
I have a data set showing different clusters of data points and was attempting to find a way to get the peak of at every cluster. Comparing the moving average between a set of points does not work as ...
- 101
0
votes
0
answers
9
views
Deadline Monotonic formula with same priority
I have a question related with the response time of Deadline Monotonic scheduling...let's assume that there are 4 tasks, and the processor only allows to have 3 task priorities, thus there will be 2 ...
-1
votes
0
answers
9
views
How to Design Synchronous Circuit with 7 Segment Display
Design a synchronous counter using JK flip flops and NOR(or inverted) for the following sequence: the value of your counter will be displayed using 7 segments display; this will require bcd-7 segments ...
- 1
0
votes
0
answers
13
views
Mapping relationtional data to hierarchical data (JSON, XML, etc.)
I'm working on a project that involves mapping relational data to a tree hierarchy. The hierarchical data is preferred to be JSON or XML. Is there an existing general algorithm for this?
Current ...
3
votes
2
answers
164
views
Find Minimum Transformation Between Multisets of Lists of Cards
Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
- 51
0
votes
1
answer
24
views
Shortest Hamiltonian Path in a Complete Graph
I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is in NP. I am wondering, however, if the restriction to a complete weighted graph emits an algorithm in P. ...
0
votes
1
answer
37
views
What is the hit rate of the cache when executing this code?
C++ code:
int main()
{
short int arr[4][4];
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
arr[i][j] = i+j;
}
}
return 0;
}
Is there ...
- 1
0
votes
0
answers
28
views
HAMILTONIAN PATH AND SUBSETSUM
If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P?
...
- 1
0
votes
1
answer
26
views
Guess the output of a c program [closed]
I have come across a c program like this .
int main()
{
int a,i=4;
int z=5;
a=--i+ --i+ --z;
printf("%d %d",a,i);
return 0;
}
What will be the output? I need some explanation.
0
votes
0
answers
18
views
CFG PL for L=\{a^ib^j \mid j = i^2\}
where i got it from. This was weird so I wanted to try it myself because they way he did it seemed wrong. So this is my attempt is it correct?
I did not add the basic parts of the pumping lemma proof ...
1
vote
1
answer
17
views
How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?
$\mathsf{RP}$ can be deterministically defined as:
A language $L\in\mathsf{RP}$ iff there exists a polynomial $p$ and deterministic Turing machine $M$, such that:
$M$ runs for polynomial time $p$ on ...
- 1,429
0
votes
0
answers
20
views
How do you use Rice's theorem and why does it make sense? (Use provided Rice's theorem)
So this is the Rice's theorem we were provided:
Definition: $TM$-$FUNC(S)$
Input: Turing machine $M$
Question: Is $f_M \in S$
Let $S$ be a set of computable partial functions with $\emptyset \neq S \...
- 1
10
votes
1
answer
327
views
Are there associative cryptographic / collision resistant hashes?
Git uses SHA hashing as a content address key. This relies on their being a vanishingly small probability that two different pieces of content will ever hash to the same key.
For content ...
- 263
-1
votes
1
answer
33
views
Does the Halting Problem Explain the Fermi Paradox?
The Fermi Paradox asks why we have not yet encountered other intelligent life given the high chance of intelligent life emerging.
I recently had the following thought:
Evolution shapes the behaviour ...
- 1
0
votes
0
answers
23
views
Proving $A_{TM}$ is mapping reducible to certain language
I've been asked to prove that the language $A_{TM} = \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ is mapping reducible to the language $LOOP-ONE = \{\langle M \rangle \mid M$ is a Turing ...
- 229
0
votes
0
answers
29
views
Dynamic Program to find well formed set in a rooted tree
You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
- 139
0
votes
0
answers
20
views
Proof that DFS order is P-complete [closed]
Suppose we are given an oriented graph G with a selected number of nodes s, where for each node some particular ordering of edges leading from it is specified. If we run a depth-first search algorithm ...
0
votes
0
answers
39
views
Designing a Turing machine (TM) to multiply a unary number by 2
Now, I have assumed the unary number to be 1.
and my doubts are
Do you design this machine similar to normal unary multiplication assuming that the constant 2 (11) is always present in the input tape?...
1
vote
0
answers
25
views
Find maximum sized rectangle on a plane
I'm given a rectangular plane with width, height and a set of rectangles defined by left, <...
- 31
0
votes
0
answers
12
views
Flowgarithm for common child program for a beginner (without pointers)
I'm a first year BCA student. Can you help me with flowgarithm of the common child problem (LCS) without pointers
0
votes
1
answer
19
views
What is the name of the diagram used in JSON spec for representing a context-free language?
If you go to the JSON spec page : https://www.json.org/json-en.html, then you'll see the language represented by some diagrams showing graphically what the language looks like. I wondered, does this ...
- 101
-1
votes
1
answer
22
views
1
vote
1
answer
15
views
Max flow, min cost with upper and lower bounds
:)
I am trying to implement an algorithm that fairly distributes people into groups, given their ranking of those groups, while also taking into account their preference for partners.
I have modeled ...
- 11
-1
votes
0
answers
11
views
Need Clarification on Storage Media Statements - Seeking Help
I am currently working on a set of questions related to storage media, and I've come across a statement that seems a bit confusing to me. The question is as follows:
Mark all correct statements ...
0
votes
0
answers
41
views
The second shortest path on a directed graph
The question asks to write an algorithm using Dijkstra's algorithm with time complexity of
$\Theta(|E| \log |V|)$ that find the second shortest path between s∈V and t∈V.
The farthest I managed to get ...
- 1
-1
votes
0
answers
21
views
Backpack assigment
Can you help me solve this problem. Names of items NAME, sizes SIZE and values VALUE are given. Using dynamic programming, find the optimal filling of backpacks of size M. NAME = {A, B, C, D, E}, SIZE ...
- 1
0
votes
1
answer
24
views
Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)
Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element.
Any subarray array[start, end] ...
- 1
2
votes
0
answers
36
views
Shortest path in polygon from 2 points such that entire polygon is visible
Given an isothetic polygon (sides parallel to the x-axis or y-axis) and 2 points (start and end) on the boundary of the polygon,
find the shortest path traveling only in the direction of the x or y ...
0
votes
0
answers
11
views
Dynamic programming problem for minimum cost tower placement
I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
0
votes
0
answers
33
views
data flow analysis reaching definition analysis meaning
I'm trying to understand reaching definitions and I'm having hard problem wrapping it around my head with the following definition (taken from the the following paper page 114):
$B_i\;\text{be a ...
- 103
0
votes
0
answers
26
views
Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
3
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
4
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
1
answer
30
views
Will a FIFO buffer eventually stagnate?
Below depicts a FIFO buffer:
So the buffer is there for when the speed of data written into the FIFO buffer is faster than the data read.
But I don't understand one thing. Wouldn't eventually all the ...
- 101
-3
votes
0
answers
15
views
python django- adding a like function button [closed]
I am trying to add a like function to my blog, but I keep getting this error.
0
votes
0
answers
10
views
What are some good books for vlsi cmos design? Or some good educational software?
I'm a student trying to learn more about CMOS design, I already understand assembly and computer architecture, but VLSI is very interesting and I was wondering if you guys knew some good books/games ...
1
vote
0
answers
16
views
Approximation Algorithm for Bin packing Variant with Packing Overhead
I recently came up with this bin packing variant and was wondering, if someone has studied it before:
Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
- 11
1
vote
1
answer
38
views
(Co)-induction, fixpoints and inference systems
I'm learning about induction and co-induction. From what I know, given a set of judgments $U$ and an inference system $\Phi \subseteq \wp(U) \times U$, where $(\left\{ h_1,\dots,h_n \right\}, c) \in \...
- 13
-1
votes
0
answers
18
views
How to construct a turing machine from L= {w (a Ub)* | w = wR} [closed]
How to construct a Turing machine from L= {w (a Ub)* | w = wR} . I have to design a Turing machine in exam. help me.
-2
votes
0
answers
22
views
Maximum flow of multiples [closed]
The problem is that I'm given 3 numbers N which represents the number of nodes in my graph, M which reprensents the amount of vertexes and x which represents an amount of people. The problem is that I ...
- 1
-1
votes
0
answers
6
views
I need help plotting a 3D trajectory field for a 3x3 matrix [closed]
I'm trying to plot the trajectories of a 3x3 matrix. I can do this on the 2D plane but cannot get it to work on the 3D plane as needed for a 3x3 matrix. When I try to use
from sage.plot.streamline ...
0
votes
1
answer
58
views
Visiting all nodes of a directed graph exactly once (not dfs)
Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should ...
- 35
0
votes
0
answers
32
views
Greedy Maximum Bipartite Matching
To find the maximum matching on a bipartite graph, I propose the following greedy algorithm:
At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours ...
1
vote
0
answers
19
views
Computing the centroid of an "ellipsoid slice"
I want to compute the centroid of a body of the following form:
$$
E\cap H_1\cap \cdots \cap H_T
$$
where:
$E$ is an ellipsoid in $\mathbb{R}^d$: $E = \{x = c + Bu | u^T u \leq 1\}$, where $c$ is the ...
- 5,730
3
votes
0
answers
65
views
Subset sum problem with big items
Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
- 5,730