All Questions

Filter by
Sorted by
Tagged with
1
vote
0answers
19 views

Algorithm to find largest intersection of sets

This is a cross-posting from here, on the mathematics Stack Exchange. I thought this might be a more appropriate venue. The problem is this: I have a list of sets $$S_1, S_2,... S_N$$ where each set ...
0
votes
1answer
26 views

Can someone explain intuitively why union find works to find a cycle in an undirected graph?

I understand how the UF algorithm works to detect a cycle in an undirected graph, but I don't understand why it always works. Could someone explain that intuitively? Specifically, I don't understand ...
-1
votes
1answer
33 views

Design the finite DFA where 5 divides 2i+3j

a) For $\sum =\{0,1\}$ , design a deterministic finite automaton $M$ accepting the language $L=\{a^ib^j:i,j\ge 1, \text{5 divides (2i+3j)}\}$ b) Prove that ypur automaton exactly accepts the language ...
1
vote
0answers
52 views

Could someone explain the algorithm from this paper? (Thank you) [closed]

Trying to get a fair understanding of our artificial immune systems. To do this I’ve been reviewing this paper, but the algorithm and mathematics is over my head, could someone explain the below to me ...
-1
votes
1answer
36 views

Reduction from SAT to 3SAT

a few days ago I had a test and could not pass it. This is a question I did not understand in the test. Recall the reduction we saw $SAT \leq _p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we ...
0
votes
1answer
27 views

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$ I am trying to prove that $L$ is not in $RE$ by reduction ...
0
votes
2answers
60 views

Declarative, interrogative, imperative, and exclamative sentences in computer languages

The following English sentences have different forms (syntax): Declarative: You are my friend. Interrogative: Are you my friend? Imperative: Be my friend! Exclamative: What a good friend you are! ...
1
vote
2answers
122 views

Reduction from vertex-coloring problem to edge-coloring problem

A few days ago I had a test and could not pass it. This is a question I did not understand in the test. We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G =...
0
votes
0answers
12 views

Memory Controller Actions

Can a memory controller read from memory and send from memory simultaneously and is the main system bus involved in this reading from memory? I posted a question I still do not understand but this is ...
0
votes
0answers
24 views

Efficient algorithm to solve multiplication Diophantine equation

Consider an equations of the form: (a + x) * (b + y) - c = 0 Or: (a + x) * (b + y) = c Or: ...
2
votes
1answer
34 views

How can I prove that the empty string is the identity element with regards to the operation of concatenation?

Let $w$ be a string over an alphabet $\Sigma$. It is obvious that $w \circ \epsilon = \epsilon \circ w = w$. However I'm having a hard time coming up with a proof for that (which I assume should be ...
0
votes
1answer
16 views

What does it mean when asking to Convert 16-bit binary numbers to two 8-bit signed integers (two’s complement) in decimal

The question is Convert the following 16-bit binary numbers to two 8-bit signed integers (two’s complement) in decimal. i. 0b 0011 0110 1101 0100 I first flipped it and added 1 to it which equaled ...
0
votes
1answer
25 views

Complexity of the maximal minimum size problem

Here is a question that I do not understand: There is a list of items $E = e_1,\dots,e_m$. Suppose we have two players (the first and second). Each item $e_j$ has a value $v(e_j) \ge 0$. The values ...
1
vote
0answers
18 views

How can there be an enqueue event outside the function range of enqueue events?

I'm trying to understand Figure 1 in this theoretical description for queues: https://www.cs.bgu.ac.il/~abraham/courses/Concurrency14/2(Logic)/3.Qexample.pdf Key excerpts from the PDF: I grasp ...
1
vote
2answers
165 views

What kind of binary compatibility is present for 2 processors sharing an Instruction Set?

Consider Intel x86 and AMD x86 Processors. As I understand, since they use the same Instruction Set, in theory an application compiled for Intel x86 processor would run without any modification on ...
2
votes
1answer
25 views

