/r/algorithms

Photograph via snooOG

Computer Science for Computer Scientists

Computer Science for Computer Scientists

Smokey says: avoid streaming video to fight climate change! [see more tips]

Note: this subreddit is not for homework advice. Requests for assistance with coursework may be removed.

Other subreddits you may like:

Does this sidebar need an addition or correction? Tell me here

/r/algorithms

102,754 Subscribers

4

what algorithm is best for this

'The player starts at the location labelled “S” and wants to reach the finish, labelled “F”. Each
turn they choose one of the four cardinal directions to move. However, except for S and F the
floor is covered in frictionless ice, so they will keep sliding in the chosen direction until they
hit the wall surrounding the area, or one of the rocks (labelled “0”).'

.....0...S
....0.....
0.....0..0
...0....0.
.F......0.
.0........
.......0..
.0.0..0..0
0.........
.00.....0

I was going ahead with a* but due to the fact that we have to turn only after hitting the block, i'm getting confused now.

solution to this

  1. Start at (10,1)

  2. Move left to (7,1)

  3. Move down to (7,2)

  4. Move left to (6,2)

  5. Move down to (6,10)

  6. Move right to (8,10)

  7. Move up to (8,8)

  8. Move right to (9,8)

  9. Move up to (9,6)

  10. Move left to (3,6)

  11. Move up to (3,1)

  12. Move left to (1,1)

  13. Move down to (1,2)

  14. Move right to (4,2)

  15. Move down to (4,3)

  16. Move left to (2,3)

  17. Move down to (2,5)

  18. Done!

10 Comments
2024/04/22
11:13 UTC

0

Given 2 numbers X and Y, want to find largest value of P such that (X mod 2^P) = (Y mod 2^P)

this is to be done on large dataset by a computer so most efficient possible please

Simple and inefficient algorithm would be (pseudocode):

function greatest_common_power_2_mod(int X, int Y) -> int{
  int P = 1;
  loop{
    if ((X mod 2^P) != (Y mod 2^P)){
      return (P-1);
    }
    P++;
  }
}

but i expect there is more efficient way to check this?

6 Comments
2024/04/21
17:31 UTC

0

Jeff Erickson Chapter 11 Exercise Question 10

Please provide the accurate solution of the Below problem Statement Based on Netwrok Flow.

Suppose we are given a set of boxes, each specified by its height, width, and depth in centimeters.

All three side lengths of each box lie strictly between 10cm and 20cm. As you should expect, one

box can be placed inside another if the smaller box can be rotated so that its height, width, and

depth are respectively smaller than the height, width, and depth of the larger box. Boxes can be

nested recursively. Call a box is visible if it is not inside another box.

Describe and analyze an algorithm to nest the boxes so that the number of visible boxes is as

small as possible.

2 Comments
2024/04/20
12:32 UTC

1

Reducing A to B in polynomial time.

Im starting to sort of understand this but if B were know to be NP-Complete would that prove anything about A? I know that it doesn't prove A to be NP-Complete but could I say that A is at least NP-Hard for sure?

7 Comments
2024/04/20
04:36 UTC

1

Pathing/Travelling Salesman Problem for Risk AI.

Hey guys! I'm coding an AI for Risk: Global dominations which is a popular online implementation of the board game Risk. I'll be writing a symbolic AI which will manually calculate paths for capturing territories and bonuses. Currently I have been stuck on finding a method to find the paths which the AI should take to capture a territory bonus (pics if you are unfamiliar with the game).

I am intending to represent the board as a graph, with nodes representing territories (and their troop/player data) and edges representing the connections between these territories. Examples of the AI pathing to take territories would be this position for the green agent to take Europe, and this position for the pink agent to take Asia. In this problem, we can have multiple starting stacks, with the goal to travel to all unoccupied territories and preferably end with the troops on external border territories to guard from invasion. Note that I am only looking for ways to find these paths from multiple starting points, not the evaluation of them. Also note that each territory can only be visited once, but as shown in the pink agent example, one territory can make multiple attacks off the same territory, it just cannot be recaptured.

Algorithms to achieve this, tips on board representation and fields of study covering similar problems would all be greatly appreciated! Cheers.

2 Comments
2024/04/20
04:45 UTC

5

Algorithm to Efficiently Search a Solution Space

