# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

8,824 questions
Filter by
Sorted by
Tagged with
9 views

### Logarithmic Time — O(log n) in Python

Hi , I am new to Data Structure and trying to get some clarifications. Following shows an example Logarithmic Time — O(log n) in Python. ...
20 views

### Multipilcation table

we have this program: n = int(input('give n: ')) for i in range(n): for j in range(n): print(f'{i*n + j + 1:2}', end=' ') print() and we are supposed to changed it so that it prints 3 tables next to ...
6 views

### Competitive algorithm to solve a scheduling problem to minimize truncated gaps

Time is discrete. There are $m$ time-slots. There are $n$ jobs and one machine of budget $B$. If job $i$ is scheduled at time-slot $t$, then it will consume $c_i(t)$ units of the budget $B$. If job $i$...
15 views

### How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...
7 views

### How do you prove that this tree path calculation function works, from first principles mathematically?

I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
12 views

### DAG decomposition, similar for one for series-parallel graphs

Let's consider directed acyclic graphs (DAGs) with single source and single sink. Such graphs can be combined with two operations, used in Series-Parallel graphs - parallel composition $P$ and series ...
21 views

### Asymptotic runtime of recursive algorithm uisng subsitution method

I need to solve this question using the substitution method: $T(n) = 3T(n/2)+2n$ if $n>1$ otherwise, $T(n) = 1$ Note: $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$ $$a^{\log_b n} = n^{\log_b a}$$ ...
12 views

### Various implementations of adjacency list representation of a Graph

Just started learning about graph and it's various representations (matrix and adjacency list). Now I found that the adjacency list representation can be implemented in various ways: Array of arrays (...
36 views

### Oriented undirected edges in directed graph

I have a graph with $n$ vertices and $m$ edges. Some edges are already oriented, some are not. How do I determine how to orient all undirected edges so that each vertex has the same outgoing and ...
39 views

### Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set ...
51 views

### How can I compute logarithm when comparison is undecidable?

In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively: ...
18 views

### Non-Interactive Zero Knowledge Proofs: zk-snarks and zk-stark

I read up on an abstract example of ZKPs (the cave and the door), but I'm trying to understand NIZKs (specifically zk-snarks and zk-stark). All the examples I can find online seem to have some ...
18 views

### Algorithm to mapping given probabilities to empirical probabilities

Consider following problem statement: You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
51 views

...
427 views

### Why does the time hierarchy theorem use a rather intricate diagonal argument?

Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$? Where ...
25 views

### Сyclic routes in the table

In a $n × m$ table, some cells are locked. How to determinate time whether it is possible to split the remaining cells into cyclic routes of length at least $3$? All unremoved cells must participate ...
15 views

### Can Johnson's algorithm for simple cycles be modified in order to find only cycles up to length L (but all of them)?

I have a question regarding Johnson’s algorithm for finding all simple cycles in a graph. I was wondering it is possible to modify the algorithm in order to find only cycles up to a given length. ...
178 views

### The same outgoing and incoming degree in graph

I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same ...
44 views

### Bipartite maximum matching with added constraints

Suppose you have two lists as follows List $A$ = $(a_1, a_2, ..., a_m)$ List $B$ = $(b_1, b_2, ..., b_n)$ Each element in list $A$ can be paired with many or no elements in list $B$. I have a function ...
43 views

### Converting Decimal Numbers between 0 and 1 to Binary

I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater ...
26 views

### “what does the 1 to 10 mean?” FOR number ← 1 TO 10

"what does the to 10 mean?" FOR number ← 1 TO 10
50 views

### Are some algorithms inherently recursive?

Are some algorithms inherently recursive? As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise. I am asking because I struggled to ...
22 views

### Probability of false positive for lookup in hashtable

I am going over Mikkel Thorups notes on hashing, as revision, and I came to the following exercise that i cannot see how to tackle (even initially - I know this is not ideal for a question.)  \...
41 views

### 3SAT and directed graph

Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
25 views

### Minimize range of distances between two sets of points

I have two sets of n points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets A ...
51 views

### Knapsack Problem with Constraints on Item Values

Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight ...
111 views
+100

### How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
21 views

### algorithms and the sequencing of numbers given a value

The numbers in the table below are the result of executing an algorithm that has one parameter $n$, a non-negative integer, and produces sequences of integers as outputs. For values of $n$ from 0 to 5,...
18 views

### How to write a method that takes two int parameters and return a string? [closed]

How do I write a method that takes two int parameters, a and b, and returns a String in the form a=q*b+r where q is the quotient from division and r is the remainder? Also how do I write a method that ...
29 views

21 views

### proof non-empty AVL tree

The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor. The root is not considered an single child. let mark in numOnly a number of vertices ...
57 views

### Find list of tickets with best price sum

I have an optimization problem, where i need to find set of tickets for certain period, such that sum of prices for these tickets is minimal. Algo should accepts list of trips and list of tickets as ...
18 views

### Are there any dynamic programming algorithms that combine solutions to sub-problems in a more 'dynamic' way?

First of all, I now know that 'dynamic' has nothing to do with the dynamism of a dynamic programming algorithm. But I didn't before I studied them, and I was kind of disappointed that they all seem to ...
103 views

### How to detect “tree-able” set-families?

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
52 views

### Finding certain elements when only able to ask in chunks

I have a set of $n$ elements. Of these elements $b\ll n$ are blue and $r=n-b$ are red. I want to find all blue elements. My only way to discriminate between red and blue objects is by asking a ...
22 views

### Lowest complexity - Number closest to 0

I'm currently trying to improve my algorithm skills and I was trying a simple algorithm : Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his ...
179 views

### Game on the graph with matchings

The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move ...
67 views

### Longest common sub-sequences with a condition

A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length....