# All Questions

41,519 questions
Filter by
Sorted by
Tagged with
15 views

### Really confused

Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this? P = NP P ⊊ NP P ≠ NP NP ⊆ P
5 views

### Efficient algorithm for finding assignable zones

This is an actual logistics problem I'm facing at work and I'd like an advice on what algorithmic approach is suitable for solving this. I have two data structures: Container and Zone defined as ...
8 views

### Applications of Complete Binary Tree?

Wondering what are the real word applications of the Complete binary trees or Almost complete binary trees where the the last level of the tree may not be complete and all nodes in the last level are ...
18 views

### Creating a database of math questions and of answers and a front end for them

Need some guidance on where to begin. I am just learning python if it has any bearing. I want to create a page on my site where users log in, choose multiple topics from a list, choose between levels ...
11 views

### recurrence with exponentials

I am trying to figure out on how to approach the problem on finding proving the asymptotic of an exponential recurrence. It is described as such: t(n)=4t(n/2)+2^n with t(1)=1 for n>=5 From what I ...
15 views

### Would all objects in a reversible computing language be mutable?

Full disclosure, I'm asking this after watching a couple pop science videos; I do not know anything about the actual physics and hardware. I suspect the presenters expected an audience like me because ...
10 views

### Loop in control flow graph of a program versus checking whether program goes into infinite loop or not

Which of these is true or false. 1)If Control Flow graph(CFG) doesn't contain any loop, the program will never go into infinite loop. 2)If CFG contains loop, the program may or may not go into ...
12 views

### Visit each node in a circular graph with most distance

A simple graph is shown below with 10 nodes. Each node is labeled after a letter in the alphabet. This is basically a circle (J connects to A). ...
22 views

### Number of stall cycles when there is only EX/MEM pipeline registers or only MEM/WB pipeline register

I am working on a problem which is related to The processor. The problem is the problem 4.12 in the book whose title is "Computer Organization and Design". The problem has the assumption as ...
17 views

### How to develop a interleaving transition system with 3 parallel programs

Up until now, Ive learnt how to design a transition system using 2 program graphs. But I am looking for researches on this approach with 3 program graphs. I cant seem to find any online resources to ...
214 views

### Runtime complexity of algorithm that subtracts progressively larger amounts

How would you describe the runtime complexity if I have an algorithm that at each step, the size of the array reduced by an exponentially-increasing amount? For example, for each step in the algorithm,...
12 views

### generalized mean distance-based k-nearest neighbor classifier - from formula to cod in Matlab or python