What are the job names for researching neural networks & deep learning?

I am a student who wishes to research neural networks (ANN, CNN, RNN) and deep learning, write papers on those topics, and actively participate in forums like CVPR. My question is: Which professions ...
0
votes
0answers
11 views

For classifier systems, how is the genetic algorithm run on delayed class?

I am reading Signals and Boundaries and came across Classifier Systems. In the book, John Holland seems to imply that the signals in the input, as they come from a live environment, don't have an ...
1
vote
1answer
19 views

How do you prove that a solution to the 0-1 knapsack problem is optimal?

Given a boolean vector b representing a solution to the knapsack problem with n elements k capacity and where each element has integer weight and value. Proving that the solution is a solution is ...
2
votes
0answers
35 views

Finding a simple algorithm for an assignment problem

I have an assignment problem where I need to assign resources to consumers. Each consumer has a list of resources it'd like to acquire, ordered by preference, and each consumer can have at most one ...
1
vote
0answers
14 views

How to find the number of common edges in two sequences?

Lets say I have two sequences such as these: Sequence 1: A B C E D F Sequence 2: A B D F C E Both sequences contain the same set of elements and each element is unique. I want to find the number of ...
-1
votes
1answer
57 views

What's so difficult about computer verifiable proofs?

What's so hard about creating a piece of software with as minimal as possible mathematical axioms, defining a formal language in which one can create new constructs based on the existing ones, and ...
-1
votes
0answers
36 views

Why does Prim’s algorithm work?

I recently started learning Prim’s Algorithm for finding a Minimum Spanning Tree for a connected graph. However, I am having a problem understanding why the algorithm will indeed produce a MST every ...
1
vote
1answer
20 views

SAT formula for connected graphs on the grid

In the answer to an earlier question "SAT algorithm for determining if a graph is disjoint" a formula is constructed that is satisfiable iff a given graph is connected. The formula uses a ...
0
votes
1answer
26 views

How many /20-subnets are in the network 130.149.0.0/16?

I'm new to networking so please bear with me. My textbook gives 4 as an answer, but I'm not sure I understand the question: What's a "/20-subnet"? My understanding is that a network mask (/...
0
votes
0answers
16 views

Understand what this phrase is in the Turing

I had a test a few days ago and failed it. There was a question that was not clear to me. This is the question: For the purpose of describing the drawing on the tape of a Turing machine at each step ...
0
votes
0answers
27 views

Process Response time in CPU scheduling

I'm Confused about Response time in CPU scheduling because i found different definition for it, so what is exactly the Response time ? Is it : the time between a process enters ready queue and get ...
0
votes
2answers
31 views

Complexity of `n & (n - 1)` should be O(1) or O(log n)?

I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether n is a power of 2. Method 5, ...
0
votes
1answer
26 views

How to know if language is in comp or np?

I'm new to the site. I had a test a few days ago and failed it, I had a question I did not understand. This is the question: Let's look at the FALSE language: Collect all the verses P in the form of ...
0
votes
0answers
14 views

Bus Bandwidth Calculations

I cannot understand this question and the model answer for it and I wonder if anyone here is able to help me. Question: ...
0
votes
1answer
18 views

Nearest neighbor algorithm for TSP when triangle inequality holds

The output given by this nearest neighbor algorithm for the Travelling Salesman Problem can be arbitrarily bad. In the example constructed here, the triangle inequality doesn't hold in most cases. Let ...
1
vote
1answer
23 views

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges. I ...
0
votes
1answer
22 views

comparision based sorting algorithms

The book CLRS says that any comparision sort algorithm requires omega(nlgn) comparisions n the worst case. My question is that why for heapsort it's O(nlgn) not omega(nlgn) since heapsort is also a ...
0
votes
1answer
27 views

Can the “closest neighbor” algorithm get arbitrarily bad in TSP?

