0
votes
0answers
6 views

Is it fair to withhold test and assignment memorandums at tertiary educational institutes?

I have a module at university that broadly covers data structures and algorithms. The subject coordinator of said module simply refuses to supply any feedback or opportunities to students that want to ...
2
votes
1answer
11 views

How to show ExactOneSAT is NP-Complete?

$\text{ExactOneSAT}= \{\phi\;|\;\phi\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \}$ I am trying to reduce 3SAT to this ...
0
votes
0answers
6 views

Elimination rule for the equality type aka J axiom

I'm implementing a interpreter for lambda calculus, and now I want to add the equality type. The introduction rule for it is easy, but the elimination rule is rather obscure for me. I found this ...
1
vote
1answer
14 views

regular expression to accept all strings other than one containing ads or adlib

My intention is to select only those packages whose name contain adlib or ads ........but if i add *adlib* and *ads* it diselect all packages containing the ...
0
votes
0answers
1 view

Is it a good idea to determine coordinates of object on images with regression algorithms?

I am doing doing one of getting started competitions on kaggle, the one which requires you to find coordinates of different objects on images. I know that the usual method for this is to use sliding ...
0
votes
2answers
18 views

Maximum frequency in any row and column

I have been given 2D matrix with some elements. I want to find out what is maximum frequency in any row and column. Example: 1 2 1 2 3 4 1 2 1 1 1 1 2 2 2 2 Maximum frequency is 6 which occurs in last ...
0
votes
0answers
11 views

Relation between determinant and matrix multiplication

I remember reading somewhere that if matrix multiplication can be done in $O(n^\omega)$ time then determinants can be computed in $O(n^\omega)$ time. I am unable to find the reduction and would it be ...
0
votes
0answers
8 views

On relation between FFT and polynomial multiplication

Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ ...
0
votes
0answers
9 views

Understanding Murmur3

The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the seed parameter to easily create a variety ...
1
vote
0answers
17 views

On formula complexity of permanent

Is it consistent with our knowledge that $VNP=VP$ and/or $Permanent\in P$ but still formula complexity for permanent is large? If so what would exponential formula size for permanent give and why ...
0
votes
1answer
15 views

Checking my understanding of right quotient

So I am trying to fully understand the concept of quotient languages. I will give some examples, let me know if this is correct: Say that ...
-5
votes
0answers
20 views

What is the complexity of this code?

I am trying to figure out the complexity of these codes,i am new to algo analysis so please explain the concept for these two ...
0
votes
0answers
7 views

Using abstraction (generalization and aggregation) in db-tables?

I'm confused about the abstraction (generalization and aggregation) within an entity–relationship model: how is this useful? should I map this on my relation-model (db-tables)? what are the ...
1
vote
1answer
14 views

(a,b)-tree vs B-tree

I would like to know what are the differences between (a,b)-tree and a B-tree. It has been a few days I am studying different papers and I am seeing different definitions that make me confused. For ...
-2
votes
0answers
10 views

Robot model recommendation

I have to find a robot that I can program to: recognise and talk to people (it needs to have a camera and microphone) wave its hands and move around on wheels or legs I was given a budget of £500 ...
0
votes
0answers
14 views

What's the diff between a philosophical ontology and a computational ontology?

A computational ontology is supposed to be decidable and tractable, how else is it different from a philosophical ontology? Is there a peer-reviewed explanation of the similarities and differences ...
1
vote
0answers
12 views

Proving a certain superset of $L_{halt}$ is $\notin R$

Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w ...
0
votes
0answers
14 views

Heuristic Arguments against Existence of very inefficient alogirthm for SAT

I am reading the Handbook of Satisfiability and in the preface Martin Davis wrote Of course what is regarded as the most important problem in theoretical computer science, P = ? NP lives right ...
1
vote
0answers
6 views

Space complexity of random sampling

I asked this on cstheory but got no answer so far, so posting here. Consider a computational model with three tape (probabilistic/non-deterministic) TMs. (read-only) Input, (read-write) work, and ...
2
votes
1answer
21 views

Probability bounds on size of smaller partition in randomized quicksort

Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability ...
1
vote
0answers
18 views

Homomorphic computation?

Cryptography has the concept of homomorphic encryption. Homomorphic encryption lets you transform binary values into an encoded form, put them through a circuit and then decode the bits, getting the ...
0
votes
0answers
9 views

physical address

The address stored in CS register is 1234H and IP register is 5678H, then the physical address is 179B8H But Why 1234H can be written as 12340H? Also,the character of the address which store in CS ...
0
votes
1answer
26 views

Question on interpreting logical notation, relating to alphabets, theoretical comp sci

$\exists x \in \Sigma^* (t=sx)$ Have I interpreted the above into words correctly?: "There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, ...
1
vote
2answers
36 views

What is the Big Theta of $(\log n)^2-9\log n+7$?

How can I find the Big Theta of $(\log n)^2-9\log n+7$? I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.
3
votes
1answer
32 views

A Shortest Path Strange Formulation, or new modeling?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. For ...
1
vote
1answer
50 views

Single-source shortest paths as a linear program