I'm looking for advice on how to efficiently search a solution space under certain conditions.

The solution space is a multidimensional array of positive integers. At each point in the array I run a function that either fails or passes. Importantly, if the function passes at a point, then every point "under" it will also pass and doesn't need to be tested.

To illustrate, a 2D example would be an array of X and Y where X is 0 - 10 and Y is 0 - 15. If the point (2,3) passes then I know that (2,2), (2,1), (2,0), (1,3), (1,2), (1,1), (1,0), (0,3), (0,2) (0,1), (0,0) will also pass. Each of those points is "under" (2,3) in the sense that each element is less than or equal to it. There can be multiple “outer” pass points - for example, (1,5) could be a pass point in addition to (2,3).

Any advice is greatly appreciated, thank you!

8 Comments
2024/04/20
04:39 UTC

0

Algorithm to combine multiple tables with varying row counts

So I'm creating an application (using Excel VBA) to ingest a text file with a bunch of test results and present them in a spreadsheet in a more useful format. The text file consists of multiple log files combined, each with the same set of parameters, tested over multiple temperatures.

  • 1st pass divides it up into "groups", and creates a table for each log file
  • 2nd pass then takes the tables and lays them out side by side for comparison

My problem is that while each table has the same set of parameters (rows), if a test should fail for example, when it moves to the next temperature (column), the results continue on the next row as well. Not sure if that makes sense but basically the tables have the same # of parameters, but different # of rows...

So I need to compare all of the tables to each other, row by row, and if one has a value where another has a blank cell, I need to insert a blank row to match so that in the end they all have the same number of rows and each parameter lines up with its corresponding data. I created a visual aid to help better illustrate but cant seem to add it to this post.

I came up with a fix on another similar project, but it's terribly inefficient and this seems to me like a problem that has likely been solved already using some algorithm somewhere.

Looking for any suggestions/ideas on how I should approach this problem as efficiently as possible.

Thanks in advance

1 Comment
2024/04/20
02:42 UTC

0

Accelerate MOCUS Algorithm for DataFrames processing

I'm working on a project that involves implementing the MOCUS (Method for Obtaining Cut Sets) algorithm using Apache Spark and DataFrames. The MOCUS algorithm is used in fault tree analysis to generate minimal cut sets, which are the smallest combinations of basic events that can cause the top event to occur. I came across a helpful video lecture that explains the MOCUS algorithm and demonstrates the matrix method to retrieve minimum cut sets. I'm wondering if it's feasible to translate this algorithm to work with Spark DataFrames, or if it's simply not well-suited for this framework.

Here's a snippet of the code I have so far:

from pyspark.sql import SparkSession
from pyspark.sql.types import ArrayType, StringType, StructType, StructField
from pyspark.sql.functions import col, explode, array, when, lit, array_union, array_except

# Define the schema for the dataframe
schema = StructType([
    StructField("id", StringType(), nullable=False),
    StructField("gate", StringType(), nullable=False),
    StructField("children", ArrayType(StringType()), nullable=False)
])

# Create the dataframe
data = [
    ("TOP", "And", ["E1", "E2"]),
    ("E1", "Or", ["A", "E3"]),
    ("E2", "Or", ["C", "E4"]),
    ("E3", "Or", ["B", "C"]),
    ("E4", "And", ["A", "B"])
#     ("A", "Basic", []),
#     ("B", "Basic", []),
#     ("C", "Basic", []),
]

# spark = SparkSession.builder.getOrCreate()
df = spark.createDataFrame(data, schema).alias("events")

exploded_df = df.select(df.id, df.gate, df.children, explode(df.children).alias("child")).alias("exploded")
display(exploded_df)
joined_child_gates_df = exploded_df.join(df, col("events.id") == exploded_df.child, "left")\
.select("exploded.id", "exploded.gate", "exploded.children", "exploded.child", col("events.gate").alias("child_gate"))
display(joined_child_gates_df)

For the example provided, the minimum cut sets are [['C'], ['A', 'B']].

I also came across this paper with the best efficient algorithm.

Any insights, suggestions, or examples would be greatly appreciated. Is this a feasible approach, or should I consider a different strategy for implementing MOCUS with Spark?

0 Comments
2024/04/19
15:12 UTC

1

Continuous convolution?

