All Questions

Planar graphs are graphs which can be drawn on the plane without edges crossing. Disk contact graphs are graphs obtained as follows. Place some disks in the plane without overlaps, allowing touching. ...

I have a lot of difficulty with the turing machines. I understand the theory well, but I need help with a lab exercise... Design a SINGLE TAPE Turing Machine that accepts the language $a = > b \...

GeeksForGeeks We are given an array arr of $n$ element. We need to count number of non-empty subsequences such that these individual subsequences have same values of bitwise AND, OR and XOR. For ...

I am preparing for Bank PO exams and I require some guidance about books which contain topics like MS Office, Network Systems(Star ,Bus etc.) and also computer history(generations and all). I would ...

I want an algorithm that takes a list of strings $X = \{ x_1, \dots, x_n\}$ over an alphabet $\Sigma$, and determines the smallest templating of the strings, where by templating I mean a string ...

According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?). So, two problems may ...

A) 32bit word size B) 3GHz clock speed I think should be (A).2^32 instruction at one time ?

I do not understand how Merkle tree can be used to efficiently verify data in a peer to peer, distributed network like IPFS. I mean I understand how the merkle tree is constructed: basically take a ...

We know that maximum clique and minimum Steiner tree are NP-hard. I am trying to come up with a reduction from clique to Steiner tree. However, I have no idea, can anyone help me?

The arithmetic logic unit, ALU, is where the computation takes place in a CPU, and the rest is registers and control unit. I have a hard time understanding how ALU would increase in proportion to the ...

I would like to discuss with you please the following problem and it's solution. Setup: We are travelling with the following constraints: You can only drive in the daytime. On any given day, you can ...

I wish there were more, but the subject pretty much captures my whole question. Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...

We all know that the RUN Time of most of our program are Big O of linear time, quadratic time, cubic time or log time. But Can this be in unusual or uncommon poly time like $x^6-y$ or cosine function ...

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset. ...

What algorithm can be used to find a balanced edge in a binary tree? If we remove that particular edge, the tree is split up nearly equally. Each tree will have at most $ \ceil{(2n-1)/3}$

Are there any methods for computing the "similarity" between two algorithms? Intuitively, selection sort and merge sort are more similar to each other than merge sort and radix sort. I want ...

I'm new here on the site, I'm a final year student in computer science. In a machine learning course, there was a question on a test that I could not understand. The question goes like this: Suppose ...

I want to predict as many time steps of a variable (X) as possible. The more time steps forecasted, the more successful the solution proposed. To the best of my knowledge, applying LSTM neural ...

In this paper by Azar and Epstein in Section 4 they consider online strip packing of rectangles without rotation in a setting where when a rectangle arrives it has to be lowered monotonically ...

Supercomputing is faced with the power wall challenge where the design of more powerful supercomputers has to ensure that their eventual operation is power efficient enough to be economically viable. ...

Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step ...

I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$: Set a PL. I chose $p=2$ Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...

Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2. We are looking for the shortest path between a node from group 0 to group k-1 (path ...

Given a 3SAT problem with the additional constraints that: No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses. For any/every clause, the ...

The Professor has given us a Assignment and Has asked us to tell the axiom that is used to define the semantics of the semantic network of one Particular example, the issue is I have no Idea what ...

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ? Can ...

This is my homework question Given an array A[1..n] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that A[i] + A[j] = α for a given value α. Give an O(n^2) ...

Question: Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...

I was reading distributed algorithms (by Nancy lynch) and there is a part that I would kindly like to get a simpler explanation for. I know the book mentioned no algorithm can solve mutual exclusion ...

Is $\{a^{2n} b^{3n} \mid n \ge 0\}$ a context-free language? Also. I need to prove that $\{a^s b^t \mid s=t^2, s,t \ge 0\}$ is non-regular using the pumping lemma, and that $\{a^s b^t \mid s \neq t^2, ...

If we represent a heap using array the 2nd half of the array will be represent the leaf nodes of the heap. But I can not understand for array of length n, all elements in range A[[n/2+1]....n] are ...

Question: Describe an efficient algorithm that, given a set $\{x1, \cdots, x_n\}$ of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given ...

Can there be a computer without software (only hardware) which can produce meaningful output? "Software" would be for example an operating system (whether in the level of "firmware&...

My question I have two complexity classes, $L$ and $Mod_kL$. I'm confident these classes satisfy $L\subsetneq Mod_kL$, as I'll explain below but you can take for granted for a moment. From these two ...

Description: In this work you will have to design the logic and implement the code in python language in order to display (real time) information about the weather in five areas of Greece: Athens, ...

How to find a saddle point in a binary tree. where saddle point is a node in a tree whose value = min(the node and all its ancestors) = max ( the node and all its descendants)

I am looking to prove the following: Each binary tree with $n \ge 2$ nodes has an edge whose removal results in two trees, each having at most $\lceil (2n-1)/3 \rceil$ nodes. I am not sure how to ...

I am quite confused by this slide from a course I found on the internet from UCL on Graphical Models. Here is the slide: I would like to confirm whether I have correct understanding: In the following ...

Convert the following while loop into a for loop. Your code should be written so that the return statement does not need to be altered. You are allowed to change the code before the while loop proper. ...

I am trying to solve a variant of the traveling salesman problem. In this variant, the nodes have a state which is required to go in order. Specifically, first is order food, second is give food, and ...

I have seen the stochastic introduction of simulated "entities" (typically queuing for service) via stochastic inter-arrival times. Specifically, the times between arrivals are simulated ...

So I came across this question and I would like to know if I am on the right track,if not I would like it if someone could give me tips on how to approach the following problem. "You have a ...

I just read this Why doesn't Python need a compiler? I know that Python isn't absolutely compiler or interpreted but it is both of them it's maybe an interpretive, high-level, and all-purpose ...

I'm currently trying to train a custom model with tensorflow to detect 17 landmarks/keypoints on each of 2 hands shown in an image (fingertips, first knuckles, bottom knuckles, wrist, and palm), for ...

Without restriction (e.g. continuity or convexity are not guaranteed), we're given an W x H raster-based shape that needs to be placed on an infinite tiling of <...

I recently learned about the one-way 2-party model of communication complexity in some lecture notes. It seems that all algorithms studied in this model are either deterministic or randomized Monte ...

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...

I have acknowledged that the $\epsilon$-greedy algorithm does exploration and exploitation with probability $1-\epsilon$ and $\epsilon$. Is there a way to simply express the expected total reward $\...

I am wondering why the following "proof" of $coNP = NP$ does not work: $\subseteq:$Let $L$ be a language in $coNP$, that means there is a non-deterministic Turing Machine $M$ that decides ...

I have recently read the definition of $coNP := \{L \ \mid \ \overline{L} \in P\}$, where $L$ denotes a language. However, I am wondering what the difference between $P$ and $coNP$ is, since an ...