All Questions

I have been working on a data science model building. I want to understand that, how can I create a working data preprocessing pipeline in python for a single pickle file to save transformer data. The ...

I have created a neural network architecture by considering the data for one study area. Have performed grid-search to tune almost all the hyperparameters of the model. I want to use the same network ...

I am not sure I understand correctly the following assertion (source): For all $\epsilon > 0$, approximating the chromatic number within $n^{1−\epsilon}$ is NP-hard. Does this mean that, for any ...

Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$: Describe an ...

I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia: ...

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...

When we discuss data structures, linear typically means that we can iterate through the data sequentially. For example, a linked list or array can fall into this category while a binary search tree is ...

it is a Haskell question down in the picture and I have no idea on how to solve this

I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...

In constraint Satisfaction, there are implicit constraints which is a single variable and explicit constraints which are multiple variables. I have found a way to transform an explicit constraint into ...

what is the difference between the worst case time complexity of assignment problem using Hungarian method arbitrarily: choose only one optimal solution (is polynomial time)and with repetition: choose ...

Consider I have a user program of 6 pages and 4 byte page size. Now my memory has 300 frames out of which 10 frames are free for allocation. Can the OS allocate page 1 of the given process to any of ...

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...

For IEEE, the single representation is 1-bit sign, 8-bit exponent and 23-bit mantissa. This means that at each exponent value, you can test all 2^23-1 (roughly 9mil cases) possible combination of ...

A typical proof of Cook-Levin's Theorem proceeds like this: Suppose problem X is in NP. Then there is an NTM M deciding X in time n^k, for some k. Given a word w, NTM M, and k, we construct a Boolean ...

I need a reference for sorting algorithm where all possible orders are considered. example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...

In an algorithm where I have to search for the pair of points in a plain, with the smallest distance: suppose that we want to use a "Divide and Conquer" approach. Is it possible to make it ...

I am currently studying CS and came across a question in my lecture. Question: Two theories in the same complexity class can always be reduced to each other in polynomial space and time. This is part ...

Take the following case ...

I am trying to write a program that identifies lower triangular matrices. I am quite new to Prolog and i would like your assistance on this. Considering a matrix as a list of lists, where each list is ...

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...

When I was undergrad student, wondering how the inventor of the algorithm thinks like that. What was he/she writing out/drafting on papers/boards? I still cannot throw the thougt out the window, even ...

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...

Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as: $$ f(n) = \begin{cases} 1 & \exists m \text{ such ...

Let $S$ be a set of $n$ circles in the plane. I need to describe a algorithm which computes all the intersection points of the circles. The algorithm should run in $O((n + k)\log n)$ time, where $k$ ...

...

We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W_1(e) &...

I'm trying to implement Trees in agda as follows: ...

consider the following question from this link. How it possible to slove this question with finding largest path in Dircted Acyclic graph?

Is the 3-SAT problem with $s$ variables and $t$ clauses FPT, parameterized by $s+t$, or W[1]-hard, or para-NP-hard?

Is there an efficient algorithm to solve the following decision problem? Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of ...

Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...

I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...

I have a game about drone delivery company. The game consists of a rectangular map, which contains tiles that cannot be passed. I can control a certain amount of drones, each one of them starts at a ...

I'm having a hard time understanding how to solve this problem for my Computer Science 101 class. On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a ...

My idea of the program is : Input = n sets objective function ObjFn equals to O(n^3) Output = the order of n sets Steps: Applying ObjFn to all n sets Choose the n of the Minimum ObjFn to be ordered ...

I was trying to solve a discrete math question regarding the comparison needed by a merge-sort algorithm. I wanted to ask if there were a more formal way to put organize my reasoning for this problem ...

Let $a,b,c,d,e,f$ be integers selected from the set $\{1,2,\cdots, 100\}$ uniformly and at random with replacement. Let $M=a+2b+4c+8d+16e+32f$. What is the expected value of the remainder when $M$ is ...

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells ...

Hello i have a piece of code like this: ...

I am learning computational complexity and parameter complexity. In order to proof that a problem is np-hard, we should reduction one which is np-hard to the problem. However, I don't have any idea ...

In a talk by Tony Hoare, he said something interesting and I'm looking for more reading on the topic minute 57: "Languages don't recognize the different structuring principles that are being ...

So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...

Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap? ...

So I was going through the exercises in the 'Kurose and Ross' book. Suppose users share a 2 Mbps link. Also, suppose each user transmits continuously at 1 Mbps when transmitting, but each user ...

Suppose we are given a tree $T=(V,E)$ where $|V|=10$. Now, one of the vertices is goal and we want to find it. The structure of the tree is given as input, but which vertex is the goal is unknown. In ...

Information: In SQL (e.g. Presto/Hive), there exists columns of "Complex" type {ARRAY, STRUCT, MAP} which are higher level structures on top of the basic INTEGER, BOOLEAN, DOUBLE, STRING, ...

need help solving this equation. the general equation I end up with: 2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]

Given a problem A is NP-Hard and A ≤𝑝 B, is there a way to prove that B is also NP-Hard?

I am a novice when it comes to computer science. But I know that traditional quantum computers are not non deterministic Turing machines. But it seems to me that the principles of quantum mechanics ...