algos-and-data-structs

[dark aurora]

so the main func goes

for i in range(1, m) :
    for j in range(1, n) :
        dp[i] [j] = min(dp[i] [j-1]+1, dp[i] [j-1]+1, dp[i-1] [j-1]+(str1[j-1]==str2[i-1]

why does it still work on most cases if i put n+1 and m+1 instead of n, m shoulsn't I get an error

and why does it not work in this case in particular

[trim rover]

problem is, how do I even create the tuple without making either a very long line e.g. tup = (1,2,3,4,5,6,7,etc) or adding a bunch of separate lines e.g. category = 123 tup += category or make my code more confusing by not naming these parameters and going straight to storing them in the tuple/list e.g. tup += 123?

[halcyon plank]

Hey @dark aurora!

You either uploaded a .txt file or entered a message that was too long. Please use our paste bin instead.

[trim rover]

I wish there was a way to use a dictionary for inserting to mysql. That would solve my problem most elegantly. But there does not seem to be command that turns {"category": 123, "url": 456} into (123, 456) Or is there?

EDIT: may have found answer in https://stackoverflow.com/questions/9336270/using-a-python-dict-for-a-sql-insert-statement

[haughty mountain]

so I imagined rewriting the functions to return a namedtuple and accept a namedtuple as argument in this code

[haughty mountain]

.values(), though relying on dict ordering always feels a bit iffy

namedtuple is a better fit for this imo

e.g. my_tuple(category=123, url=567)

[trim rover]

assuming the function where the variables are set goes like this:

url = 567```
how do I turn this into a named tuple?

wait, what is a namedtuple? I thought you were talking about a tuple with a name lol

let me google one sec

[haughty mountain]

my_tuple = namedtuple('my_tuple', ['category', 'url'])

it's a tuple but with named fields

so you can write

my_tuple(category=123, url=567)
```to create a tuple or
```py
existing_tuple = (123, 567)
my_tuple(*existing_tuple)
```to create from an existing tuple

[trim rover]

can i break it down to chunks? otherwise it would still create a very long line, I think

[haughty mountain]

I mean, you can always add newlines to make things more readable, e.g.

my_tuple(
  category=123,
  url=567
)

[trim rover]

nice!

[dark aurora]

https://paste.pythondiscord.com/raw/merebenova

for thos

*this

[haughty mountain]

share the full code?

[loud path]

who knows how to solve a rubik's cube

[plain fiber]

can anyone help me kadane algo?

[tame whale]

how can i calculate/code, given m and n, the amount of longest path (except in cases like 2x2, essentially all positions must be visited) solutions to traverse from the top left to the bottom right of that grid with dimensions m x n?

[haughty mountain]

seems like this but on a general grid and not a square grid http://oeis.org/A121788

[tame whale]

i don’t really understand what that means

[fiery cosmos]

can y'all read the problems in CLRS and start dreaming up solutions? i feel like most of them i read and I'm completely in the dark on even where to begin. is this normal?

[plain fiber]

what is CLRS

[fiery cosmos]

https://en.wikipedia.org/wiki/Introduction_to_Algorithms

[fluid gate]

can someone tell me why solution A results in 40 but solution B results in 59 for [4,-2,-3,4,1]. It's driving me crazy because they are functionally IDENTICAL!! Question here https://leetcode.com/problems/sum-of-subarray-ranges/

Solution A

        sum = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                sum += (max(nums[i], nums[j]) - min(nums[i], nums[j]))
        
        return sum

Solution B

        res = 0
        for i in range(len(nums)):
            minVal = nums[i]
            maxVal = nums[i]
            for j in range(i, len(nums)):
                minVal = min(minVal, nums[j])
                maxVal = max(maxVal, nums[j])
                res += maxVal - minVal
        return res

[fiery cosmos]

basically like the bible for algorithms

[plain fiber]

god a book

[fiery cosmos]

its over 1200 pages

[fiery cosmos]

still dont know what to make of this line in the pseudocode

[tacit nova]

https://leetcode.com/problems/rotate-image/

this is the ENTIRE solution, i want to ask what is that A[:] doing ?

class Solution:
    def rotate(self, A):
        A[:] = zip(*A[::-1])

[haughty mountain]

if you reverse the rows and transpose, it ends up being a 90 degree rotation, A[::-1] reverses, the zip is a transpose

the assignment to A[:] is to replace the entire slice of A

to assign A in-place

[haughty mountain]

they aren't identical, B keeps track of the prefix maximum/minimum as it goes, A does the max/min of adjacent values

this change should make them identical, though this is a lot slower

        sum = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                sum += max(nums[i:j+1]) - min(nums[i:j+1])
        
        return sum

[tacit nova]

i see they are in-place with A[:], thank you

[haughty mountain]

it's just a set union, python has a built in set you can use

in fact return {a[m]} | recursivecall(...) is valid python

(although not optimal performance-wise)

this is a better option for performance

s = recursivecall(...)
s.add(a[m])
return s

[fiery cosmos]

hmm

i'm used to seeing { } in dictionary notation. ok thanks

[haughty mountain]

dicts and sets are very similar

one gotcha is that the empty set is set()

because {} is a dict

[fiery cosmos]

is time complexity synonymous with lines of code executed

or rather is it approximately equal to

this question comes from the cover files of a given script and my exercise yesterday where i added up all the lines executed by randomized quicksort to see how it runs compared with the expected running time

and it was more than expected for a given input, but as another user pointed out, thats bc i neglected to take into account the constant in the theta notation

and some small constant like 5 could easily upper bound the lines executed for the given input of one input array of n=1000 elements

i think im understanding it correctly unless there is some deeper layer of like computations that the code is doing that i cannot see with a cover file, and that those computations are what is meant by time complexity

[haughty mountain]

in reality different cpu instructions take different amount of time

[fluid gate]

Omg thank you so much

[haughty mountain]

when analyzing algorithms you assume that there is some set of operations that take constant time, and work from there

[fiery cosmos]

so would it be in error for me to work from the cover file and show that the expected runtime is consistent with the number of lines executed for a given input n?

like for example, randomized quicksort is O(nlgn). my version ran and executed 43k lines. for my given input of an array of n=1000 integers, 1000*lg(1000) = 9,965. so while it took more lines (computations?) than expected, this is easily upper bounded by say, c of 5, and so it is indeed true that randomized quicksort if O(nlgn)

this is a legitimate analysis i think unless i'm completely off base

[haughty mountain]

trying to say anything from a single data point is going to be iffy

you could run for some different n and plot the results

but if you do that, why not just plot the time taken for different n instead?

the number of operations is used as a proxy for time, when possible measuring the real deal will be more useful

[fiery cosmos]

so let say i wanted to analyze the same algorithm but with arrays of n=1000, n=10k, n=50k, n=100k. what would a rudimentary analysis be comprised of

furthermore if i were to plot the number of lines executed (after adding up all the lines from each cover file) for each, would it be helpful to ask excel to plot an equation of that line?

[opal oriole]

Plotting the n and time taken for each. Trying to create a function that matches/fits that curve / guessing the complexity. Using that guess as the goal in a proof to show that it is actually that runtime.

[fiery cosmos]

hmm makes sense ok

[opal oriole]

(You can just use whatever plotting program, desmos is fine)

Also you want multiple runs averaged.

[fiery cosmos]

so you mean multiple runs at n=1k, multiple at 10k, etc

[opal oriole]

If you run your program and it takes 10 time units the first run, 20 the second, 13 the third, etc. You just average them and plot those.

Just to deal with the randomness.

Like maybe your PC happened to be running something in the background.

[fiery cosmos]

i'm not looking at time units but the cover file and adding up all the lines executed

which i suppose could be my "time units"

[opal oriole]

Yeah ticks / time units / steps.

[fiery cosmos]

ok

im going to also track time elapsed within python, but that is secondary to the steps

./ not as important

[opal oriole]

Even real time will be fine if you just average the runs.

[fiery cosmos]

eh thats a no-no for my course

[opal oriole]

It's just to get a guess for the proof.

[fiery cosmos]

if its to guess for the proof im sure itd be fine

no-no for formal analysis

[haughty mountain]

as said, number of operations is a proxy for time, so if you can measure time why not do it directly?

[opal oriole]

The proof is the formal part. Real time is what ends up mattering in engineering / real programming (because it's the reality of how long it runs).

But whatever, courses have their ways.

[fiery cosmos]

i am measuring time directly using pythons time function but the prof said that takes backseat to operations performed / steps

[haughty mountain]

time complexity for expected growth, real time to have a baseline

real time measurements, especially in lower level languages, is quite fun

[fiery cosmos]

i've sort of lost my way in CLRS, need to get back to reading chapters. i am all over the place

[opal oriole]

Reality + prediction for further because you probably don't want to test all possible N (good luck with that :))

[haughty mountain]

you can often see where you start missing cache, because the slope for the time taken can change dramatically

[opal oriole]

In software engineer, I don't ever count steps. Just real time and proof of runtime complexity for prediction for large N.

Steps can be seen by just looking at the code, no need to actually count it with a program.

(Although it can be nice, just don't really need it in practice (except maybe some rare cases))

[fiery cosmos]

good to know

i was gonna ask whether y'all build heaps out of classes or arrays but then i remembered python has a built in heap function, so nvm

clrs seems to imply you can implement them as arrays

[opal oriole]

Arrays.

(Not in Python)

(This gets into more details about how modern machines work so I would not worry about it)

[fiery cosmos]

if y'all wanna ask me anything you think i should know going into a grad lvl algos course, i am all ears

[haughty mountain]

e.g. in a loop like

for i in range(n):
  for j in range(i+1, n):
    thing
```I know the `thing` will run like n(n-1)/2 times because math, I don't really need to count

[fiery cosmos]

im going to try to write this in summation form as practice

[opal oriole]

(You counted in the math sense of counting (combinatorics), but not by program or manually by hand)

[haughty mountain]

heapq uses lists for the heap

[haughty mountain]

lazy counting :P

[opal oriole]

Yeah efficient / more advanced counting. In math it's the branch of "counting". Which includes stuff like counting how many combinations a Rubick's cube has (without just counting each one by one manually).

(And also how many times steps in an algorithm run)

[haughty mountain]

just put the question/code here, someone might look at it

[fiery cosmos]

is this described in one summation or two

[haughty mountain]

either really, it's a nested summation of ones, or a single summation n-1 + n-2 + ...

easy enough to check with a print, no?

[fiery cosmos]

why not classes?

[haughty mountain]

shouldn't you get a python error then?

because recursion depth

[haughty mountain]

you mean defining a node class and whatever? it's generally slower

[fiery cosmos]

hmm ok

[haughty mountain]

having stuff nearby in memory is important for performance, so storing the data in an array rather than a node based structure is better

[fiery cosmos]

i guess my binary trees will be slow then

[haughty mountain]

I mean, it depends. If you're doing recursion in python you'll have a fun time in general

[fiery cosmos]

for i in range(n):
  i+=1```

[haughty mountain]

(python is at the kind of slowness where I'm not scared about cache misses)

[fiery cosmos]

did i describe that loop correctly

or maybe it'd be i = i+1?

[opal oriole]

Just to clarify and make sure we are on the same page, what do you mean by classes? I kind of made an assumption, but could you write it out?

[fiery cosmos]

class = Node:
  __init__(self, somestuff)

class = BinTree:
  __init__```

[opal oriole]

And each node has a left, right?

[fiery cosmos]

yes each node will have properties like left, right, maybe a color in the case of red black trees

[opal oriole]

Yeah, so, when you create an object in Python, it allocates memory for it. And it does so on a heap.

(Or if you did it in another language this way you would probably also have it on a heap)

[fiery cosmos]

do you mean the heaps as in CLRS heapsort algorithm?

the heap data structure?

im getting a feeling thats a different heap than the data structure

[opal oriole]

Memory pool would probably be a better term.

What matters here is that when it allocates those objects, they may not be next to each other in memory, they can be scattered all about.

[fiery cosmos]

arrays are a contiguous chunk of memory, IIUC

(in python)

[haughty mountain]

not really. besides, the loop you wrote is weird, it doesn't compute a sum, it increments the index which will be overwritten on the next iteration anyway

[opal oriole]

Yeah arrays are often contiguous chunks of memory.

[fiery cosmos]

is this correct:

i=0
for i in range(11):
    i+=1

print(i)

[opal oriole]

And the reason that matters is because of how you need to get data / memory from devices such as RAM to the CPU so it can perform work on it.

[haughty mountain]

list in python is a contiguous array of pointers, though the actual objects are stored elsewhere

[opal oriole]

If you get the first element of an array, the CPU won't get just that one element, one-by-one, because now it's bottlenecked by having to wait on each of them. By the time a single element from the array arrives at the CPU, the CPU could have sorted a small array.

(CPUs are that fast (ridiculous))

[haughty mountain]

you mean to write this, right?

s=0
for i in range(11):
    s+=1

[opal oriole]

So to help solve this issue, the CPU will fetch memory in chunks. And if you have a nice contiguous array, and it sees that you are just looping over that, it can predict what it will need next and fetch a whole bunch all at once.

If your nodes are randomly located in memory, it will have a very hard time.

[haughty mountain]

no, seems like a very greedy problem

[fiery cosmos]

it works the way i wrote it as well, but yes perhaps for clarity's sake that is better. so might i describe this loop as:

[opal oriole]

(It's jumping around)

[fiery cosmos]

ok i'm with you. the reason i implemented my binary trees as classes is bc i think thats how the pseudocode was written, in other words i don't think the pseudocode would work on a binary tree built based on an array. that or i couldn't figure out how to build one from an array

[haughty mountain]

no that's not how you write sums, my loop is s = \sum_{i=0}^{10} 1

is there a LaTeX bot here?

[fiery cosmos]

i can do it

[haughty mountain]

.latex $\sum_{i=0}^{10} 1$

[opal oriole]

Implementing them as arrays is an optimization, and does not matter as much in Python because Python is already slow. Use what you think makes it easier to understand until it becomes a problem (slowing down your program when profiling).

[haughty mountain]

I should petition enabling the latex thing here...

[opal oriole]

(For these kinds of things it's best to do the simple to understand solution until it's actually a problem)

[fiery cosmos]

i can paste this in the math server and copy here

[opal oriole]

(For a non-garbage-collected programming language it can be easier to just use the array approach (so faster and more simple to work with))

(And technically freeing your heap is now O(1) instead of O(n) (the entire heap, if you want it all gone))

[haughty mountain]

but yeah, that's

s = sum(1 for i in range(11))

or

s = 0
for i in range(11):
  s += 1

[fiery cosmos]

right right

[fiery cosmos]

i'm feeling pretty good about starting class this month until i see stuff like this

the exercises on mergesort with insertionsort once the subproblems get small enough were suprisingly intuitive

[opal oriole]

Depends on what you want to do. Many programmer have probably not made a data structure in years other than for interviews.

[fiery cosmos]

i've been practicing using substitution and master's theorem yeah

this is what i should practice up on now tbh

[opal oriole]

If you want to make new things, and not just reuse code / libraries, etc, you will probably need to be able to do it from scratch.

Then you need both the memorization and from scratch practice.

[fiery cosmos]

so what would you example then be, the n(n-1)/2 one in math notation? i'll repaste

for i in range(n):
  for j in range(i+1, n):
    thing

if you write the notation i can convert to latex

you don't need the latex command

[opal oriole]

You want both the fast pattern matching based on what you have memorized and the slower from scratch analytical ability.

It helps to write it out by hand. Play around with simple cases (base cases and near base cases) and then see how those cases relate to each other (it may be a recursive / DP thing).

[haughty mountain]

meh, I'm used enough to writing LaTeX, though this should really be in some equation environment

  \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} 1
= \sum_{i=0}^{n-1} n - (i+1)
= \frac{n (n-1)} 2

[fiery cosmos]

sorry i meant if you write the latex i can put it through and get the output

[haughty mountain]

I don't have a LaTeX environment readily available on my phone, sadly :P

[fiery cosmos]

i have access to another server where i can easily run it through quickly

[haughty mountain]

I made a request to activate it here

[opal oriole]

You would expect this channel of all channels to support latex.

[haughty mountain]

it should be fixed soon enough

[haughty mountain]

but yeah, that

[fiery cosmos]

ok perfect thank you

[haughty mountain]

for better or worse I've written enough LaTeX to read the source code as math pretty fluently

[fiery cosmos]

its certainly better for your wallet/career

[haughty mountain]

if you're not writing even things like shopping lists in LaTeX, what are you even doing?

[fiery cosmos]

im just happy i read something about a heap and knew the min or max elements would be something in the realm of 2^h nodes where h is the height of the heap

i still can't read that summation notation 🙄

maybe it doesn't matter. i just need my B

[haughty mountain]

\section{To buy}
\begin{itemize}
  \item bananas \\
  \item chocolate \\
  \item milk
\end{itemize}

[fiery cosmos]

haha

[haughty mountain]

shopping list with class

[haughty mountain]

the Σ notation overall? it's not so weird

this is all there is to it

\sum_{i=a}^b f(i) = f(a) + f(a+1) + \ldots + f(b-1) + f(b)

[haughty mountain]

it's just a shorthand to write such a long sum

[covert thorn]

i thought that \sum is the inline text style, and that \Sum was the normal style, but i guess that's not the case. apparently inline depends on context, and may or may not require \displaystyle to say otherwise

[haughty mountain]

depends if it's inline or display math, yeah

[fiery cosmos]

I’m not understanding in CLRS when they talk about an array having the aspect heapsize. I can call len(array) in Python, does there exist a similar heap(array) function?

[fiery cosmos]

How would I add a parent attribute to my binary tree based on node classes

In an array based approach I think it’d be tied to the indices

I’ll have to take a look at my code, I’m just in the book rn

[haughty mountain]

in python you let the storage be dynamic size, so len == heap-size if you use heapq

[haughty mountain]

you just store the parent, much like you would the children?

[fiery cosmos]

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

    def __repr__(self):
        return str(self.key)

class BinaryTree:
    def __init__(self, root):
        self.root = Node(root)

tree = BinaryTree(7)

def tree_insert(root, key):
    if key <= root.key:
        if root.left is not None:
            tree_insert(root.left, key)
        else:
            root.left = Node(key)
    else:
        if root.right is not None:
            tree_insert(root.right, key)
        else:
            root.right = Node(key)

looks like i'll need to add parent and child attributes to class Node

[fiery cosmos]

how again does 2((2^k)lg(2^k)) become k2^(k+1)?

-->

[lament totem]

lg(2^k) becomes k

[fiery cosmos]

that's the most i know 😂

[lament totem]

so then it becomes 2 * (k2^k)

And 2^k * 2 is 2^(k+1)

[pseudo gust]

Hello here , hope you feel good, I'm here to learn more to create apps or tools other than CRUD applications. I think about how advanced developer implement protocols in a langage for exemple ? or systems... Something different, I'm beginner and all your help or advice will be usefull

[lament totem]

Because you are just multiplying by 2 one more time than k

[fiery cosmos]

right i guess the parentheses confuse me. but we can also see that with the rule a^b * a^c = a^(b+c)

ty @lament totem one last thing

[haughty mountain]

again, lg(2^x) = x

that's all that's been used

[fiery cosmos]

wow i just realized the CLRS publishers literally posted python implementations of every algorithm on their website 🤦‍♂️

probably better i didn't know that while i was learning

i wonder if we should pin that here or if it'd be detrimental to learning purposes

[fiery cosmos]

i'm still not printing my entire sorted arrays with my return statements, if anyone may know what thats about

[haughty mountain]

what code?

[fiery cosmos]

Anything I run where the array is too large, just gets lopped off at the end of the print statement there must be a max character return in the print function

[haughty mountain]

any code example? maybe it's something with your programming setup?

[fiery cosmos]

Maybe it’s a vscode thing. I can share code when I’m back at my pc but it’s happening code agnostic

[haughty mountain]

quick googling gave me https://stackoverflow.com/questions/57764639/how-to-stop-vs-code-from-truncating-python-data-in-the-console#58203545

I wouldn't know these issues, I just work in a terminal 😛

[fiery cosmos]

hmm i'm not seeing the Data Science setting of the python extension. i'll keep looking. thanks for this

i forget why i migrated from the default IDE that ships with python but at some point i did for some reason

hmmmm

[fiery cosmos]

just realized in the beginning of CLRS they put:
(x number of instructions) / (y number of instructions/second) to get computational time. that's the formula i will follow once i get the number of instructions per second of my processor

can i look up the instructions per second for my cpu or must it be calculated

[haughty mountain]

it depends on the instruction

[fiery cosmos]

wiki says i can do it in this manner:

[haughty mountain]

why not just measure the time?

that's ultimately what you want

[fiery cosmos]

i will be doing that as well

this seems to be what i want given what i was trying to calculate before

[haughty mountain]

as always, counting instructions will at best be a bad approximation of time taken

especially if you count lines in python

if you look at individual instructions you can start to count the number of cycles needed for a sequence of operations, but it gets very complicated very quickly

[opal oriole]

IPS is a pretty bad measure of processor speed on modern machines.

[fiery cosmos]

i guess that makes sense given clrs was written 30 years ago

ok. i'm just trying to figure out how to use those lines executed in my analyses

beyond "we can see the bulk of the work is here"

finally recognized that k+1 = lg(2^(k+1)) 😂

this has been a wild ride coming from the RNA sequencing and biochem world

there are some cool dimensional analyses we do

[cobalt temple]

Hey is there a library in python that could decode iso646

[fiery cosmos]

can someone help me understand this runtime:

looks like the first summation runs from i=1 to n-1, so i understand what's written above and below, but why is it n-i

[slender sandal]

It seems both loops run n-1 times nope

[fiery cosmos]

so here they have split out the summation into the summation of n being n*(n-1) and are subtracting the i summation is it?

[haughty mountain]

it's a decent proxy for ballpark time estimates, 10^9 cheap operations in a compiled language might be ~1s

in python...a lot fewer operations in 1s

like 100x less

[fiery cosmos]

i'm sorry that i keep asking about this btw

[haughty mountain]

again, parentheses matter, I'll complain until you do it right :P

[fiery cosmos]

i know its frustrating, the summations just haven't clicked yet

[haughty mountain]

yeah, you can split a (finite) sum

Σ(a + b) = Σa + Σb

[fiery cosmos]

can anyone hop in voice? i'd love to talk through the bottom line and say "this is how i interpret this" and see if i'm comprehending things properly

[opal oriole]

The outer loop runs n-1 times. The inner runs starting from i+1 to n. So if i is 1 then it's 2 to n and if it's 2 then 3 to n. So if say it was starting at i rather than i+1 and i started at 0 rather than 1, then at most it's 0 to n, which is n. And every time i increases it's n - i.

n - 1, n - 2, n - 3, ...

(Because the range gets smaller by i going up)

(The reason I let i start at 0 is because it makes it more obvious (IMO), but it still applies when you do the i = 1 to start and all that they are doing)

When you have a summation in math, the summation not only adds stuff up, but the index (i in this case) can be used to know which iteration you are currently in, and that is important in this case because which iteration you are in affects how many iterations the inner loop does.

[fiery cosmos]

so they're capturing the entire complexity of the algo with a single summation and not mentioning the variable j used in the internal loop?

how would the summation change if the internal loop weren't present

just summation(i)?

[opal oriole]

Then it would be constant time. If no inner loop.

So sum over a constant term.

(Unless there is recursion or something)

[haughty mountain]

you could write a nested sum, but it's a boring sum over ones

[opal oriole]

Like it's it just did foo += 1 inside the loop instead of another loop or calling another function or something.

So if you had the sum from i = 1 to N for the outer loop, and inside there was no inner loop, just a single instruction, it would be the sum from i = 1 to N of 1. Or just N, because it's doing 1+1+1+... N times, which is how multiplication works (1 * N).

[haughty mountain]

.latex $1+1=2$

aww, not added yet

[fiery cosmos]

ok so it looks as if the n summation is just equal to n(n-1) and the i summation becomes equal to (n^2 - n)/2?

[haughty mountain]

the n sum is just adding n, n-1 times

that's what the sum means

[opal oriole]

In this case, the inner loop is the one being replace by N, except not exactly N, because of how i starts further and further.

[haughty mountain]

and yeah, the i sum should be familiar by now

[fiery cosmos]

i guess what's tripping me up is we aren't summing an integer or something, we're using it to mean the summation of all the lines executed, which is more abstract

[haughty mountain]

we are summing integers

[opal oriole]

You can think of it as counting the number of times the inner most lines are being executed that are O(1).

[fiery cosmos]

lines 3-7 should be O(n)?

[opal oriole]

On their own in isolation can't say, because don't know what i is.

If we assume that i = 1 or 0 (such that it's the maximum, it would be N times).

[haughty mountain]

technically true, because O is an upper bound, but it's not Θ(n)

[fiery cosmos]

can someone give me a bit of code and i'll try to write the equivalent summation which describes the loop and/or loops?

[opal oriole]

for i in range(n):
  for j in range(n):
    foo

(foo is O(1))

[jolly mortar]

if youd like to pr its just adding this channel id to https://github.com/python-discord/sir-lancebot/blob/main/bot/constants.py#L109 and https://github.com/python-discord/sir-lancebot/blob/main/bot/exts/fun/latex.py#L36 👀
although not sure if an admin/coredev already approved yet

[haughty mountain]

it's just doing Dijkstra, isn't it?

modified?

you just need Dijkstra afaict

that doesn't really change much

[fiery cosmos]

?

[opal oriole]

Remember you are counting how many times foo is executed. And foo is a single instruction (counts as 1).

How about first try this: ```py
for i in range(n):
bar

[haughty mountain]

e.g. a grid like this corresponds to the graph below

1 2
3 7

o--1--o
|     |
2     5
|     |
o--4--o

[fiery cosmos]

wait no

[haughty mountain]

idk, sounds more annoying than it's worth

[opal oriole]

And if bar counts as 1 operation?

[haughty mountain]

you binary search for the smallest distance for which the dfs reaches the goal

[fiery cosmos]

?

[haughty mountain]

though idk how that dfs would even be written, you kinda need dijkstra to get the right ordering

[opal oriole]

Yes, but finally, note that in math summations it's [,], not [,). So if you are starting at index 0, your max index is?

[fiery cosmos]

n-1

[opal oriole]

Correct, now write out the summation in ... form.

Like how you had 1+2+3+...

[haughty mountain]

wow, one of the first solutions I see in the discussions say "BFS(Dijkstra)" 🤢

BFS is not Dijkstra, different things

[opal oriole]

There is no n-1 at the end, it's always 1 inside the sum, just a bunch of 1s added together.

[opal oriole]

Try a concrete value for n, like 10. What does the sum expand to?

[fiery cosmos]

wdym expand

like what does it evaluate to?

[opal oriole]

Yeah.

[haughty mountain]

they do, but writing it like that give me like 0 confidence in the author

[fiery cosmos]

10

[opal oriole]

And how did you compute that?

[fiery cosmos]

i thought of a loop adding +1 to a variable 10 times beginning at var = 0

[opal oriole]

Which looks like: 1+1+1+1+1+1+1+1+1+1.

So sum from i = 1 to 10 is: 1+1+1+1+1+1+1+1+1+1.

But repeated addition is just multiplication.

[haughty mountain]

I'm suspect of the dfs+binary search one, I'm not convinced it works

[fiery cosmos]

is this accurate

[opal oriole]

Yes.

[fiery cosmos]

idk what it is but summations are so nonintuitive to me

[haughty mountain]

why wouldn't the dfs just go down in this case and get the wrong distance to the goal?

1 1 9
9 1 9
1 1 9
1 9 9
1 1 1

[fiery cosmos]

like having "the summation one" just adds so much unnecessary ambiguity

are we adding one? to what? are we beginning at one? is it both?

[opal oriole]

In the same way you do 1+5+3. What is it adding to? Nothing, it's just there.

You can combine them all into 1 value.

And the summation notation denotes that combined thing.

[fiery cosmos]

here we are beginning with a single term 1, and adding 2 terms 5 and 3 to it. the order could be any different which way and it wouldn't change things, but its the same basic operations

[haughty mountain]

why? it's literally just a short form

\sum_{i=a}^b f(i) = f(a) + f(a+1) + ... + f(b-1) + f(b)

for whatever function f

[opal oriole]

Yea, but let's say we have 1+2+3+4+5+...+984357893763979865. Would you want to write that all out?

[opal oriole]

Instead we can just say sum from i = 1 to 984357893763979865. Basically when there is a pattern, you can compress things, symbolically, etc. And that notation lets us do that.

[fiery cosmos]

how would one evaluate this in english

[fiery cosmos]

i guess my brain just doesn't work that way idk

[agile sundial]

the sum of (1 + 1) from i=0 to n

although you'd just say 2n

[haughty mountain]

the dfs doesn't go in a specific direction, it just goes while the distance is less than some limit

[fiery cosmos]

and how would you do this mathematically

[opal oriole]

I add twos, n plus one times.

[opal oriole]

2+2+2+2+...+2 (n+1 times)

(There are n+1 twos)

[fiery cosmos]

why n+1

the max is n

[opal oriole]

Because you started at i = 0 rather than 1.

Try n = 3: Then i is [0, 1, 2, 3].

(4 things)

[fiery cosmos]

alright i'll change my index to begin at 1 but in python i think it'd be zero

[opal oriole]

Yeah, you can just make the end n-1.

To make up for the +1 from starting at 0.

Which is what Python does. The index is never equal to n, it's as most n-1.

When you do for i in range(5), i is [0, 1, 2, 3, 4]. (5 total iterations)

[opal oriole]

The last one is n+1.

[fiery cosmos]

dang!! ok lol

[opal oriole]

(When i = n)

[opal oriole]

Summation notation starts on the start value and ends on the end value.

[fiery cosmos]

like ) or ]

[opal oriole]

[]

[fiery cosmos]

so including

[opal oriole]

Yeah.

I mean in the 2+3+4+5+...+(n+1)

[fiery cosmos]

ok. i'm starting to get it although the idea of describing two loops with a single summation still has me 😵‍💫 🥴

[opal oriole]

We will get to that, first do you understand why the last is n+1?

[opal oriole]

In this.

=2+3+4+5+...+(n+1), not 2+3+4+5+...+n.

[fiery cosmos]

bc we started at i=1 not i=0

[haughty mountain]

wait, I read the problem wrong :/

[opal oriole]

Nope.

[haughty mountain]

it's the max along the path, not sum

[opal oriole]

What is the start i value and what is the end value?

[haughty mountain]

then yes it works

sure

[fiery cosmos]

for this?

[opal oriole]

Yes.

[fiery cosmos]

i begins a 1 and ends at n

[opal oriole]

And what is the value inside the sum at 1 and at n?

[haughty mountain]

you can write it with two sums if you want to

\sum_{i=1}^{n-1} \sum{j=i+1}^n 1

err, I'm missing an _

after the 2nd \sum

if you add that it should work properly

[fiery cosmos]

when i=1 its 1+1 = 2 and when i=n its 2+3+4...+n+1

[opal oriole]

I meant the specific part of the sum at n, not up to n.

[haughty mountain]

fixed```
\sum_{i=1}^{n-1} \sum_{j=i+1}^n 1

[fiery cosmos]

n+1

[fiery cosmos]

@haughty mountain what code is this describing

[opal oriole]

Yeah so, do you see why it's 2+3+4+5+...+(n+1) and not 2+3+4+5+...+n?

[haughty mountain]

the selection sort you posted

[fiery cosmos]

no i only said it was n+1 bc of the expression in the summation e.g. (i+1)

[opal oriole]

Well, if i = 1 gives you the first value in the sum (2), and i = n gives you the last value in the sum, then the last value is not n, it's n+1.

    2 + 3 + 4 + 5 + ... + (n+1)
i = 1   2   3   4   ...     n

(The summation is doing i+1 for each term)

[fiery cosmos]

i think we're confusing the expression with the maximum range

[haughty mountain]

maybe it would be worth practicing some sums? e.g. what is this sum in the sigma notation?
4 + 9 + 16 + ... + 64 + 81

[haughty mountain]

cool, so you get how that one fits together

[opal oriole]

How about 4 + 9 + 16 + ... + n^2?

[fiery cosmos]

yeah like i said it makes sense when its integers, not theoretical lines of code run

[fiery cosmos]

lms

[haughty mountain]

we are just counting how many times the interior of the inner loops run, it's all integers

[opal oriole]

What happens when i = n^2?

[haughty mountain]

well, the upper limit isn't quite right

[fiery cosmos]

idk what happens

[opal oriole]

You get n^4.

n^4 is not the last value in the sum I gave.

[fiery cosmos]

wat

[opal oriole]

(n^2)^2

[fiery cosmos]

wat??? it should just be up until i = n^2???

[opal oriole]

It is up until i = n^2.

[fiery cosmos]

bruh

this confusin as hell

[opal oriole]

If you substitute you get i^2 = (n^2)^2.

[haughty mountain]

the thing in your sum is i²

if you put i=n² in there you get...badness

i.e. n⁴

[opal oriole]

The i^2 inside the sum is the value of each term in the sum.

[haughty mountain]

much like your upper limit before was sqrt(81) = 9, the new limit is sqrt(n²) = n

[fiery cosmos]

right..

[opal oriole]

When i = 1, you get 1^2, when i = n^2, you get (n^2)^2.

[fiery cosmos]

no i'm lost

[haughty mountain]

like, how did you figure out the limits in the sum 4 + ... + 81?

[fiery cosmos]

you just go up until i=9

[opal oriole]

Try n = 4.

In your sum.

Expand it out.

[haughty mountain]

why i=9?

(it's correct, I just want to see why you arrived at it)

[fiery cosmos]

working on it

[fiery cosmos]

bc that captures the final term in your sequence

i^2 = 81

[haughty mountain]

because 9² = 81, right

what about when the last term is n^2?

you can apply the same logic

[fiery cosmos]

i can't evaluate this bc i don't know when i=n^2

ugh this is so frustrating. i can tell that y'all want me to change the upper bound to n instead of n^2 but i have no idea why

[opal oriole]

Goal (n = 3):
1^2 + 2^2 + 3^2

Using your summation (n = 3 also):
        1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 + 9^2
i =     1     2     3     4     5     6     7     8     9

Because n^2 = 9, and your summation ends on n^2.

[fiery cosmos]

or like, i can't see how the expression would change the upper bound in such a manner

[haughty mountain]

i^2 = 81  -> i = 9
i^2 = n^2 -> i = ???

[fiery cosmos]

right ok

[haughty mountain]

you can do operations with variables just like you can do with regular numbers

i.e. the logic for the limit remained the same

sqrt(81) = 9
sqrt(n²) = n

[opal oriole]

If you summation ends on n: ```
(n = 3 again):
1^2 + 2^2 + 3^2
i = 1 2 3

[fiery cosmos]

i think all the variables get me or the math part of my brain is.. limited..

[opal oriole]

Now instead of n = 3, what if n = n?

(Not a specific value)

[fiery cosmos]

for this one:
?

[haughty mountain]

variables are basically just placeholders for some number, you don't know the number yet, but you can still do operations on it

e.g. x+x = 2x

x*x = x²

sqrt(x²) = x

and whatnot

in the end, here it's just some integer

it behaves just like an integer would

[fiery cosmos]

i guess variables are variable eg x and constants are fixed eg k

[opal oriole]

If variables are placeholders, then think of 1+4+9+16+...+n^2 as another placeholder. The entire thing waits for some value of n.

But you can still do operations on it until then.

[fiery cosmos]

i thought it 'waits' on a certain value i, eg when i =n^2

[opal oriole]

You can think of it generating the entire thing up until the end value which depends on what n is.

And to generate it step by step, it uses i.

As a result n also determines how many generation steps are needed.

[fiery cosmos]

but to be clear it terminates when the index of summation i is equal to n (or n^2)

[opal oriole]

When it's equal to whatever the end is.

In this case it would be n.

Because each term is i^2.

We generate each term by i^2.

And we want the last generated term to be equal to n^2.

So we must choose the correct end value for the summation, which in this case is n.

Because (n)^2 when you replace i with n.

[fiery cosmos]

wdym replace i with n

[opal oriole]

It needs the match the 1+4+9+16+...+n^2 pattern.

[fiery cosmos]

i thought its when i = n

[opal oriole]

i = n is replacing i with n.

Substitution.

[fiery cosmos]

sorry when do you 'replace' the upper bound with i??

[opal oriole]

Other way around.

i with the upper bound, is the last term.

i gets set to the upper bound.

i := n

(i becomes n)

At first i becomes 1, then i becomes 2, then i becomes 3, etc until i becomes n.

That would match 1+2+3+4+...+n on its own (sum of i from i = 1 to n).

To get it to match 1+4+9+16+...+n^2. we just square i.

[fiery cosmos]

right..

you're kind of just proving my point that the max should be n^2

[opal oriole]

The max value is n^2.

But the max i is n.

The value is i^2.

[fiery cosmos]

ohhhh

i think something just clicked

with "the max value is i^2, but the max i is n"

[haughty mountain]

in \sum_a^b i sweeps from a up to b, and you get one term for every step

i=a, i=a+1, ..., i=b-1, i=b

and you evaluate what's in the sum for every of those values for i and sum the results

[opal oriole]

The index is used to generate the value.

The index max is not the same as the value max.

[haughty mountain]

err I meant to write \sum{i=a}^b

my bad

[opal oriole]

(Unless the value is just i)

[fiery cosmos]

thats not right lol

[agile sundial]

you need _ and ^ for start and end

[haughty mountain]

dammit, forgot the _ again 😭

[opal oriole]

This will give you the indices. But now you need to choose what your values will be, which can be based on the indices.

[haughty mountain]

is it not possible to fork from the mobile website or am I blind?

[haughty mountain]

hence why I write

\sum_{i=a}^b f(i) = f(a) + ... + f(b)

the thing you sum is some expression in terms of i

i.e. some function of i

[jolly mortar]

not sure im on phone too but im not signed in

[fiery cosmos]

alright i need to look at the selectionsort and the two loops and see if its clicking

[haughty mountain]

searching around all I see is "switch to desktop mode", which is just sad

[opal oriole]

What is 1+4+9+16+...+n^2 though now? With that notation.

(Can you get the right side to match / align?)

(What is f(i) = ?)

[fiery cosmos]

1

[opal oriole]

That is correct.

[fiery cosmos]

its correct that the notation is needlessly confusing

[opal oriole]

f(i) = i^2, f(a) = 1, f(b) = n^2.

(It matches the 1+4+9+16+...+n^2, you can tell by checking the ends)

[fiery cosmos]

i really don't see how n has anything to do with getting squared, its just when you stop your computations, when i = n

i guess its when i = n you could think of it as n^2, but its really just end on i when i equals n and square i as the last term

anyway, thanks for all your help today y'all

some day i will write out the neat conversion i used to do in the lab btwn ng/uL DNA and [nM]

if anyone is interested

the neat thing of it is that the [nM] concentration is based on the size of the DNA fragments, so you have to measure that, get an average, and then use the average DNA molecule length in your calculation

bc the instruments wanted to be loaded at a certain pM concentration, not pg/uL

that is, for optimum loading they wanted trillionths of one mole per liter

say like 20 trillionths of one mole or similar

IIRC

[haughty mountain]

welp, let's see what happens https://github.com/python-discord/sir-lancebot/pull/1083

[haughty mountain]

n^2 has to do with getting squared though :P

[opal oriole]

Yeah i = n, theni^2 = n^2. Last index n, last value n^2.

[haughty mountain]

woot, merged

[agile sundial]

.latex \iiint

😭

[fiery cosmos]

$\sum{i=a}^b$

[haughty mountain]

.latex $\int_{-\infty}^\infty \mathrm{e}^{-x^2} \mathrm{d}x = \sqrt{\pi}$

[fiery cosmos]

.latex $\sum{i=a}^b$

[agile sundial]

ew inline

[haughty mountain]

does $$...$$ work for display math?

[agile sundial]

¯_(ツ)_/¯

[grand haven]

Failed to render input.

View Logs

[opal oriole]

.latex $$\sum_{i=1}^{n}{i^2}$$

[haughty mountain]

cool

@stone sorrel thanks! ❤️

[opal oriole]

Finally no more hand-waving for this stuff.

[haughty mountain]

yeah, this will be useful for a bunch of the math flying around

[opal oriole]

.latex $$\sum_{i=1}^{n}{\color{red}i^2}$$

[grand haven]

Failed to render input.

View Logs

[opal oriole]

Aw.

[haughty mountain]

color needs a package I think

[opal oriole]

.latex $$\sum_{i=1}^{n}{\color{red}{i^2}}$$

[grand haven]

Failed to render input.

View Logs

[opal oriole]

Which one?

[haughty mountain]

xcolor, I think

[opal oriole]

.latex \usepackage{xcolor} $$\sum_{i=1}^{n}{\color{red}{i^2}}$$

[grand haven]

Failed to render input.

View Logs

[opal oriole]

Will this just work?

Nope.

[haughty mountain]

.help latex

[stone sorrel]

Haha that’s unfortunate

[opal oriole]

.latex \usepackage{xcolor} $$\sum_{i=1}^{n}{\color{red}{i^2}}$$

[grand haven]

Failed to render input.

View Logs

[opal oriole]

Nope.

[stone sorrel]

I don’t entirely understand latex, but we use an external API for it

I believe they document what they support

[haughty mountain]

package includes need to be before \begin{document} iirc, so I don't think this will work sadly

[fiery cosmos]

hey y'all were helping me with my recursive mergesort before but i guess i never got it working? anyone remember what was wrong? i'll paste the code

import time
import math
import random

def merge(array,p,q,r):
    
    n1 = q-p
    n2 = r-q
    
    left = [0 for x in range(n1)]
    right = [0 for x in range(n2)]
    
    for i in range(n1):
        left[i] = array[p+i]
    for j in range(n2):
        right[j] = array[q+j]

    left.append(math.inf)
    right.append(math.inf)

    i = 0
    j = 0

    for k in range(p,r):
        if left[i]<=right[j]:
            array[k]=left[i]
            i+=1
        else:
            array[k] = right[j]
            j+=1


def mergesort(array,p,r):
    if p < r:
        q=(p+r)//2
        mergesort(array,p,q)
        mergesort(array,q+1,r)
        merge(array,p,q,r)


a = []
for x in range(100):
    a.append(random.randint(1,1000))

print('the array before sorting is: ' + (str(a)) + '\n')

start=time.time()

mergesort(a,0,(len(a)))

print('the array after sorting is: ' + str(a))

start=time.time()

[haughty mountain]

you could send a PR to add it to the template the bot uses https://github.com/python-discord/sir-lancebot/blob/main/bot/resources/fun/latex_template.txt

[haughty mountain]

you're mixing indexing standards

e.g. the q+1 should just be q in mergesort

that's the obvious thing I see at least

I suspect CLRS uses dumb indexing, and you've half-converted to the saner one

[fiery cosmos]

Ok I’ll look it over again

I think removing that q+1 gives me a recursion error

[haughty mountain]

def mergesort(array,p,r):
  if r - p > 1:
    q=(p+r)//2 
    mergesort(array,p,q)
    mergesort(array,q,r) 
    merge(array,p,q,r)

the if check is also slightly different with [p, r) indexing

in short, if there are 2 or more elements, use merge sort to sort the halves

maybe r - p >= 2 is nicer, but whatever

[fiery cosmos]

@haughty mountain you are a wizard

why would they have py if p < r: in the pseudocode

[haughty mountain]

lol, it was easy enough to find the other fix needed after actually running the code and seeing the error

[haughty mountain]

they use different indexing, they use inclusive-inclusive, i.e. [p, r] rather than [p, r)

[p, r) is a much nicer way of indexing, it removes a lot of +1s all over the place

like, the halves are [p, q) [q, r)

[fiery cosmos]

yeah i think it was squiggle that helped me work this out

or yourself

either way i'm familiar with the "up to but not including" aspect of pythonic ranges now

[haughty mountain]

it's just a nicer standard in general imo

e.g. the length of [p, r) is just r-p

[fiery cosmos]

right. and it works with my initial call bc the upper bound is len(array), which conveniently terminates at and including the array's highest index

wow mergesort is fast!

0.11s on average to sort an array of 10k randomly generated integers btwn 1-10k

[haughty mountain]

yeah, it's quite good

it has some disadvantages, but it's a very solid sorting algo

[fiery cosmos]

lets try an array of 100k 🙂

will it scale linearly? i guess not if its nlgn runtime

[haughty mountain]

n lg n, yeah

[fiery cosmos]

eg we'd expect it to do 1.1s if it scaled linearly

but i guess it doesn't bc its n * lg(n)

lets see

i don't want to fry my cpu, i should pull up some diagnostics

eh it is almost linear, its taking like 1.2s for array of 100k. that's, insane

everything is default its not even overclocked or anything

i could overclock up to 4.3GHz ish

still not returning the entire arrays on output, super annoying. i'll have to get that worked out

array size of n=1m ints btwn 1-100k takes 13.5s

[haughty mountain]

looks not quite linear, these are avg runtime for a bunch of samples

     1: 5.502268240088597e-07s
    10: 4.7196618240559475e-05s
   100: 0.0005869835479999893s
  1000: 0.007533813875983469s
 10000: 0.09336091971956194s
100000: 1.115556204796303s

i.e. slightly superlinear

smells like a log factor

[opal oriole]

Want to make your implementation faster?

[fiery cosmos]

sure. one sec i am in a call

[fiery cosmos]

@opal oriole i don't think i'll get time tonight i have office hrs in 15m

[stone magnet]

Apparently deques as recommended to use over lists. What about versus Numpy arrays?

[agile sundial]

deques aren't recommended over lists in general, only in certain situations

same with numpy arrays. all 3 are used because all have different things they're good at

[agile sundial]

deques are good when you need to append/pop a lot at both ends

[compact hill]

hello, does somebody know how to print a graphic of this "df_boston.plot(kind='scatter', x= 'Rooms', y= 'Value')" with the library statsmodels, the guy of the tutorial is using jupyter and he just entered and that's it, but am using vscode and it doesn't work

[vestal citrus]

#data-science-and-ml might be better-suited for your question. Jupyter is an interactive notebook and DataFrame.plot() simply displays in the notebook. In VSCode, you’ll have to do import matplotlib.pyplot as plt and plt.show() iirc

[compact hill]

Oh okay, yeah thanks dude, i'll do it with matplot then

[twin vapor]

ello

leetcoding

[frigid zealot]

Is it necessary to master data structures and algorithms for a data scientist?

[finite rose]

Where I can learn python easily?

[haughty mountain]

!resources

[halcyon plank]

Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

[haughty mountain]

also, #python-discussion is a better channel to ask that

[stone magnet]

Is that the specific use case of deques? Just popping and appending?

[agile sundial]

yes

[stone magnet]

Interesting, I mean I've had to pop or append a few times but never like more than once

I wonder what deques would be best applied to

[shut breach]

they're used for queues

[lament totem]

They're nice when you want a rolling window over some bigger data for example

That way you can append to the right, and pop from the left

[stone magnet]

Oh yeah that makes sense, I can see how deques can be very useful for that

[fiery cosmos]

just learned new logarithm property:

also

[fiery cosmos]

just found this resource:
https://pimbook.org/

[glad gyro]

my braincells are getting fried

[fiery cosmos]

yeah tell me about it. i'm focusing on this stuff and proofs bc its the most difficult material for me

[vocal gorge]

it's a consequence of the property that log_b(a) = log_c(a)/log_c(b), where c is an arbitrary third base.

[glad gyro]

meanwhile im stuck on doing college physics questions compared the logrimithics are big diff but i do code for fun or macros

[fiery cosmos]

i did two college physics courses but they were the dumbdumb ones, algebra based not calc based

which really doesn't make sense

[agile sundial]

actually in some situations, avoiding calc makes things very very annoying

[fiery cosmos]

yeah i could see that. i don't recall how bad it was, only at one point i thought i had an epiphany about reversing the concept of an electric generator and instead using the magnetism to drive the rotation of an axel, i talked to the prof about it and he said "you just described an electric motor" so i guess i sort of found my way to that concept which made me happy

i took brief calc but that was brutal bc i was also in organic chem and micro and stuff

i'd love to go back and relearn it

hmm i just thought of something,

for i in range(10)``` goes up to and does not include 10, (pythonic range function is [x,y), but how about when you are stepping by ```-1```

eg for i in range(mid,low,-1):

i suppose a simple reversal would indicate that it begins at mid, and goes down to and includes low

actually, this would seem that it goes down to and does not include low

bc of the [mid,low) nature of the function

[glad gyro]

i hate algebra but like its non making sense of sht

like how did the x get converted into the answer

basiclly that but in advance lv

[fiery cosmos]

lets keep this focused on algos and data structures, feel free to PM me

[haughty mountain]

right, that's why I much prefer to do reversed(range(...)) instead

[fiery cosmos]

right i recall you mentioning that before, i wonder if reimplementing that in my code would solve my recursion error

so if range(1,10) begins at and includes 1 and goes up to and does not include 10, then reversed(range(1,10)), begins at and includes? 10 and goes down to and does not include 1?

could you clarify? alternatively i will search for the answer

i can just print these things

or not

keep getting range_iterator object

[agile sundial]

use list on it to get a list

[fiery cosmos]

ty

ok so looks like it begins at and does not include 10, just as we might expect of the reversed range

x = range(1,10)
x = reversed(x)
print(str(list(x)))

prints:

[9, 8, 7, 6, 5, 4, 3, 2, 1]```

omg i'm doing my python certs all over again 🤦‍♂️

well you know what they say, you don't use it you lose it

do we have a python runtime environment in here

where we can run code within discord

[agile sundial]

!e

[halcyon plank]

Missing required argument

code

Command Help

!eval [python_version] <code, ...>
Can also use: e

*Run Python code and get the results.

This command supports multiple lines of code, including code wrapped inside a formatted code block. Code can be re-evaluated by editing the original message within 10 seconds and clicking the reaction that subsequently appears.

If multiple codeblocks are in a message, all of them will be joined and evaluated, ignoring the text outside of them.

By default your code is run on Python's 3.11 beta release, to assist with testing. If you run into issues related to this Python version, you can request the bot to use Python 3.10 by specifying the python_version arg and setting it to 3.10.

We've done our best to make this sandboxed, but do let us know if you manage to find an issue with it!*

[fiery cosmos]

!e x = range(1,10)
x = reversed(x)
print(str(list(x)))

[halcyon plank]

@fiery cosmos :white_check_mark: Your 3.11 eval job has completed with return code 0.

[9, 8, 7, 6, 5, 4, 3, 2, 1]

[fiery cosmos]

cool

obligatory:

!e print("Hello World!")

[halcyon plank]

@fiery cosmos :white_check_mark: Your 3.11 eval job has completed with return code 0.

Hello World!

[fiery cosmos]

!e

import math
from math import floor

def findmaxcrossingsubarray(a,low,mid,high):
    left_sum = -math.inf
    sum = 0
    for i in reversed(range(low,mid)):
        sum = sum+a[i]
        if sum > left_sum:
            left_sum = sum
            max_left=i

    right_sum = -math.inf
    sum = 0 
    for j in range(mid,high):
        sum = sum+a[j]
        if sum>right_sum:
            right_sum = sum
            max_right = j

    return(max_left,max_right,left_sum+right_sum)


def findmaxsubarray(a,low,high):
    if high == low:
        return(low,high,a[low])
    else:
        mid = floor((low+high)/2)
        (left_low,left_high,left_sum) = findmaxsubarray(a,low,mid)
        (right_low,right_high,right_sum) = findmaxsubarray(a,mid,high)
        (cross_low,cross_high,cross_sum) = findmaxcrossingsubarray(a,low,mid,high)
        if left_sum>=right_sum and left_sum>=cross_sum:
            return (left_low,left_high,left_sum)
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return (right_low,right_high,right_sum)
        else:
            return(cross_low,cross_high,cross_sum)

a = [10,-12,2,-6,8,5,-3,4,7,-13,25,-22,89,71]

# print(findmaxcrossingsubarray(a,0,((floor(len(a)/2))),len(a)))

print(findmaxsubarray(a,0,len(a)))

[halcyon plank]

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "<string>", line 43, in <module>
003 |   File "<string>", line 29, in findmaxsubarray
004 |   File "<string>", line 29, in findmaxsubarray
005 |   File "<string>", line 29, in findmaxsubarray
006 |   File "<string>", line 30, in findmaxsubarray
007 |   File "<string>", line 30, in findmaxsubarray
008 |   File "<string>", line 30, in findmaxsubarray
009 |   [Previous line repeated 992 more times]
010 |   File "<string>", line 28, in findmaxsubarray
011 | RecursionError: maximum recursion depth exceeded while calling a Python object

[haughty mountain]

I mean, it's just the same range, just in reverse order

[fiery cosmos]

right i was musing about how the list would change if the inclusions were also reversed, but clearly that does not happen

eg [1,10) --> (1,10]. but no, that was incorrect way of thinking about it

ok so i'm trying to solve the recurrence T(n) = 2T(floor(n/2) + 17) + n

via substitution

and in an exemplary problem i learned to solve a similar recurrence (which did not include the 17), and substitute in m = n/2 into my guess of O(nlgn), getting the form T(n) < c(n/2)lg(n/2), and then substituting in this guess into the recurrence. my question is, how do i handle this problem given the 17 there. must i use m = (n/2)+17?

i get that T(n) <= (cn+17)(lg(n+34)-1+n == O(cnlgn)

did anyone else solve?

i also have a question regarding recursion trees

[haughty mountain]

I can't be bothered to do the details with the constants, but slightly sloppy

T(n) = 2T(floor(n/2) + 17) + n

Guess T(n) = a * n log n

T(n) = 2(a (floor(n/2) + 17) log(floor(n/2) + 17)) + n
    <= 2 a (n/2 + 17) log(n/2 + 17) + n
     = 2 a n/2 log(n/2 + 17) + O(n)
    <= a n log(n) + O(n)  # for n >= 17

[fiery cosmos]

ok thanks @haughty mountain

anyone have good resources for where to practice proofs by substitution?

[inland stirrup]

Would anyone be able to help me out with the problem I've listed below? I've tried to solve it using the simplex method but I can't figure out how to do it. I've come up with a solution I think is in polynomial time which would be to draw lines between each colored pair point until a valid line is found that would divide up the points but I'm not sure if that approach is actually valid.

[fiery cosmos]

would someone pls point out flaws in my logic / where i have gone wrong, thank you:

[haughty mountain]

this part isn't given, it's what you want to show

or wait

let me re-read

[fiery cosmos]

no you're right i sort of did it backwards. i'm supposed to first derive this:

and plug this into the c n lgn expression

[haughty mountain]

so you want to show that this is bounded by c n lg n

.latex $$T(2^{k+1}) = 2 T(2^k) + n$$

[haughty mountain]

yeah, what you wrote

[opal oriole]

The question is asking to show that T(n) = nlgn right?

[fiery cosmos]

i'm doing it the longhanded algebraic way rn

[fiery cosmos]

correct

[opal oriole]

No big O involved.

[haughty mountain]

oh yeah

an exact result

[opal oriole]

Not really even a CS question, just induction to get a closed form.

[fiery cosmos]

yea i should be posting in the math server

[opal oriole]

It shows up in CS, but it's more generic than that technically. Just as most induction goes with recurrence.

[fiery cosmos]

lol what is algmyy typing

[haughty mountain]

so, something like this

assume T(n) = n lg n

T(2n)
 = 2T(n) + 2n
 = 2n lg n + 2n
 = 2n lg n + 2n lg 2
 = 2n lg(2n)

I should probably derive my expressions in a text editor and then copy it over rather than type for forever here :P

[fiery cosmos]

thats what i do

[haughty mountain]

wait

that's not what we wanted to show...

we wanted to show =

err...

oh

I lost a 2

fixed it

[fiery cosmos]

we wanted to show that when n=2^k for k>1, the solution to the recurrence T(n) = 2T(n/2)+2 = nlgn

[haughty mountain]

yes

assuming it's true for T(n), I showed it's true for T(2n)

[fiery cosmos]

oh. can you do it that way and avoid all the specifics?

[haughty mountain]

or T(2^k) and T(2^(k+1)) if you prefer, same thing

wdym avoid all specifics?

[fiery cosmos]

like rather than showing all this:

[haughty mountain]

oh, having it in form 2^k isn't too helpful it turns out

[haughty mountain]

your last line should be 2n lg(2n)

[fiery cosmos]

oh i didn't write this, i've just been spending a lot of time to understand what they did algebraically

which i now get by some miracle

[opal oriole]

T(n) = 2T(n/2) + n = nlg(n)

T(2n) = 2T(n) + 2n

(by induction hypothesis)
T(2n) = 2(nlg(n)) + 2n
T(2n) = 2nlg(n) + 2n
T(2n) = 2nlg(n) + 2nlg(2)
T(2n) = 2n(lg(n) + lg(2))
T(2n) = 2nlg(2n)

(lg(2) = 1)

(Can also go the 2^k route)

[haughty mountain]

you can totally do it in the world of k rather than n if you want to

we want to show that T(2^k) = 2^k lg 2^k = k 2^k

assume T(2^k) = k 2^k

T(2^(k+1))
 = 2T(2^k) + 2^(k+1)
 = 2 k 2^k + 2^(k+1)
 = k 2^(k+1) + 2^(k+1)
 = (k+1) 2^(k+1)

[opal oriole]

(Same thing but working in exponents rather than logs, I prefer logs for less parens here (not a problem with actual work on paper))

[haughty mountain]

it's a bit awkward to jump back and forth between n and k here imo, I would either work in n, or translate the whole problem to use k

[opal oriole]

2^(k+1) would be 2n.

(not n on your final step)

(although you could argue trivial change in variables, but depends on your grader / teacher (you can reuse variable letters but I would avoid this unless you have more experience with how algebras and proofs work in more detail))

[haughty mountain]

oh yeah, I pointer that out earlier

[haughty mountain]

using n to mean something different later is certainly an error

[opal oriole]

Technically you can, but I would not recommend. I really dislike it when it's done.

(It's something I see when a mathematician is trying to impress / skip steps)

[haughty mountain]

I can see three paths

1. work with n the whole time
2. translate expression to k and translate back later
3. translate the whole problem to k and solve it

[opal oriole]

These are the ways yeah.

[fiery cosmos]

@opal oriole it looks like in this line:
T(2n) = 2nlg(n) + 2nlg(2)
you multiplied by 1 in the form of lg(2) so that you could combine terms

[opal oriole]

(You could do ridiculous things for fun, but they are not practical (like put in some calc for no reason))

[haughty mountain]

I would still call it a clear error as written. Adding "where n = 2n" wouldn't really help either :P

[opal oriole]

Multiply by fancy form of 1 yeah.

[haughty mountain]

yes, remember the deadly weapons

adding 0

multiplying by 1

[opal oriole]

(log edition this time)

[fiery cosmos]

it actually has been practical in this situation bc i've been forced to learn the algebra and logarithm rules

but yeah i get what youre saying

[haughty mountain]

I think there is a third one, but I can't remember :/

[opal oriole]

There are a few for more advanced stuff like intergal of the derivative, e^log(x), etc.

[haughty mountain]

the deadly tricks were a sayings from a lecturer at my university before my time there, stories that's been passed down between generations of students

[opal oriole]

(basically f^-1(f(x)))

[fiery cosmos]

this tells me if you have two terms with logs of the same base and are adding them, you can instead take lg(term1*term2)

[opal oriole]

Yes, log sum rule.

(Or product rule depends on where you start)

[haughty mountain]

fwiw these are the same rule in different forms

lg(a)+lg(b) = lg(a b)

2^a 2^b = 2^(a+b)

addition being multiplication in the log world has fun applications

e.g. slide rules

[opal oriole]

(And log probabilities for summations instead of products)

[haughty mountain]

yeah, log probabilities are nice

[fiery cosmos]

can y'all think of a recursion i could try as practice

practicing solving using a substitution proof?

[opal oriole]

Pick some pattern sequence.

(For which you know the recurrence)

(Or try to figure it out first (extra credit))

[fiery cosmos]

i was doing that before but i want to stick with recurrences. i guess i could try to prove the fibonacci numbers but that seems too complicated

[haughty mountain]

I can give you a boring one that you've probably solved before

T(n) = T(n/2) + 1

what is an algo with this recurrence?

[fiery cosmos]

is there more randomness in the first or last five digits of pythons hash?

[haughty mountain]

what even is python's hash algo?

[fiery cosmos]

python has an inbuilt hash function?

[haughty mountain]

it does

[fiery cosmos]

based on what it could be anything

[opal oriole]

Depends on what type given.

[haughty mountain]

the python hash for integers is...bad

[agile sundial]

fast though

[fiery cosmos]

no i mean how did they pick one, it could be any function that someone thought was appropriate

CLRS gets into hashing functions a bit

something something prime number that splits not quite evenly

[agile sundial]

trial and error, basically, based on a good guess

[fiery cosmos]

knuth has written about this

[haughty mountain]

well, some proofs of properties as well

[opal oriole]

A lot of hash functions in programming have been picked by trial and error and some are wide spread but undocumented, nobody even knows the authors.

Others are more seriously analyzed.

[fiery cosmos]

hm

[haughty mountain]

the int hash is so silly, it's basically

def int_hash(n):
  if x != -1:
    return x
  return -2

because python uses -1 to signal "the operation failed"

because fun

[opal oriole]

Nothing beats the speed of doing nothing.

[haughty mountain]

nothing except in one case

so you always have a branch

unless you can write it branchless, idk

[opal oriole]

return -2 * (x == -1) + x * (x != -1) (The (x == -1) can be reused, compilers will optimize this for you (including making it branchelss, not sure if CPython does in its bytecode))

[haughty mountain]

it's still amusing that -1 is an illegal hash value

[opal oriole]

Branchless is often just multiplying by the boolean checks.

[haughty mountain]

because sketchy error handling

[opal oriole]

(Although on actual machine code, there is a specific instruction to make things branchless (often, depends on ISA))

[fiery cosmos]

hey i'm gonna ask a really dumb question

when evaluating T(n) = T(n/2) + 1, let's say i input 2, I get T(2) = T(1) + 1, so i must therefore have to go and lookup/calculate T(1) to get the answer yeah?

[haughty mountain]

assume T(1) = 1, so you have a base case

[opal oriole]

You just declare what T(1) is. Like how in the problem you gave they had a piecewise function.

(But it's just a detail that is not super important for this practice)

[haughty mountain]

T(4) = T(2) + 1 = T(1) + 1 + 1 = 1 + 1 + 1

[fiery cosmos]

so its T(1) = 1, and T(n/2) + 1 otherwise (when n>1)

[haughty mountain]

n>1 at least

[opal oriole]

(=/= could include negatives and zero)

[haughty mountain]

n<1 feels like badness

for n not a power of two you would need to add a floor/ceil, but that's not so interesting

[fiery cosmos]

how would you eval T(3)

[haughty mountain]

as said, you would need to have T(ceil(n/2)) or similar

or just assume n = 2^k

it doesn't matter for the result

[fiery cosmos]

i think i have the core of whats required but its so scatterbrained i don't make the point and/or its circular logic:

i think im just memorizing a pattern and not really understanding. i think i would have come to the same conclusion even if i guessed the wrong answer

like i would have shown that lgn of the equation is lgn whether n=2^k or some other form

i guess the base case of T(2) = 2 = nlgn makes it hold

[opal oriole]

The question was what is an example of an algorithm with that recurrence.

@fiery cosmos

[haughty mountain]

well, the solution as well

identifying an algo with that recurrence is more of an extra

[haughty mountain]

the answer is not n lg n

[fiery cosmos]

yeah i had a feeling

/sigh

[haughty mountain]

I mean, consider a few values

e.g. T(8)

[fiery cosmos]

i was thats how i wound up at T(3)

[haughty mountain]

or T(16)

as for what an algo like this is, I read

T(n) = T(n/2) + 1
```as: do some constant amount of work and then consider only one half of the data

e.g. ||binary search||

[fiery cosmos]

binary search is lgn?

[edgy gazelle]

try: ||log_2 n||

[haughty mountain]

yep

[fiery cosmos]

we use lg to mean log_2

[edgy gazelle]

oh lmaooo my bad

[haughty mountain]

the recurrence basically counts how many times you can divide the data in half

[fiery cosmos]

but log_2(2) = 1

so when i eval T(2) = 2, T(2) =/= log_2(2)

[edgy gazelle]

(sol) ||T(n/2)+1= lg(n/2)+lg(2)=lg(n)||

[haughty mountain]

I should probably have picked T(1) = 0, huh?

it's one off

[fiery cosmos]

ok

[haughty mountain]

log_2(n) + 1

[fiery cosmos]

wait what

what is log_2(n) + 1

you're saying the sltn is lgn+1?

[edgy gazelle]

what does sltn mean 😭

[fiery cosmos]

solution

[haughty mountain]

maybe with a parenthesis to not confuse with lg(n+1), but yes

[fiery cosmos]

i knew it was off bc i was putting in T(16) and getting 32

anyway lets get back to basics

are you changing the sltn or the base case

if we change the base itll work

no need to make it lgn+1

btwn in the book they explicitly state, lgxny = lg(x)ny

they say the lg only applies to the immediately proceeding term

and no others

[haughty mountain]

T(8) = T(4) + 1 = T(2) + 1 + 1
= T(1) + 1 + 1 + 1 = 1 + 1 + 1 + 1 = 4

lg(8) + 1 = 4

yes, my base case was a bit off if I wanted to have the answer be exactly lg n

[fiery cosmos]

but you need to change one or the other not both

[haughty mountain]

as I stated it initially the exact solution (for n = 2^k) is lg(n) + 1

[fiery cosmos]

with T(1) = ?

[haughty mountain]

if T(1) = 1

[fiery cosmos]

ok

[edgy gazelle]

general sol is lgn+T(1) if interested btw

[haughty mountain]

right

[edgy gazelle]

which is reasonable bc u can just subtract both sides by T(1)

[fiery cosmos]

alright im gonna make my base case T(2) = T(1)+1 = lg(2)+1 = 2

now i'll get a form for T(n), assume it to be true, then prove that the n+1 form will take the same form, namely lg(n)+1

[haughty mountain]

T(1) = 1 is already a fine base case, no?

[haughty mountain]

2n form in this case

[fiery cosmos]

oh yeah bc you could do lg(1)+1

[haughty mountain]

the next higher step

[fiery cosmos]

ok T(2n) = T(n) + 1

sigh i am comically bad at this

[haughty mountain]

it's the same trick as last one

T(2n)
 = T(n) + 1
 = lg(n) + 1 + 1
 = lg(n) + lg(2) + 1
 = lg(2n) + 1

[fiery cosmos]

ah i see

so T(2n) = lg(2n)+1 --> T(n) = lg(n)+1

[haughty mountain]

it's more that you show that the guess you make works for 2n if it works for n

i.e. you can jump one step up

[fiery cosmos]

and we're doing that to get rid of the T(n/2) in the recurrence to make the math easier

[haughty mountain]

right, you make a guess to get something you can more easily solve

[fiery cosmos]

one step up the recurrence invocation 🧠

alright i guess that's all for me today, gonna take a break my brain is frazzled. hopefully this will all sink in

it feels like ive been stuck on the same stuff for a month

[fervent canyon]

please teach how to keras

is there shame in making a python gui for nmap and put it on my repository to show off to potential employers

[woeful hinge]

i have a question like ,i was solving exercise question from a textbook ,there i got a question where it asked me to do a factorial there are soo many ways to do it when i searched in the net and i got confused ,so my question is as a beginner where do i draw the line this is enough for now or else i would be looking at different answers for whole day ,i don't want to waste my time

[edgy gazelle]

study as much as you need or are interested;
every algorithm problem you will ever run into will have multiple solutions; different ones will run more efficiently than other ones depending on the situation;
other constraints such as space may pose additional constraints

generally reading from good (modern) textbooks ensure you that you are at least exposed to the most useful algorithms, and if a specific problem needs further optimization, you can do your own additional research from there on

algorithm complexity/efficiency may give you more insight into these things

[quartz stone]

Does anyone know if Elements of Programming Interview book is suitable for beginner who has never taken Data Structure and Algorithm before?

Are there any courses on DSA in python?

I want to study DSA first then start doing leetcode. I don't have a CS background

[woeful hinge]

thank you sm for that detailed explanation

[edgy gazelle]

1. I haven't read the book, sorry.

2. Most DSA courses will unfortunately be in Java, as it was widely popular and is simpler than C++, more common among competitive programmers due it to its general faster speed. Python is extremely slow in comparison, so you likely won't see many rip. https://usaco.guide/ is a great free resource that has many Python examples and offers a roadmap-styled resource. Bronze/silver should be good enough for most Leetcode problems imo. [MIT 6.006 has many Python examples and is pinned in this channel.]

[coral sigil]

what does this line do?

[quartz stone]

Thanks for this. The link looks great.

[quartz stone]

Would you still recommend using python to study DSA and leetcode with the ultimate goal of getting a job at one of the companies that do leetcode style questions?

or would it be better to learn java and practise it using java?

[plain fiber]

how to create the CONCAT list

all i can think of is double loop

[fiery cosmos]

You shouldn’t need a double loop to do this

[plain fiber]

alternate approach?

[fiery cosmos]

Let me hop on my pc

[agile sundial]

just do ARR * K

[fiery cosmos]

concatedarray = []
array = [0,-1,2]
k=3
for x in range(3):
        concatedarray = array*k

print(concatedarray)

[agile sundial]

just ditch the loop

[fiery cosmos]

you could also write it like a function that takes as input the array and the integer k and returns the new array

[plain fiber]

yeah loop is not needed

i just did it

[fiery cosmos]

right

[fiery cosmos]

i wonder what the searching algorithm is in the upper right hand corner

[haughty mountain]

the discord one? whatever it is it's pretty terrible

very hard to find exact matches

[fiery cosmos]

like, does it just go through line by line and search every x word combination for the phrase

[haughty mountain]

speaking of bad search stuff, github is also really terrible. phrases I know exist don't show up in searches

[fiery cosmos]

i would think github would be among the best, what with all the knowledge there on the subject

[haughty mountain]

you can do smart precomputations, e.g. precompute what posts contain certain ngrams (sequences of n characters)

https://en.wikipedia.org/wiki/Trigram_search

[fiery cosmos]

i'm going to start a career discussion in the other chan

[haughty mountain]

issues probably get fixed over time, but I've found github search very unreliable

[fiery cosmos]

lol the deepfried memoji

[tepid bolt]

int[] ans = new int[m*n] how to write the same in python?

[lament totem]

probably just ans = [0] * (m * n)

It's an array of integers right?

@tepid bolt

if you use numpy, you can also do ans = np.array(shape=(m * n))

[vocal gorge]

zeros. array converts an array-like input to an array.