[ I am working on kNN algorithm, and i want to code this new type of kNN(generalized mean distance-based k-nearest neighbor classifier) algorithm in Matlab or python. please help me. best thanks
31 views

### Is my regular expression correct for this question?

IBM has decided that all sequences of numbers (such as mobile numbers) must be ordered in such a way that any mobile number is followed by at least 2 corporate numbers, and any landline number is ...
66 views

### Are parse trees are always produced?

When my instructor taught compiler construction he explained all the phases of compiler and their working nicely. But when I read online here, at last line it is written that Parse trees are not ...
35 views

### Help Understanding the Halting Problem

There are certain points about the halting problem that do not make sense to me. I couldn't seem to find a good breakdown of it that addresses my notes below. I was wondering if someone could ...
48 views

### Does more registers increase clock cycle time ? Why?

While reading a book on computer organization , i run into a design principle stating Smaller is faster, and indicating that less registers means less clock cycle ...
27 views

### Can Someone help me to find what's different between those two codes? [closed]

I have spent an hour but did not find why both of the codes giving different outputs. The problem is to colour different cities using graphs. and the inputs are: 3 2 1 2 2 3 where the first code gives ...
13 views

### Explain the use of the “sign extended” block in case of immediate data processing in 32 bits MIPS architecture with an example

My lecturer told me that when An integer register on the MIPS is 32 bits. The remaining bits must be assigned when a value is loaded from memory with fewer than 32 bits. Sign extension is used for ...
6 views

### Algorithm to pair respondents based on differences in answers to survey

I am having the following problem: I have asked a number of people 7 different binary questions. I now want to pair my respondents based on how different their answers to the questions were. The goal ...
24 views

9 views

### how do i remove nodes with their children but keep ones that are already connected?

suppose you have graph G and you want to remove node n and n and all of his children but keep the ones that are connected to other nodes if i want to delete A it will delete C but not D becase its ...
53 views

### is Turing machine the blue print for program (software) or computer (hardware)?

I often hear Turing machine is a mathematical model of computation. Sometimes, it's said to embody any computer program. Sometimes, it's said to be an idealised computing device consisting of a read/...
17 views

### Distinguish supervised learning , unsupervised learning and reinforcement learning

AlphaZero is a computer program that was originally built to master the games of chess, shogi and go. It was trained solely via "self-play", in parallel, with no access to opening books or ...
7 views

### Concurrent Simultaneous actions

Hi i am having 2 laptops with different user names but same OS & settings, files. If i open control panel and change some settings say mouse sensitivity in laptop 1, the same should happen live/...
96 views

### Question about “with high probability”

An event that occurs with high probability is one whose probability depends on a certain number $n$ and goes to $1$ as $n$ goes to infinity, i.e. it can be made as close as desired to $1$ by making $n$...
21 views

### High Level description of Turing Machines

How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
10 views

### T(n) = 4T(n/2) + n*logn using the iteration method [closed]

Solve the following recursive relation using “iterative method”. Also justify the solution using the “Master method”.
22 views

### Time Complexity of Quicksort when using Median Pivot in sorted array

I am looking for any literature or reference for the worst case complexity of using quicksort on a sorted array with median as pivot. Different internet sources give conflicting answers and often skip ...
12 views

### Turning my Optilink XONT71110N Modem into a Router [closed]

I had an Optilink Modem which used to be the modem for my G-Internet connection (Bangalore, India). I currently am using Hathway Internet Connection which covers all areas except our bedrooms. While ...
12 views

### What is the time complexity of comparing two Merkle trees?

I have a simple recursive function that compares two merkle trees and accumulates the differences in the leaf nodes. However, I am unable to measure the time complexity of it. Specifically, I would ...
28 views

### Is it possible to allow passing arguments as references without breaking referential transparency in functional languages?

Referential transparency is a relatively new concept to me, but I understood that it means that a function will always give the same answer given the same arguments. Would passing arguments by ...
11 views

### Generic real-time message/event matching engine

I'm looking for methods (any kind of combinations of algorithms & corresponding data structures) that can be used as a generic matching engine in case of arbitrary message/event types. Let me ...
16 views

### How do I find the associativity or precedence of operators/terminals to create the Operator Precedence Table from an Operator Precedence Grammar?

The initial grammar provided to me was: S->abABC/DE A->a/epsilon B->bA/epsilon C->c D->d/(E) E->e/epsilon After converting this grammar to OPG, I get: S->abaBc/abBc/De/D A->a ...
36 views

### How is “expected approximation ratio” defined in cases when the expected value of the optimal solution is known?

Consider an approximation algorithm which does better than $f(n)$, in expectation. Suppose we know that $\mathbb{E}(OPT)=g(n)$. Given that we use the convention of "larger divided by smaller"...
24 views

### Given a finite alphabet, how to generate all possible strings while excluding those that don't feature an element at least once?

Say you have the finite alphabet {a,b,c,d,e,f,g}. It's trivial to enumerate all strings of length <= 1000 over that set. But what would be an efficient way of specifying a subset of those strings ...
41 views

### How to define a formal language for describing procedural activities

I do not have a formal computer science background here so I am looking for pointers. How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing ...
26 views

### Worst case finding the goal node in a tree

Suppose given a tree with 10 nodes, we want to find vertex goal that is unknown for us. We act as follow: we pick a arbitrary vertex x, then if it goal we return it, else if it's not goal we have ...
33 views
+50

### Algorithm or solution for counting possible items within budget using HashMap and recursion?

Using Java 8, I am trying to figure out an algorithm / proper solution to see how to store a List<String> with buyable items within a certain allocated budget....
20 views

### Return electrons per shell given the atomic number of the element

Suppose you are given the atomic number of an element, ex. Technetium, which is 43. Is it possible to return array like this -> [2,8,18,13,2] which shows the distribution of electrons across ...
861 views

### recover a set with the information of the sums of all its subsets

I have a set $S$, which contains $n$ real numbers, which generically are all different. Now suppose I know all the sums of its subsets, can I recover the original set $S$? I have $2^n$ data. This is ...
24 views

### Do identical algorithm end up having the same abstract syntax tree?

More often than not, most programming problem can be solved in more than 1 way. You see this in website for practicing solving coding challenges where you often have myriad of solutions to the same ...
29 views

### What are the fixed-points of the Y combinator?

Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
35 views

### Which sorting algorithm is this?

I was trying to implement bubble sort in python, but turns out it's not bubble sort, it's faster than bubble sort. Can somebody please enlighten on me what sorting algorithm I implemented? ...
16 views

### Merge N number of euclidean distance matrices to get an overall single euclidean distance matrix

I want to find out the aggregated euclidean distance of a big dataset D comprising of x and y cordinates where the data set is divided into N sub dataset where 1st sub dataset contains 1 to kth ...
15 views

### Reference/textbook on RAM model/model of computation for algorithms

Can someone recommend a reference/textbook on the RAM model of computation? Preferably something with a concise definition and doesn't get too much into computer architecture. I'm very fine with this ...
8 views

### What are the possible algorithms behind dex aggregators?

I want to know what is the algorithm behind 1inch, paraswap, and other dex aggregators. The problem is: Imagine you want to sell a huge amount of some coin and a there are multiple brokers with ...