I have a system that handles signal processing of relatively sparse timewise signals, eg a single scalar sample every 20ms or so. I want support convolution that given the historic samples and last sample of two signals, outputs a single scalar value.

Does it mean that my output is simply, for two signals f and g with N samples:

Σ_{m=0…N} f[N-m]g[m]

Or am I missing something crucial here?

5 Comments
2024/04/19
15:12 UTC

1

A problem related to intervals.

Can someone help me reason about this problem?

I came across this problem in an online assessment and it's been giving me sleepless nights because I can't figure out how to do it even days later. The problem:

There's a conference happening from time 0 to time 't'. There's only one meeting room at the conference and there are presentations scheduled for this meeting room. The ith presentation starts at S[i] and ends at F[i]. No presentations overlap. The times when there are no presentations scheduled are free for the attendees to network. You're given a number 'k' which is the maximum number of presentations you can move around (maintaining that they don't overlap). You need to find the largest free time for networking by moving at most 'k' presentations around.

I don't remember the examples I saw but let me know if the question needs more clarifying.

7 Comments
2024/04/18
10:33 UTC

0

Algorithm for measuring how addictive something is?

Is there an algorithm to measure how addictive something is? I don’t want to reinvent the wheel if it’s already out there. I’m expecting that I can’t get YouTube/Facebook/Tick Tock, ad nauseum(?) to release their algorithms

5 Comments
2024/04/18
03:20 UTC

0

The maximum amount of edges within a graph is `n(n-n)/2`. Am I understanding how this function is derived correctly?

The maximum amount of edges within a graph is n(n-n)/2. How do you derive this function?

I could intuit this simply by drawing it out

A graph with 4 vertices and 6 edges:

O----O
|\  /|
|  x |
|/  \|
O----O

I see that 4(4-3)/2 = 6

My guess is that:

  • n
    • amount of vertices
  • (n - 1)
    • this comes from the minimum amount of edges per vertex
  • /2
    • Each vertex has a pairwise relationship with another vertex resulting in a duplicate
    • the divde by 2 eliminates the duplicate
9 Comments
2024/04/18
02:29 UTC

0

How to identify if the problem can be solved with merge sort algorithm

1 Comment
2024/04/17
23:34 UTC

1

Kruskal's Help!

hello! i have a question relating to kruskal's algorithm in relation to MSTs. i am trying to implement it right now but i keep getting this strange result where there are numerous components which are connected but the graph as a whole is not connected and is hence, not an MST. the code is pretty lengthy so i'll leave it below. any ideas on where i might have gone wrong?

import java.util.*;

public class TSPGraph implements IApproximateTSP {

    //class for Edges as i choose to use Kruskal's algorithm
    private class Edge implements Comparable<Edge> {
        int source;
        int destination;
        double weight;

        public Edge(int source, int destination, double weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }

        u/Override
        public int compareTo(Edge e) {
            return Double.compare(this.weight, e.weight);
        }
    }

    private class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int item) {
            if (parent[item] != item) {
                // path compression
                parent[item] = find(parent[item]);
            }
            return parent[item];
        }

        public void union(int a, int b) {
            while (parent[a] != a) a = parent[a];
            while (parent[b] != b) b = parent[b];

            if (rank[a] > rank[b]) {
                parent[b] = a;
                rank[a] = rank[b] + rank[a];
            } else {
                parent[a] = b;
                rank[b] = rank[b] + rank[a];
            }
        }
    }

    u/Override
    public void MST(TSPMap map) {
        int numVertices = map.getCount();
        UnionFind unionFind = new UnionFind(numVertices);

        ArrayList<Edge> arr = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            for (int j = i + 1; j < numVertices; j++) {
                double weight = map.pointDistance(i, j);
                arr.add(new Edge(i, j, weight));

            }
        }

        arr.sort(Comparator.comparingDouble(e -> e.weight));
        int mstEdges = 0;

        for (Edge edge : arr) {
            int root1 = unionFind.find(edge.source);
            int root2 = unionFind.find(edge.destination);

            // if the roots are different, add the edge to the MST.
            if (root1 != root2) {
                map.setLink(edge.source, edge.destination, false);
                map.setLink(edge.destination, edge.source, false);

                unionFind.union(root1, root2);

            }
        }

        map.redraw();
    }  
0 Comments
2024/04/17
18:46 UTC

1