I saw that I can formulate single-source shortest path as the following linear program: Given $G=(V,E)$ and $w\colon E\to R$ and with negative cycles, find $\max\,d(s,t)$ such that \begin{align*} ...
1
vote
1answer
17 views

Unconditional arithmetic circuit lower bounds for permanent/determinant

In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) ...
1
vote
2answers
15 views

Operating System - CPU scheduling Decisions

I understand that CPU scheduling takes place on 4 circumstances listed below: When the process changes state from Running to Ready Changes state from Running to Waiting Changes state from Waiting to ...
0
votes
1answer
87 views

Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

Suppose we define an operation such that $$A \text{ avoiding } B = \{w \in A \mid w\text{ has no substring in }B\}\,.$$ How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ ...
-1
votes
0answers
21 views

Turing machine problem with function. Modification of a function [on hold]

EDITED It has to do with a programming language that the author of a book created, named NICE language. Short simple, each Turing machine can be converted to a NICE program. And the questions are ...
1
vote
1answer
45 views

What is the difference between modulo and modulus?

Throughout my education in computer science, I feel like I've heard the terms "modulo" and "modulus" used interchangeably. It looks like even Wikipedia claims that "modulo" is "sometimes called ...
1
vote
1answer
40 views

Select the maximum number of links to satisfy per-link constraint. How to prove is NP-hard?

I asked, incorrectly, my previous question here. I would like to thank D.W. for his answer though. He answeres that the problem is polynomial time solvable. The thing is that the cited paper shows ...
0
votes
1answer
23 views

what is the difference between memory access and data memory access?

what is the difference between memory access and data memory access? for example, here are the examples of register transfer language instructions: $R1 ←[18]$ $R2 ←[R1 +3]$ $R1 ← R1 ...
1
vote
2answers
34 views

Select the maximum number of links to satisfy the constraint on each link. How to prove is NP-hard?

Instance: $n$ non-negative real numbers $P_1,\ldots,P_n$, a positive number $k\le n$, and a positive number $\epsilon$. Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ ...
-3
votes
0answers
15 views

Bob Light alternative [on hold]

I have been trying to get per frame color of different movies but using bob light expected out is not coming so is there any alternative of bob light?
3
votes
0answers
22 views

Computing the index in a structured way

I want to map the various combinations to an unique index: For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$: Ex: For n = 6, r = 3 [012, 013, 014, 015, ..., ...
1
vote
1answer
23 views

Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$. The modified algorithm ...
-1
votes
1answer
23 views

Why no rotate property in matrix 2d? [on hold]

Why no rotate property in matrix 2D ? we know the short hand code in matrix 2D transform:matrix(a,b,c,d,x,y) a=scale X b=Skew y c=skew X d=scale Y x=translate X y=translate Y why developers didn't ...
1
vote
3answers
114 views

Acceptance of empty string by nondeterministic automaton

Why is the input $\epsilon$ accepted by the nondeterministic finite automaton shown below? Does it not leave $q_1$ and go to $q_3$?
1
vote
1answer
34 views

Revisiting Fixed Point: What does it mean in the world of computer science?

A while ago I asked Fixed point, what does it mean in the world of computer science? While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever ...
0
votes
0answers
12 views

Understanding an MPI error [migrated]

I am fairly new to computer science (chemistry background) but am writing a code that uses MPI in C. Every time I compile my code I get various errors, for instance, ...
-1
votes
0answers
12 views

Research topics of information systems [on hold]

My name is Hary, I am a master student, majoring in information systems. I was looking for a research topic. And I am interested in IT governance. I intend to connect the design of IT governance with ...
-3
votes
0answers
17 views

Is it possible to Expand the RAM memory of Laptop using cloud? [on hold]

is it possible to expand the RAM memory of laptop using Cloud??? if yes den vl it be harmful to laptop??
3
votes
1answer
23 views

Why there's a single accepting state in G-NFA's?

It's clear that we can only have a single start state in G-NFA's but I would like to know why we can't have more than one accepting state in G-NFA's.I think it's better to have more accepting states ...
0
votes
0answers
9 views

Need help on implementation of MoSIFT algorithm in OpenCV [on hold]

I'm trying to do a Violence detection in a video based on the paper by Long Xu et al. "Violent video detection based on MoSIFT feature and sparse coding" and I want to know if there has been an ...
-3
votes
0answers
9 views

How can I access a local file using Papa Parse and google chrome? [on hold]

I have a big csv file that I am trying to access and parse using Papa Parse. My works when I use a string but what I want the code to do is to access a file on my machine and parse it. My code is: ...
1
vote
1answer
40 views

What are differences between Static Scope and Dynamic Scope?

My teacher has provided the following pseudo-code, and says that the output using static scope is 1 2 3, but the output using dynamic scope is ...
4
votes
0answers
35 views

Algorithm to optimize polling frequency between producer and consumer

I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo: Problem Statement: Suppose there are 3 ...
1
vote
1answer
67 views

Showing undecidability

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the ...
0
votes
0answers
10 views

Sigma scaling problems [migrated]

I'm developing an evolutionary genetic algorithm for which I am to use sigma scaling in order to scale the fitness evaluation of the individuals before selecting mates. Sigma scaling of fitness for ...

15 30 50 per page