All Questions

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 (/...

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 ...

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 ...

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, ...

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 ...

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

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 ...

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 ...

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 ...

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 ...

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 ...

$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 ...

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 ...

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 ...

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 ...

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 ...

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$ ...

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 ...

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}...

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,...

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 ...

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 ...

How does Howard's algorithm avoids re-mapping of the non-critical nodes ?

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, ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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$ ...

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 ...

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 ...

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....

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...