Algorithm to search for constraint-satisfying solution efficiently

**MUST SEE EMBEDDED IMAGES TO UNDERSTAND**

I need to create an algorithm to crop an image into a 1:1 ratio while satisfying the following conditions:
(All required Like photo dimensions and eye and head positions are already calculated and given as input)

  1. The Head Height Percentage Should Be 50-69% of the total photo height

For Example, if the head height is 500px. If we choose 50% as the Head Height Percentage the image should be cropped to include an additional 500px of height So the head can be 50% of the total height (1000px).
Image
(The Head Height Percentage Controls the scale of the crop box 50% head height percentage: Largest Box 69% head height percentage: Smallest Box)
Image 2. The Eye Level Height Should Be 56-69% of the total photo height
For Example, If we choose 60% as the eye level height percentage and the total height (from the previous step) came out to be 1000px then the height from the eye level to the bottom of the crop is 600px the image should be cropped to include an additional 400px of height above the eye So the total height is 1000px
(The Eye Level Height Percentage Controls The Y position of the crop box)
Image

The solution (crop box) (1:1 ratio) needs to satisfy these conditions while not exceeding the original image's dimensions and not be less than 600x600 in resolution
Image

I have tried brute forcing every Head Height Percentage value with every Eye Level Height value until one combination fits within the image's dimensions boundaries.
it worked but it is not efficient and it's a bottleneck in the process. I need an efficient solution.

1 Comment
2024/04/17
08:09 UTC

0

Applications of (uniform) spanning trees

Hi!

For a class that I'm taking, I need to apply or extend Wilson's paper on generating random spanning trees. A lot of what I see online are maze generators that use Wilson's algorithm, I wonder if there are any other applications that I could explore.

1 Comment
2024/04/16
15:41 UTC

0

Count of range sum

0 Comments
2024/04/16
18:42 UTC

0

How would I improve this sorting algorithm, and how do I find the average time complexity?

Not sure if this is the right sub, but I'm trying to improve a sorting algorithm I made, and find the average time complexity. Python pseudocode below:

def boochin_sort(arr):
  n = length of arr 
  while not sorted:
    bigger = [] 
    smaller = [] 
    for i in range(1, n): 
      if arr[i] > arr[i-1]: 
      append arr[i] to bigger 
    else: 
      append arr[i] to smaller 
    append arr[0] to smaller 
    arr = smaller + bigger 
  return arr

Worst case: O(n^(2))
Best case: O(n)
Average case: ???

It's not very fast, and it grows quadratically, but I enjoyed making it. Any improvements welcome! (Also first time writing pseudocode, sorry.)

6 Comments
2024/04/16
07:39 UTC

0

Looking for a better algorithm to sort trending items.

I am looking for an algorithm to sort by trending with each item having 2 factors. Hypothetically lets say, we have multiple buttons, and for each button you have 2 values: interactions and subscriptions. How would I sort the buttons by trending?

I thought about using zscore with different weight on interactions and subscriptions, but I am wondering if I can do better.

0 Comments
2024/04/15
21:26 UTC

1

Looking for an algorithm that determines the machinability of a certain 3d part

Not sure if this is the right place to ask. I have a project where I need to generate 3d geometries and determine its heat conductivity (the easy part) and if it is machinable. Since there will be too many parts to check, I will need some kind of algorithm to do that for me.

8 Comments
2024/04/15
15:35 UTC

2

Mental Models or Visualizations to help with programming?

My brother told me he thinks of heaps as “magic box that gives me minimum of maximum of things” and he visualises trees for binary trees. I have aphantasia so I didn’t know people could visualise things, how do all of you visualise computer science concepts or data structures and algorithms?

4 Comments
2024/04/14
17:12 UTC

0

Pareto set, skyline,"The maxima of a point set"

HI,

I have a task that involves finding a Pareto set in a group of data I have, for example there are some vectors and from these vectors I have to find the Pareto set. I'm new to the game, learning some C.

I see there are so many algorithms that do this, but I really don't understand how they work. I don't want the solution, I just want to know how they work.

please help.

9 Comments
2024/04/13
17:38 UTC

6

Given a point in the 3D brain and areas to avoid, find a path to drill through the brain to get to that point.

The specific context for this problem is placement of electrodes in the brain.