Let's consider the following simple algorithm for attacking the Travelling Salesman Problem: Choose the pair of cities $(A,B)$ where $A\neq B$ and the distance between $A, B$ is minimal amongst all ...
1
vote
1answer
38 views

SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
0
votes
1answer
48 views

What is the complexity of computing $C(n + m, m)$?

$C$ here represents combinations. $$ C(n + m, m) = \frac{(n + m)!}{n! m!} = \frac{(n + m) * (n + m - 1) * \ldots * (n + 1)}{m!} $$ In this formula it looks like it's $O(m)$ because both the numerator ...
0
votes
0answers
17 views

Minimum weight $k-$path cover on a DAG proof verification

Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
2
votes
1answer
28 views

What is the nature of the two bits of data held in a computer memory cell?

I hope this question doesn't offend anyone. I start off by saying that I have and always had difficulty understand the language used in computer science so I have to interpret everything into the ...
-3
votes
1answer
44 views

Designing a context free grammar for a language

Design a grammar for the language $$F = \{x^a y^b zx^b y^a\mid a, b\geq 1\}$$ I'm trying to get a stronger grasp of designing grammars for languages. A thorough explanation of how to design the ...
0
votes
0answers
34 views

What is the name of this data structure?

I am trying to solve a problem efficiently. The problem is to recurse over a set $\{0,1,\dots,n-1\}$ (as array) in ascending or descending order, while removing or re-adding items in $O(1)$ time. A ...
0
votes
0answers
79 views

Proving that a problem is not FPT using reduction

In the Inclusive Vertex Cover problem, For a given graph $G=(V,E)$, each vertex $u\in V(G)$ has weight $u_{w} \in \mathbb{N}$ and value $u_{v}\in \mathbb{N}$. The value and weight of a set cover $S$ ...
2
votes
1answer
53 views

Merging all adjacent and overlapping rectangles in a grid to bigger rectangles

I have a 𝑛×𝑚 rectangular grid of cells, and a set 𝑅 of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where ...
0
votes
1answer
100 views

How to determine the approximation factor for greedy vertex cover algorithm?

The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $0$ are left. Formally: $\text{GreedyVertexCover}...
1
vote
0answers
29 views

Is weighted interval scheduling where the weights are the interval lengths simpler/faster

In weighted interval scheduling arbitrary weights are given to the intervals. A clean dynamic programming solution runs in $O(n \log n)$ time. If the weights of the intervals are their integer lengths,...
1
vote
1answer
34 views

Why this problem is NP-Hard?

I'm asking about the question described here: Knapsack Problem with exact required item number constraint Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check ...
0
votes
1answer
28 views

Understanding the complexity class of a problem formulation

I'll keep the reasoning abstract. If I start from a mathematical formulation of a problem $A$ known to be $NP$-hard, I add a set of constraints which creates a problem $A'$. However, I do know that ...
0
votes
0answers
12 views

Mechanism of Howard's algorithm

How does Howard's algorithm avoids re-mapping of the non-critical nodes ?
0
votes
1answer
29 views

Is this way to combine two functions into a new function called a function product?

I have been looking for a maths operation that allows me to combine functions in a specific way. For example if we have functions f and g both with single mappings from o to e and v to c respectively, ...
0
votes
0answers
28 views

Self Organizing List vs Hash Table Preformance

I am wondering what the advantages and disadvantages of a self organizing list are over hash tables. Also, does a self organizing list run faster with a memory access pattern, but the memory access ...
0
votes
3answers
33 views

Mutual Friends in a Network?

I always seem to have trouble finding a formal way to analyze this (be through proofs or whatever). The problem statement is as such: If A and B are friends, and B and C are friends, then A and C are ...
1
vote
0answers
37 views

Puzzled by this interview problem of scheduling a computation graph on a single-processor under a memory constraint

I recently went through a interview session for a SWE/CS role at a well known company. It wasn't specifically a "coding-round" but was titled a "domain interview" session, so I ...

15 30 50 per page
1
3 4
5
6 7
831