All Questions

Filter by
Sorted by
Tagged with
-1
votes
1answer
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
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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). ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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,...
-1
votes
0answers
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
0
votes
0answers
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
24 views

A relaxation-free variant of Dijkstra's shortest path algorithm

I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
2
votes
1answer
41 views

Showing NP is closed under intersection

I was solving the following question: Show that $L_1 \cap L_2 \in \mathrm{NP}$ for $L_1,L_2 \in \mathrm{NP}$. I came a cross this solution on the internet which is: $M$: On input $w$ — Run $M_1$ ...
1
vote
1answer
32 views

Interpreting = in aymptotic notation

We can interpret $f(n) + o(f(n)) = \Theta(f(n))$ as for any $g(n) \in o(f(n))$ there exists some $h(n) \in \Theta(f(n))$ such that $f(n) + g(n) = h(n)$. But can we perceive it as for any $g(n) \in \...
0
votes
1answer
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 ...
0
votes
2answers
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/...
0
votes
1answer
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 ...
0
votes
0answers
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/...
3
votes
2answers
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$...
-1
votes
1answer
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 ...
-1
votes
0answers
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”.
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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"...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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....
0
votes
0answers
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 ...
13
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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.
0
votes
0answers
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? ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
26 views

I Need learning videos for hardware [closed]

I want to learn computer hardware any idea where I can learn it? I mean hardware course for free
0
votes
0answers
19 views

In shortest-path graph, for the unique path $p= ⟨v_0=s,v_1,..,v_k ⟩$ why do we have $d[v_i] \geq d[v_{i-1}] + w(v_{i-1},v_i)$ for $i=1,2,..k$?

I was going through the CLRS [2e] text where I faced some difficulty in an expression used in the proof. The excerpt from the text is given partially below to explain the context. The expression where ...

15 30 50 per page
1
2 3 4 5
831