You know the specific point where you want to place the electrode in the brain, and assume you know where "danger areas" are (i.e. blood vessels, breathing, consciousness, speech). You want to drill a straight line from the surface of the skull to that point while avoiding danger areas maximally. You also want to penalize longer lines because you want to drill through as little brain as possible.

Assume the brain is a 3D matrix (you may also pretend it is a spherical shape), and "danger areas" are sets of points within the 3D matrix. The line you drill needs to be a straight line.

How can I solve this?

I can tell that it seems like an optimization problem where you want to maximize distance from danger areas, and that a good first guess would probably just be the shortest path to the given point, but I'm not sure how to approach this.

22 Comments
2024/04/12
18:19 UTC

1

But what is an algorithm?

An algorithm (/ˈælɡərɪðəm/ ⓘ) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

Wikipedia - Merriam-Webster Online Dictionary.

Speaking of how I would maybe like to think: a morphism[0] between two computational structures[1], or a system of morphisms between a number of computational structures that converge to an "output"/target resulting in the completion of a computation. And because this motivates me to define what "Computation" is and in this sense, can I say that the morphism of structures is in fact what Computation is?

Also, Computation is an empirical demonstration of ideas. Maybe labeling the subject of computation under "Ideas" is a bit too ambiguous.

Anyway, I want to come to my question. I was reading a book concerning a state automata machine for parsing grammar of let's say, a programming language. My uncle's son who is a professional programmer asked me what I was reading. I referred him to a block of text containing pseudo-code. "Look! This is the algorithm of the parsing mechanism", I said. "This is not the algorithm, but rather the implementation of the algorithm" he replied. It sounded a bit absurd to me, "if this is the implementation of the algorithm, then where is the real algorithm, I can't see it anywhere in the book".

Up until that point, I thought, an algorithm can only exist in terms of pseudo-code, as pseudo-code is almost a plain English expression of your algorithmic ideas. However, it is not the plain English record of the mechanism of an algorithm. Maybe the true representation of an algorithm is right to exist in a paragraph of plain English?

Then mathematical ideas exist in functions, equations, identities, theorems etc. All of these are a domain of math lingo. There has to be something similar in terms of computational ideas. [ Computer Lingo if you can call it ]. I thought pseudo-language IS the computer lingo. Where have I gone wrong?

So, where does an algorithm exist? Can we have a concrete record of an algorithm? Just like a concrete record of Ideas introduces the need of a language. But an algorithm written in a language is an implementation of the algorithm, not the algorithm itself? Is a written text of an idea an implementation of the idea, but not the idea itself. I would like your input on this question.

[0]: I don't know if I'm using category theory, I guess I'm not (probably). A morphism can constitute one of X_{n+1} = A(X_n). Or maybe, X_{n+k} = [A(X_{n - (k - 1)}), B(X_{n - (k - 2)}),..., Z(X_n))]. It presupposes k length seed.

[1]: I don't think there exists a term for "Computational structure" or if this is even accurate to term it like that. But a computational structure is not a data structure. Computational structure defines the evolution of a data structure (namely the contents) with respect to time. You can think of a data structure as space, however a computational structure is spacetime.

2 Comments
2024/04/11
19:21 UTC

1

I don't know if I'm too stupid, but I don't know how to solve this problem

Hello everyone, I'm trying to solve a problem and I don't know how to do it, if anyone could help me solve it with some tip or algorithm I would be extremely grateful. The problem is the following:

I need to collect a specific key list. Keys can be obtained by opening a door. Doors can be opened with one or more keys. I need to return the possible paths to obtain the keys and the keys that were obtained on the path. When I can't return when I can't get a specific key, I must return the reason.

It would be something like this:

const doors = [
  {
    door: 1,
    openWith: ["a", "b"],
    obtain: ["c"],
  },
  {
    door: 2,
    openWith: ["e"],
    obtain: ["f", "g"],
  },
  {
    door: 3,
    openWith: ["a", "c"],
    obtain: ["d", "e"],
  },
  {
    door: 4,
    openWith: ["a", "c"],
    obtain: ["f", "g"],
  },
  {
    door: 5,
    openWith: ["x"],
    obtain: ["y"],
  },
  {
    door: 6,
    openWith: ["a", "z"],
    obtain: ["y"],
  },
];

