Questions tagged [python]

Programming questions are off-topic here. Do not ask questions about how to write code in Python. However, conceptual questions about computer science are more appropriate. See our help center for the scope of this site.

219 questions
Filter by
Sorted by
Tagged with
4k views

Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks? [closed]

Python quite famously uses indentation to syntactically define blocks of code. (See Compound statements in the Python Language Reference). After years of using Python I'm still intrigued by and very ...
• 257
3k views

Does an algorithm's space complexity include input?

Consider the Kadane's algorithm for finding maximum subarray within an array: ...
6k views

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$. def is_equal(a: int, b: int) -> bool: return a == b <...
38k views

Time complexity of min() and max() on a list of constant size?

If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?
• 145
11k views

What is the expected time complexity of checking equality of two arbitrary strings?

The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters. So far so good. I think we can all agree that ...
2k views

Space complexity for storing integers in Python

So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point. The question that the ...
753 views

What are the fundamentals of calculating space complexity in loops?

Imagine you loop n times, and every iteration you create a string of space n with scope only within that iteration (thus it is no longer accessible in the next iteration). I would look and say that I ...
202 views

Warnsdorff's rule: more errors with odd sized boards

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
• 167
162 views

Why does parallelising slow down this simple problem against looping through all the data?

I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn ...
• 205
1k views

Find 1s in almost all 0 array using comparisons only

So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python): ...
810 views

Number of Inversions found in Selection sort vs Exchange sort

Exchange sort is similar to selection sort, just swaps "overly eagerly" instead of finding the minimum and doing only one swap. And the swaps affect how often the ...
• 480
188 views

Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order. I believe that I understood the three terms pretty well, and ...
• 189
191 views

Python versus Matlab on the quantity 1/0

Python and Matlab seem to disagree on the division by 0. Python: ...
• 133
68 views

How does numpy.linalg.inv calculate the inverse of a matrix?

What is the algorithm behind this routine and is there documentation available for it?
112 views

What's the runtime complexity of this algorithm for breaking up string into words?

I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
527 views

Understanding Applicative Evaluation Order with the Z-Combinator

I am trying to understand how the Z-combinator (Y-combinator for applicative order languages) definition came about. As Python is applicative I am using Python for this. So I know Python's evaluation ...
• 295
348 views

Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?

I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it. Python starts from the end of the array to the start. Looking at the algorithm I didn't see any ...
• 131
976 views

How to use Latin hypercube sampling with fixed points?

I use Latin hypercube sampling to select what point to evaluate my function. As evaluations take a lot of time, I want to limit the time by adding already evaluated points. I thought about taking the ...
• 131
39 views

Subtype Check with Type DAG

Trying to understand how compiler/static-type-checker checks for subtyping, I run into 2 problems. 1. Reachability in DAG Since both Python/C++ support multiple inheriatnce, the types can be ...
• 131
648 views

Doubt about computing running time / time complexity of a function in Python

I am learning about time complexity now, and I am working with BST (Binary Search Trees). This question needs some context and this is a follow up post to this post. Basically, I would like to compute ...
• 189
623 views

“Converting” networkx / osmnx graph to a planar graph

I am currently working on some analyses of the Berlin road network, and I am using OSMNX to get a relevant graph representation. I noticed that - if with drawbacks - many authors use planar ...
• 123
72 views

Complexity of iterative exponentiation

I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it: The following function calculates $x^n$ ...
279 views

Why is this n^2 growth?

I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading: "... performs of the order of $n^2$ steps on a sequence of length $n$....
175 views

Repeated addition and comparisons of floating point numbers

In the following program where I repeatedly half an integer, it takes until i = 1074 for my integer to be equal to zero (I know that ideally the while loop shouldn'...
322 views

Compute hash value according to multiplication method

In "Introduction to Algorithms" by C. E. Leiserson, R. L. Rivest and C. Stein (ISBN: 978-0262033848), p. 264 they state this: I get everything but the last part stating $h(k) = 67$ ...
• 123
450 views

How can I optimize 3 variables in order to maximize the end product?

I am in the process of making a cryptocurrency trading bot. Currently, I am doing backtesting over a period of 7 months in which I provide a portion of historical data as if it were in real-life. By ...
86 views

Repeated Substring Pattern

I've been working on the following challenge on LeetCode: Problem: Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together....
• 123
64 views

Which approach of mine for an algorithm upper bound is correct?

Say we have this algorithm in Python. ...
604 views

Why does python's threading library use OS level threads when it can't achieve parallelism?

I was surprised to hear that the threading module from python uses OS level threads. From what I know, OS level threads are more expensive (but can achieve parallelism) meanwhile green threads are ...
• 121
150 views

Why is KMP preprocessing O(N)?

My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from ...
• 21
364 views

Lambda Calculus Conversion

How can I take a Haskell data type or function (eg fold, list, String, zip) and convert or translate it to a lambda calculus abstraction? Example: If sum computes a sum of all elements in a list, and :...
3k views

Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
• 123
581 views

(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

The following question is taken from Leetcode entitled 'Combination Sum' Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
• 169
846 views

Minimum cost node cut

I am interested in solving the following problem: Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph. Is there ...
• 23
102 views

What is the practical use of list.clear() method in Python?

I was wondering if there is a reason behind clearing all the values in a list and reusing it, as opposed to deleting the list and creating a new one. Are there any practical advantages of using ...
123 views

Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical

My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. ...
• 123
3k views

Finding the area of a rectangle in python [closed]

Q: Standard input consists of exactly four integers, first x1 and y1, the coordinates of the bottom-left corner of a rectangle, then x2 and y2, the coordinates of the top-right corner. Write a Python ...
174 views

"Visited" vs "Seen" Positions in Breadth-First Search

I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid. In ...
754 views

Conditional Shortest Path Through Weighted Cyclic Directed Graph

Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge ...
• 121
32 views

Fast calculations using fast-Fourier convolution

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$. We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
• 151
41 views

What is an algorithm to do this binary image segmantation task?

What I need to do is go from a binary image like this: to a segmented structure like this: because I have a program that operates on those separated line contours after. As you see, those contours ...
130 views

How to calculate delta Q (modularity increase matrix) in graphs?

I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in ...
139 views

How do you write a python\pseudo code that generates all pair permutations?

What would be a good pseudo code or Python 3 code for the following permutations problem? Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\}$ and ...
• 21
65 views

Reducing Kleene's predecessor for Church numerals

I am trying to "reinvent" Kleene's predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. ...
• 1,101
79 views

Consider vectorization and for loop, do both approaches have the same time complexity?

I am learning this post Fast computation of nearest neighbors is an active area of research in machine learning. The most naive neighbor search implementation involves the brute-force computation ...
392 views

On teaching Kolmogorov complexity with Python and the complexity of composed strings

The setting of this question is a bit long-winded, but please bear with me. This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing ...
• 121
1k views

Knapsack problem in real life

My task is to develop an algorithm for the optimal arrangement of cylindrical objects in cartons. The algorithm is to have the task of placing as many products as possible into cartons, at the same ...
• 121
1 vote
211 views

Why does Python allow stand-alone expressions?

In Python, this is a valid program def PrintWorld(): print('World') print('Hello') 0 'beautiful' True None 0 < 0 3, 3 lambda c:3 PrintWorld() All it does ...
1 vote
Is the complexity of this two-sum binary search algorithm $O(\lg n)$ or $O((\lg n)^2)$?
This algorithm solves the Two-Sum problem$^1$ assuming that the input array/list is sorted. ...