# All Questions

42,733 questions
Filter by
Sorted by
Tagged with
10 views

### Data Preprocessing pipeline and saving as a pickle file [closed]

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

### Reusability of neural network architecture

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

### Meaning of "approximation within $n^{1−\epsilon}$"

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 ...
1k views

### Find shortest path between two vertices that uses at most one negative edge

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

### Shamos algorithm , cannot understand the Area part

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

### modify dfs to find longest path

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

### Linear having two different connotations?

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

### Haskell family tree questions [closed]

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

### Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}

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

### Constraint Satisfaction Constraints Transformation

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

### Time complexity of assignment problem arbitrarily vs with repetition

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

### Can Operating system allocate a page of process to any free frame in memory?

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

### Solve recurrence where the base case's time complexity is a function of the original input size

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

### What are some good strategies to test a floating point arithmetic implementation for double numbers?

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

### Why proofs of Cook's Theorem assume k is given (n^k for NTM)?

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

### Searching for sorting algorithm taking into account all possible solution of similar numbers

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

### Closest pairs of points with conquer without divide approach

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

### FO-Logic: Two theories in the same complexity class can always be reduced to each other in polynomial space and time

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

### Is arithmetic/constants code optimization a function of the Language/Compiler/CPU/ALU/OS and what languages implement such features in itself?

Take the following case ...
16 views

### Triangular matrices in Prolog [closed]

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

### How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

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

### Handwritten sources of first inventors

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

### Maximal edge weight clique of given size

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

### Proving set of register machines that halt before k steps for some input is non-recursive

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

### Compute intersection points of n circles

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

...
55 views

11 views

### Convert nested Schemas of SQL Columns to Hierarchical naming representation [closed]

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

### recurrence equation 2T(n-4) + n^2 solution?

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 ]