const want = ["f", "g"];
const initialKeys = ["a", "b"];
getKeys(want, initialKeys);
/**
 * Output: {
 *  success: [
 *      "to get: ['f','g'] you need to open: '1 -> 3 -> 2' and you  will end up with the following keys: ['a', 'b', 'c', 'd', 'e', 'f', 'g']",
 *      "to get: ['f','g'] you need to open: '1 -> 4' and you  will end up with the following keys: ['a', 'b', 'c', 'f', 'g']"
 *  ]
 * }
 */
const want = ["y", "f"];
const initialKeys = ["a", "b"];
getKeys(want, initialKeys);
/**
 * Output: {
 *  success: [
 *      "to get: ['f'] you need to open: '1 -> 3 -> 2' and you  will end up with the following keys: ['a', 'b', 'c', 'd', 'e', 'f', 'g']",
 *      "to get: ['f'] you need to open: '1 -> 4' and you will end up with the following keys: ['a', 'b', 'c', 'f', 'g']"
 *  ],
 *  errors: [
 *      "failed to get: ['y'] through door 5 because you need to provide the following keys: ['x']",
 *      "failed to get: ['y'] through door 6 because you need to provide the following keys: ['z']",
 *  ]
 * ]
 *
 */
0 Comments
2024/04/10
23:24 UTC

4

First principles!!

What are some learning resources that teach everything from scratch or like from first principles, very basics!? The resources you found helpful or will reccomend others.

22 Comments
2024/04/09
11:52 UTC

0

How can I optimize this algorithm to find holes in polygons?

Hi,

I made an algorithm but its pretty slow and I have a feeling it can be faster.

https://github.com/garma83/public-playground/blob/master/polygon\_hierarchy/merge\_exterior\_interiors.py

I have a list of polygons, which is the result of a contour tracing operation in a tif-image. The task is to find out which polygons are actually holes in other polygons. This is a recursive problem, so the hole might contain an island, which then might contain a hole etc. However in the end result the islands can be separate entities.

The end result should be a list of exterior polygons, with their holes in a list of interiors

- The polygons are guaranteed to be valid (non-self-intersecting)

- Holes also guaranteed to be fully contained within their exteriors (so no overlaps)

What I have so far: The algorithm loops over every polygon to find out if it is part of some other polygon. If it isn't it's an external polygon. After that it finds every polygon that is contained in the found external polygon and puts it into a list of interiors. The next step is then to figure out which interiors are direct holes, and which ones are part of islands. the former is added to the polygon, the latter is fed to the algorithm recursively, to be added separately to the output.

I'm also happy with python optimisations (Im not super experienced in Python)

2 Comments
2024/04/09
08:42 UTC

2

Simple and effective algorithm for constant state detection in time series

Hello,

some years ago I've published an article Simple and effective algorithm for constant state
detection in time series.

abstract:

The article introduces simple and effective algorithm for constant state detection in time series. The algorithm, based on sliding window of variable length, searches a sections of time series with at least some given minimal length, that have difference between maximal and minimal value in the section less than some given value. It is shown that the computational complexity of aforementioned algorithm is O(N log N ), where N is the length of time series.

Article is here.

13 Comments
2024/04/09
01:50 UTC

0

Having difficulties understanding some details in the quicksort algorithm

I am trying to understand quicksort implementation from the hackerrank's video here: https://www.youtube.com/watch?v=SLauY6PpjW4&ab_channel=HackerRank

In general I do understand the quicksort algorithm, the code structure and principles of this particular implementation (there are many variations but I found this one to be straightforward and maybe the easiest to remember).

But devil is in details that I fail to wrap my head around. In particular why are some comparisons done with `less than` and `greater than` rather than `less than or equal to` and `greater than or equal to` and vice versa. Also why do I return `i` index from the partition function and not the other index that goes backward. I commented these lines in code below where I asked my self these things.

There is not much explanation in the video why these things are is done in this way so maybe someone can help me get some intuition behind them. I'd rather have a sound logical reasoning in my head than having to remember which index to return from the partition function and which if statements comparison should be `strictly less/greater` vs. `less/greater than or equal to`.

