All Questions

Filter by
Sorted by
Tagged with
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
34 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
56 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
34 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
18 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
25 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
25 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
30 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
47 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
43 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
52 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
99 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
27 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 ...
2
votes
1answer
24 views

Finding an optimal solution in a tile painting game

The Problem Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal solution, just find one of them. Game Rules The game level is made up ...
0
votes
0answers
26 views

Recursive formula for cardinality of table size

In a data migration task (similar to ETL), data is migrated from table A on server X in database Y (legacy database) to server Z (modern data base) in server p. This is just a copy transformation ...
0
votes
0answers
24 views

Is the name 'class' from 'Complexity class' came from ZF set theory?

I just want to know if people in the complexity initiated the name 'class' because the term 'class' in Zermelo-Fraenkel set theory or not? For me, I assume the answer is Yes; because it doesn't seem ...
2
votes
1answer
17 views

Finding an unknown point on an infinite number line

Given a number line from $-\infty$ to $\infty$, there exists a point $P$ on the line. We need to find the minimum number of steps to get to $P$ subject to the following constraints: The value of $P$ ...
1
vote
0answers
25 views

Modified Kruskal's Algorithm

I have a connected graph, each vertex has a cost. I want to slice the graph into as many components as possible, but each component should have a cost (sum of costs of vertices) at least C. I think it ...
4
votes
3answers
306 views

Clarification on the algorithm for finding a majority element

Here's a question about using a divide and conquer approach to find a majority element in an array. It's taken from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Question 2.23. I'm ...
0
votes
2answers
33 views

In what stage is next PC address available or known to the processor?

Assuming you know the meaning of pipelining in Computer architecture & organization. When is the next PC address or jump address available or known to the processor? In this lecture, https://youtu....
0
votes
1answer
26 views

When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?

This seems to be my first ever question :) Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that. I don't ...
5
votes
1answer
77 views

Find all $k$ such that $X_1+kY_1,\ldots,X_n+kY_n$ are all equivalent modulo $M$

Let $n, M$ be integers. Given two arrays $X$ and $Y$ of $n$ elements. For each $i \leq n$, we define arithmetic progression $X[i] + kY[i] \pmod M$, where $0 \leq k \leq M$. Find all $k$ such that for ...
0
votes
0answers
32 views

How is segmentation a solution to external fragmentation

As per Galvin's book, segmentation is the solution to external fragmentation. But in segmentation, the memory blocks are of different sizes. So, if one segment is removed that creates a hole. If we ...
1
vote
1answer
24 views

M does not accept [M] | 'Correction' of proof possible?

The language $D=\{[M]|M([M])=0\}$ is not decidable because of the following argument: Suppose there was a $TM \space M_D$ that decides $D$. Then if we gave $M_D \space [M] $, there would be two ...
3
votes
1answer
29 views

Show that $P^A \neq EXP^A$ for all oracles A

I knew that $P \neq EXP$ by Time Hierarchy Theorem. But, I'd like to show that $P^A \neq EXP^A$ for all oracles A. How can I do it? I knew that If I make A=EXP, PSPACE, NP, and many others, then this ...
3
votes
1answer
18 views

What is the primary reference for the observation/discussion of how neural networks struggle with ambiguous training datasets?

It is known that neural networks, such as convolutional neural networks, struggle with pattern recognition if training sets contain ambiguities (i.e. several labels can correspond to one and the same ...
2
votes
2answers
85 views

Satisfiable CNFs where each clause contains logarithmically many different literals

Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability. A side note before, to be more clear: A CNF clause consists of $n$ clauses ...
3
votes
1answer
30 views

Sum of squares of length of longest common prefix for all pairs in given strings

Given a list of unique strings, how can I find the sum of squares of longest common prefixes length for all pairs? I think a trie will be useful but I'm not sure how to calculate the final result. For ...

15 30 50 per page