```

def quicksort(arr, start, end):
  if end > start:
    pivot = arr[(start + end) // 2]   # why floor and not ceiling
    index = partition(arr, start, end, pivot)
    quicksort(arr, start, index - 1)  # why index-1 and not index
    quicksort(arr, index, end)        # why index and not index+1
  return arr

# returns index at which array is separated into two subarrays
def partition(arr, start, end, pivot):
  i = start
  j = end

  while i <= j:                     # why <= and not strictly <
    while arr[i] < pivot: i +=1     # why strictly > and not >=
    while arr[j] > pivot: j -=1     # why strictly < and not <=
    if i <= j:
      tmp = arr[i]
      arr[i] = arr[j]
      arr[j] = tmp
      i += 1
      j -= 1
  return i                          # why return i and not return j


def print_quicksort_result(arr):
  print(quicksort(arr, 0, len(arr) - 1))

print("\n--- quicksort, pivot at middle:")
print_quicksort_result([2,1])
print_quicksort_result([3,2,1])
print_quicksort_result([2,3,1])
print_quicksort_result([4,2,3,1])
print_quicksort_result([8, 10, 5, 7, 3,1, 2, 4, 3, 9, 6])

```

The original code in video is in c++ and this is my Python version. You can copy/paste to your code editor and test it to confirm it works as expected.

I played around trying to understand how thing works, eg. I tried to return `j` instead of `i` from the partition function, and then change parameter in recursive calls like this:

```

    quicksort(arr, start, index)
    quicksort(arr, index+1, end)
```

but it fails to work (either array out of bound or recursive stack overflow error happens).

Any help in improving my reasoning behind these details is greatly appreciated.

4 Comments
2024/04/08
16:00 UTC

0

Help with memory limit exceed

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

void detectCycle(int u, int p, vector<int>& status, vector<int>& parent, vector<vector<int>>& adjlist, vector<int> &cycles) {

if (status[u] == 2) {

return;

}

if (status[u] == 1) {

int cur = p;

cycles.push_back(cur);

while (cur != u) {

cur = parent[cur];

cycles.push_back(cur);

}

return;

}

parent[u] = p;

status[u] = 1;

for (int v : adjlist[u]) {

detectCycle(v, u, status, parent, adjlist, cycles);

}

status[u] = 2;

}

void bfs(int startNode, vector<vector<int>>& adjlist, vector<int>& vis, vector<int>& res) {

queue<int> q;

q.push(startNode);

vis[startNode] = 1;

res[startNode] = -1;

while (!q.empty()) {

int node = q.front();

q.pop();

for (int neighbor : adjlist[node]) {

if (!vis[neighbor]) {

vis[neighbor] = 1;

res[neighbor] = -1;

q.push(neighbor);

}

}

}

}

void markCycleVertex(vector<int>& res, vector<vector<int>>& adjlist, vector<int> &cycles, vector<int> &vis) {

for (int i = 0; i < cycles.size(); i++) {

for (int x : cycles) {

if (vis[x] == 0) {

bfs(x, adjlist, vis, res);

}

}

}

}

int main() {

int t;

cin >> t;

while (t--) {

int N, M;

cin >> N >> M;

vector<int> cycles;

vector<vector<int>> adjlist(N + 1);

vector<int> status(N + 1, 0);

vector<int> parent(N + 1, 0);

int n1, n2;

for (int i = 0; i < M; i++) {

cin >> n1 >> n2;

adjlist[n1].push_back(n2);

}

detectCycle(1, 0, status, parent, adjlist, cycles);

status.assign(N+1,0);

parent.assign(N+1,0);

status[1] = 1;

markCycleVertex(status, adjlist, cycles,parent);

queue<int> q;

q.push(1);

while (!q.empty()) {

int node = q.front();

q.pop();

for (auto it : adjlist[node]) {

if (status[it] == 0) {

q.push(it);

status[it] = 1;

} else if (status[it] == 1) {

status[it] = 2;

q.push(it);

}

}

}

for(int i=1;i<status.size();i++){

cout<<status[i]<<" ";

}

cout<<endl;

cycles.clear();

}

return 0;

}

I'm supposed to detect all nodes in a graph that have infinite ways to be reached. Basically if there's a cycle then all the nodes on that cycle can be reached infinitely, also all the nodes connected to such nodes will also have infinite ways. print -1 for all such nodes

Other than that if a node has finite ways then print 2, else if 1 way then 1, else if 0 then 0.

I'm encountering MLE using this algo

2 Comments
2024/04/08
18:16 UTC

Back To Top