algos-and-data-structs

[haughty mountain]

the definition would just be def bs(A, l, r) (using my preferred letters for a range)

then you can call that like I mentioned earlier

[fiery cosmos]

Maybe post the problem statement if there is one?

[haughty mountain]

bs(A, 0, len(A))

err, I need some predicate argument as well if that's supposed to be a binary search

but you get the point

[fiery cosmos]

so i'm trying to implement from the pseudocode

so p and r are not the beginning and end but the first and last index in the array i'm seeing

[haughty mountain]

yes, they use inclusive indexing (which I hate)

[fiery cosmos]

they don't ever define them explicitly..

i have to tell the computer that the beginning and end of the array indices are equal to some things

[haughty mountain]

when you first call the function yes

[fiery cosmos]

like they are not declared as variables anywhere...

[haughty mountain]

they are parameters though

[fiery cosmos]

so i think in order to implement this i'd have to look at the length of the array beforehand and know what the last index would be and pass it in as an argument

how would i make it more self-contained?

[haughty mountain]

def quicksort(A, p, r):
  if p < r:
    q = partition(A, p, r)
    quicksort(A, p, q-1)
    quicksort(A, q+1, r)
```which you then call like
```py
quicksort(A, 0, len(A)-1)

ah, yes

[fiery cosmos]

or have like ```py
def quicksort(A, p=0, r=None):
if r is None:
r = len(A)-1
...

[haughty mountain]

I think this is much cleaner

def quicksort_impl(A, p, r):
  if p < r:
    q = partition(A, p, r)
    quicksort_impl(A, p, q-1)
    quicksort_impl(A, q+1, r) 

def quicksort(A):
  quicksort_impl(A, 0, len(A)-1)

you could also write it as a closure which is pretty neat and self contained

def quicksort(A):
  def quicksort_impl(A, p, r):
    if p < r:
      q = partition(A, p, r)
      quicksort_impl(A, p, q-1)
      quicksort_impl(A, q+1, r) 

  quicksort_impl(A, 0, len(A)-1) 

if I ever write stuff like recursive dfs a closure is super nice, you can avoid passing a bunch of parameters around

[haughty mountain]

case in point, you don't need to pass A to the closure here

def quicksort(A):
  def quicksort_impl(p, r):
    if p < r:
      q = partition(A, p, r)
      quicksort_impl(p, q-1)
      quicksort_impl(q+1, r) 

  quicksort_impl(0, len(A)-1)  

but regardless, separating the recursive impl from the user api is a good idea

[fiery cosmos]

ok thank you

nope im confused lol

[haughty mountain]

what in particular?

[haughty mountain]

fwiw, this is probably the sensible version to look at

[fiery cosmos]

I’m looking over it

[fiery cosmos]

i think that's getting away from the pseudocode a bit much for me

this is what i have so far:

arrayA = []
for num in range (1,51):
    arrayA.append(num)

#print(arrayA)

def quicksort(array, p, r):
    if p < r:
        q = partition(array, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def partition(array, p, r):
    x = array[r]
    i = p-1
    j = p 
    for num in range(j,r-1):
        if array[j] <= x:
            i += 1

quicksort(arrayA, 1, 50)

now when they say "exchange", i'm not sure how to swap elements. i cannot simply declare one equal to the other

or can i?

no

the second variable declaration wouldn't be accurate then

[haughty mountain]

python has nice syntax that works here

a, b = b, a

[fiery cosmos]

i am aware i am setting out to sort a sorted array, i'll change that

[agile sundial]

in other langs you need a temp variable

[haughty mountain]

if you write it out one thing at a time you would need

tmp = a
a = b
b = tmp

[haughty mountain]

unless they have a swap function

or similar

[fiery cosmos]

ok i've formatted it as such:

[agile sundial]

fair enough

[fiery cosmos]

array[i], array[j] = array[j], array[i]

[haughty mountain]

yeah, that works

[fiery cosmos]

ok so i see a return i+1, what is that returning and where would i put my print statement to return the sorted array

[haughty mountain]

it's returning an index

the index where the pivot element you picked ended up after the partitioning

[fiery cosmos]

lol this is great the code is like partially working like sorting some elements and not others and returning the array a bunch of times

kind of funny

[haughty mountain]

[2, 5, 1, 3, 4]
e.g. pick pivot 4 and partition
[2, 1, 3, 4, 5]
 -------  ^  -
 smaller  | bigger
          |
     pivot, index 3

3 would be the thing returned from partition

[haughty mountain]

also, you will not return the sorted array

you are modifying the array/list you pass as argument

[fiery cosmos]

the sorted array = the modified array (which has been sorted)

[haughty mountain]

it's a bit like calling .sort on a list

[fiery cosmos]

so the original list ceases to exist?

[haughty mountain]

A = [...]
A.sort()
# A is now sorted

[haughty mountain]

no, it's edited in-place

[fiery cosmos]

i mean the original ordering is lost

[haughty mountain]

it's the same list, the elements inside have just been moved around

[haughty mountain]

yes

[fiery cosmos]

right ok

alright here's what i've got:

arrayA = [0,10,41,22,79,56,47,32,101,17]
# for num in range (1,51):
#     arrayA.append(num)

#print(arrayA)

def quicksort(array, p, r):
    if p < r:
        q = partition(array, p, r)
        quicksort(array, p, q-1)
        quicksort(array, q+1, r)
    return print(array)

def partition(array, p, r):
    x = array[r]
    i = p-1
    j = p 
    for num in range(j,r-1):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i+1], array[r] = array[r], array[i+1]
    return i+1

quicksort(arrayA, 1, 9)

wait

i'm declaring q = partition before it exists 😵‍💫

https://tenor.com/view/facepalm-annoyed-stöhn-oh-no-oh-nein-gif-24943313

[haughty mountain]

quicksort(arrayA, 0, len(arrayA)-1)

[vocal gorge]

i'm declaring q = partition before it exists 😵‍💫
no? partition is defined before quicksort is called

[rose flicker]

Here was my attempt at this. I think the problem is in my cost_container function. It returns a list 11 items long with the value 17. https://paste.pythondiscord.com/sogukuwuwe

It should return a unique value for each bin

[opal oriole]

Python will run top down, defining both quicksort and partition, then quicksort is called, at which point partition must have been defined or it will error (it was defined).

So partition does exist before q.

[rose flicker]

The goal is to assign a "cost" to each bin in the container_cost function and then set the solver to minimize the cost.

[opal oriole]

If this were C instead of Python, you have issues. Because it does not check at runtime if stuff is defined (declared actually) and the order matters.

[fiery cosmos]

thanks all

[tacit nova]

any tips on how to practice big O ?
like I have some good understanding, but I still couldn't write a correct space/time

[haughty mountain]

take some simple algos and try to analyze them?

[fiery cosmos]

pop quiz find the big O's (if you want some practice and I bet we can help if you're stuck)```py
def quiz1(arr, value):
return arr.index(value)

def quiz2(n: int):
data = list(range(n))
return sum(data)

def quiz3(n: int):
while n > 1:
n //= 2```

[tacit nova]

|| quiz 1 O(n) -> O(n) simply because finding value takes n time||

|| quiz 2 O(3n) -> range is O(n), to create/copy a list is O(n), and to find sum is the third O(n)||

|| quiz 3 O(logn)-> I actually don't know why, I just know in Divide-and-Conqueror is O(logn) because the value keep decreasing by half each time, so im guessing the same here ||

also i love practices like this, that's why this is my fav site https://pgexercises.com/questions

[agile sundial]

range is actually constant time

[coarse cipher]

what are some good free courses for learning DSA from absolute scratch

[jolly mortar]

the last one is log n because how many times you can halve something before you reach 1 is exactly what log (base 2) is

[haughty mountain]

More challenging one

def sieve(n):
  is_prime = [True]*n
  for d in range(2, n):
    if is_prime[d]:
      for i in range(d**2, n, d):
        is_prime[i] = False

not so hard, show that it's ||O(n log n)||

harder, show that it's actually ||O(n log log n)||

the latter bound requires a basic number theory result ||density of primes||

[vocal gorge]

||This is exact-lish a sum 1+1/log(d)*(n-d^2)/d over d in range(2,sqrt(n)).||
|| Each term is at most 1 + n/d which when summed gives O(n + n log(sqrt(n))) = O(n log(n))||, giving the simpler bound.
And to get the fancy bound, I guess you need to somehow evaluate ||sum (k^2-d^2)/(d log(d)), d=2 to k (where k^2=n is, let's say, some integer)|| which I don't see how.

[iron pollen]

is there any similar function in python.
to release a variable from its value

[agile sundial]

no

[vocal gorge]

I mean, there's the del keyword which does what you said, but it has very little to do with C's free, which unallocates memory.

[modest breach]

If im calling a function that takes O(i) inside a for loop. What would the O notation of the loop be since the work grows by 1 each time? Still O(n) ? or im assuming something slower

[haughty mountain]

Right, let's ignore the is_prime check and the d**2 (the d**2 doesn't matter for the asymptotics, it turns out)

Then the number of iterations in the inner loop is basically n/2 + n/3 + n/4 + ... which is O(n log n)

The harder bound comes from that we have the is_prime check, we actually compute the sum(n/d for d in primes). A bit non-strict argument is that the "probability" of some number n being prime is 1/log(n) (which you included in your expression)

sum(n/(d*log d) for d in range(2, n)) =
n*sum(1/(d*log d) for d in range(2, n)) =
```the sum is indeed a bit annoying, but we can bound the sum it by an integral of `1/(d log d)` instead and (no surprise) `log(log(d))` is the primitive function.

Chain rule go brrr:

(log log d)' = 1/(log d) * 1/d = 1/(d log d)

[haughty mountain]

this might help

1 + 2 + 3 + ... + n = (n+1) n / 2

[dark aurora]

What is the time complexity of sorting tuples

a, b = [1, 3, 6, 7, 9, 10], [(3,4), (7,2), (5,1), (3, 10)]

is the time complexity of sorted(a) the same as sorted(b)

[haughty mountain]

the second scales in the length of the tuples

i.e. comparison isn't really O(1)

O(n log n * cost of comparison)

[dark aurora]

but if there was for example a list of tuples of size 2 most would compare the first two nums and only if they are the same compare the second pair so the time would be really close to array of just integers, wouldn't it?

[haughty mountain]

if your input tuple is exactly 2 then comparison is O(1), but imo that doesn't tell the whole story

e.g. it's quite common for string algos to scale with the size of the alphabet, leaving that out is a pet peeve of mine

or the length of the string, e.g. for dict, hashing a string is O(len(s))

[haughty mountain]

if you have k long tuples I can give you cases where I force you to make cost O(k) comparisons

[tacit nova]

ye i can't solve this 😂 i will read yr explanation later

[half lotus]

Wikipedia states the time complexity for Dijkstra's with a binary heap is Θ((|E| + |V|)log|V|). Does this mean that decrease-key and extract-minimum are each Θ(log|V|)? On Wikipedia it states they're O(log|V|), and I couldn't find anything giving a tight bound. It doesn't seem right to change an upper bound to a tight bound. Am I missing something?

Actually, extract-minimum should be O(1) 🤔

Or maybe extract min means find it O(1) and then remove it which is O(log n)

[tacit nova]

i think getMin is O(1), remove + heapify is O(logn), add + heapify is O(logn)

my understanding :
example in a min heap
with H as Height of binary tree
and N as total of nodes
H = logN

when you add a 3, it will be inserted in the bottom of the heap
from that node 3, you will swapping with the parent if node 3 is smaller
you will swap H times (worst case)
heapify is then O(H)
which is the same as O(logn)

[half lotus]

That doesn't answer my question. My question is about how a tight bound can be given for Dijkstras in this case rather than an upper bound.

[tacit nova]

my mistake

[half lotus]

Or rather, if the tight bound for Dijkstras implies tight bounds for binary heap operations too.

[fiery cosmos]

i still haven't figured how to handle these pseudocode statements:

for j = p to r-1:
  do something```

when they declare a variable in the loop header in this manner, i'm assuming they want the value of j or p changing at each step?

i tried to implement it like this:

[jolly mortar]

for j in range(p, r)

[fiery cosmos]

def partition(array, p, r):
    x = array[r]
    i = p-1
    j = p 
    for l in range(j,r-1):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i+1], array[r] = array[r], array[i+1]
    return i+1```

[fiery cosmos]

this worked thx

now i just need to figure why its printing the array so many times

i wrote a working quicksort!!!

[fiery cosmos]

how do i import features of random such as choice or sample

they aren't working for me, i'll check which python i have

3.10

[agile sundial]

you just import random; random.choice(a_sequence)

[meager jetty]

FYI base64 encoding first version ... ```py
b64S = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

def b64Encode(ss):

bb = []
st = 1
for b in bytes(ss,'ascii'):
    if st == 1:
        st = 2
        x = (b & 0b11111100) >> 2
        bb.append(b64S[x])
        x = (b & 0b00000011) << 4
        continue

    if st == 2:
        st = 3
        x = x | ((b & 0b11110000) >> 4)
        bb.append(b64S[x])
        x = (b & 0b00001111) << 2
        continue

    if st == 3:
        st = 1
        x = x | ((b & 0b11000000) >> 6)
        bb.append(b64S[x])
        x = b & 0b00111111
        bb.append(b64S[x])
        continue

if st == 2:
    bb.append(b64S[x])
    bb.append('=')
    bb.append('=')

if st == 3:
    bb.append(b64S[x])
    bb.append('=')

s = ''.join(bb)
return s

from https://en.wikipedia.org/wiki/Base64

[fiery cosmos]

The bit shift operator exists in python?

[haughty mountain]

yes, << and >>

[dark aurora]

Is there a faster way to sort these lists of tuples and input them

than this

n = int(input())
ranges = []

for j in range(n):
    x, y = input().split()
    ranges.append((int(x), int(y), j))

rangs = sorted(ranges, key=lambda x:(x[0], -x[1])) #sorting non reverse by x and reverse by y
rangsr = sorted(ranges, key=lambda x: (x[1], -x[0])) #sorting non reverse by y and reverse by x

[agile sundial]

you might get better speed by doing sys.stdin.read() instead of input()

[fiery cosmos]

Anyboyd know how I might change my lists (for alps, bets example in this) to numpy arays without messing my code? https://paste.pythondiscord.com/cosayarone

[brazen dock]

this algo is valid only if the head of linked list contain a head and i dont want to add an if statement into it to make it work if there is another way. i would be happy if someone explained me that

[shut breach]

wdym by "the head of linked list is given"?

[brazen dock]

first Node (if linkedlist contain a head)

[shut breach]

how could a linked list not have a head

you mean like it's empty?

[brazen dock]

suppose i have made an empty linkedlist (I'm new to DSA)

[brazen dock]

yep

i have solved the issue by this but im looking for something better

[shut breach]

not having a first element is sort of a special case of being at the end of the list

and you already have a while loop for detecting when you're at the end of the list

so it comes down to rewriting the loop to work with that first check

[brazen dock]

meaning my implementation is fair enough?

[shut breach]

just needs to be tweaked

[brazen dock]

thank you I'll work on it

[tacit nova]

is using self.listA worse than simply listA in performance?
cause honestly passing var to function (especially in recursion) is confusing

[hot oar]

ROBERTO

[agile sundial]

technically yes, but it's just so minor it shouldn't really be a concern

[brazen girder]

So I recently did a lot with matrices in python (using nested arrays) and wanted a cool way to print them, so i wrote this function:

def printMat(mat, label=""):
    mxcol = max([len(str(e)) for r in mat for e in r])
    m = [[str(e).ljust(mxcol) for e in r] for r in mat]
    if label: print("\033[1;34m" + label + "\033[0m")
    print("┌" + f"{len(mat)}x{len(mat[0])}".center(len(m[0]) * (mxcol + 1) + 1, "─") + "┐")
    for r in range(len(m)): print("│", *m[r], "│", sep=" ")
    print("└" + "─" * (len(m[0]) * (mxcol + 1) + 1) + "┘")

It shows a lovely rectangle at the end ^^

Optional Label
┌──4x3──┐
│ 4 8 1 │
│ 3 7 1 │
│ 2 6 1 │
│ 1 5 9 │
└───────┘

Just thought I'd share it because I found it very useful :)

[haughty mountain]

nice, I've done a lot of similar stuff as well, quite useful

nit: when printing ints you probably want rjust to align ones/tens/hundreds/...

also less known f-string feature, variable sizes

f'{e:{mxcol}d}'

[lament totem]

That's pretty nice!

Now make it work for 3d 😛

[haughty mountain]

couldn't resist some small refactoring + some of that fun f-string usage that people might not know about

def printMat(mat, label=""):                                                    mxcol = max([len(str(e)) for r in mat for e in r])
    m = [[f"{e:{mxcol}d}" for e in r] for r in mat]
    width = len(m[0]) * (mxcol + 1) + 1
    size = f"{len(mat)}x{len(mat[0])}"

    if label: print(f"\033[1;34m{label}\033[0m")                                print(f"┌{size:─^{width}}┐")
    for r in m:
        print(f"│ {' '.join(r)} │")
    print("└" + "─" * width + "┘")

this one in particular is fun

f"┌{size:─^{width}}┐"

[brazen girder]

okay wow thats some magic i dont understand ^^

[haughty mountain]

^ means center (< and > are left and right justify)

these can be preceded by a padding character, or default to space

[brazen girder]

Ahh thats a pretty neat feature

[haughty mountain]

it's quite powerful

[brazen girder]

i added a bit to your implementation so other types than ints are supported as well:

def printMat(mat, label=""):
    mxcol = max([len(str(e)) for r in mat for e in r])
    def format(e):
        if isinstance(e, int): return f"{e:{mxcol}d}"
        return str(e).rjust(mxcol)
    m = [[format(e) for e in r] for r in mat]
    width = len(m[0]) * (mxcol + 1) + 1
    size = f"{len(mat)}x{len(mat[0])}"

    if label: print(f"\033[1;34m{label}\033[0m")
    print(f"┌{size:─^{width}}┐")
    for r in m: print(f"│ {' '.join(r)} │")
    print("└" + "─" * width + "┘")

If for some reason you want to mix weird types together, this will at least not crash but its kinda ugly because it aligns strings to the right

[haughty mountain]

the ability to have arguments on the formatting side {width} in this case is also very powerful, and a feature relatively few people probably know about

[fiery cosmos]

could someone help me to understand whats going on in the cut-rod problem in CLRS, section 15.1, i'll write the code here:

CUT-ROD(p,n):
  if n == 0
    return 0
q = -infinity
for i = 1 to n
  q = max(q, p[i] + CUT-ROD(p, n-i)
return q```

that's the pseudocode

p is an array of prices p[1...n]

n is the rod length

i can see that its recursively computing every subproblem. i don't understand the function that initializing q to -infinity has or its impact on the q = max statement

[dark aurora]

Is there a solution to this problem in python?

https://cses.fi/problemset/task/1641/

My solution is O(n**2) but it doesn't pass the time limit

[fiery cosmos]

i'm going to venture a guess and say you could make it with some sort of recursive implementation, but i'll let an expect weigh in on the manner

wouldn't the 1.00s time be impacted by the speed of your machine?

[agile sundial]

it's not run on your machine

[fiery cosmos]

ah. figured

[agile sundial]

i don't remember this problem specifically, but think of what else you would initialize q with. it may be that for any finite initial value of q, you could construct a test case where the max value happens to be your initial value, which would be incorrect

[agile sundial]

send code? i'm not sure if you can do better than O(n^2) 🤔

[dark aurora]

from sys import stdin
 
input = stdin.readline
 
n, k = list(map(int, input().split()))
lst = list(map(int, input().split()))
dic = {}
 
sums = []
indx = []
 
for i in range(len(lst)):
    dic.update({lst[i]:i})
    for j in range(len(lst)):
        if i!=j:
            sums.append(lst[i]+lst[j])
            indx.append((i, j))
 
 
num1, num2, num3 = -1,-1,-1
rez = False
for i in range(len(sums)):
    j = k-sums[i]
    if j in dic:
        temp1, temp2 = indx[i]
        if dic[j]!=temp1 and dic[j]!=temp2:
            num1, num2, num3 = temp1, temp2, dic[j]
            rez = True
            break
           
 
if rez:print(num1+1, num2+1, num3+1)
else:print("IMPOSSIBLE")

[agile sundial]

hmm, you could make some optimizations, for example in your for loop, instead of starting the second range at 0, you could do range(i + 1, len(lst)), which saves a constant factor

instead of dic.update({lst[i]:i}), which unnecessarily creates a dict, you could just do dic[lst[i]] = i

actually wait, dic is basically just dict(zip(lst, range(len(lst)))), which should be faster than putting it in the loop

[dark aurora]

yeah, I think using a hashmap may be even faster than using a dict, but I checked the time and it would give me the TLE just for the nested loop which makes the sums (without any code further) so I don't think solution O(n**2) is viable, but I see a lot of python solutions even though I don't know how they coded it

[agile sundial]

python's dict uses a hashmap

[jolly mortar]

which saves a constant factor
does it not count as a quadratic factor
n^2 - (n^2+n)/2 = O(n^2)

idk

[agile sundial]

uh

[tacit nova]

so i have list of intervals, and I want to output a list of non-overlapping intervals
input : [[1,3],[2,6],[8,10],[15,18]]
output : [[1,6],[8,10],[15,18]]

intervals.sort()      
i = 0 
while i+1 < len(intervals) : 
  first, second = intervals[i], intervals[i+1]
  if first[1] < second[0] : # no overlapped
      i += 1 
  else : # overlapped
      intervals[i] = [ min(first[0], second[0]), max(first[1], second[1]) ]
      del intervals[i+1]      
return intervals

what's the run time on this ? n is number of intervals
sorting : O(nlogn)
looping and del : O(n) * O(n)
so total is : O(nlogn) + O(n**2) ?

[agile sundial]

so it would seem

your final result would be O(n^2)

you can do better, though

[fiery cosmos]

how do y'all implement binary trees, with classes?

[agile sundial]

yeah, classes can work

[tacit nova]

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

[fiery cosmos]

is that the most straightforward way?

[agile sundial]

yeah, imo

[tacit nova]

my approach is time O(n^2), space O(1)
official solution is time O(nlogn), space O(n) with an extra 'merged' list, you mean that ?

[agile sundial]

yeah

technically, you're still using O(n) space on cpython, since list.sort needs extra space

[tacit nova]

yea i saw it and understand it https://leetcode.com/problems/merge-intervals/solution/

[tacit nova]

because it will return another list, with different id() right ?

and it's better if i do ?

intervals = sorted(intervals)

[agile sundial]

no, the list is the same with list.sort, it's modified in place

the algorithm needs to maintain extra space internally

with sorted, you are getting a new list

[tacit nova]

ah so no matter how i sort, it's space O(n), thanks

[tacit nova]

so if an interviewer asks me "what's the big O", i would say speed O(n**2) and space O(n) then

[agile sundial]

yeah, but be prepared to defend the space one lol

[tacit nova]

how do i do that ?
also python.sort is using which algorithm in this list ? merge sort or tim sort lol ?

[agile sundial]

timsort

which is a modified mergesort

[tacit nova]

found it, im gonna read this, thanks

[agile sundial]

how do i do that ?
explain why your answer is what it is

you can read more about it specifically in listsort.txt which is somewhere on cpython's github

[fiery cosmos]

where can this graph be found

[agile sundial]

https://www.bigocheatsheet.com/

[fiery cosmos]

bookmarked, thank you

trying to understand this binary tree implementation

i gave up on dynamic programming (for now), wasn't making sense to me

i'd paste it here but its 58 lines

[agile sundial]

use a pastebin

[fiery cosmos]

well its from stack overflow so i can just paste that article

https://stackoverflow.com/questions/2598437/how-to-implement-a-binary-tree

[agile sundial]

which part?

[fiery cosmos]

i mean, it's difficult to visualize exactly whats going on, maybe i just need to read it some more

like line 17 and 18:

        else:
            self._add(val, self.root)```

let me try to convert to english

lines 14 through 16 define a function called add and pass it the required argument self and one input value val, and if there is no root (the tree is empty), assign the input value to the root

and if the tree is nonempty, to do another function called _add

i don't get the self.root bit

[agile sundial]

it's the root node

[fiery cosmos]

right i see now why they are passing it along to _add. i don't understand how the .v extensions work, i see they were defined under initializing the Node class

[agile sundial]

it's accessing an attribute. this attribute stores the value of the node

[fiery cosmos]

ok. i'm now looking at their print statement vs. CLRS inorder tree walk algo

must all the self statements be followed by a . for proper syntax?

[agile sundial]

self is a reference to the object you called the method on

[fiery cosmos]

ahh ok ok

[opal oriole]

In Python: py my_object.do_thing(x, y, z) In C (or Python without using classes): c do_thing(my_object, x, y, z) self is the my_object, Python has the object.method syntax. It's so that you get subject.verb() which matches English more than verb(subject).

(SVO word order)

[fiery cosmos]

is .verb in this case a built in method or something the user is defining

[agile sundial]

could be either

for example, list.sort is a built-in method

[fiery cosmos]

i mean in the context of classes

[opal oriole]

Classes also come with some hidden methods by default, that you can modify too.

[agile sundial]

list is a class

[fiery cosmos]

oh!

[opal oriole]

Python has everything as an object.

[fiery cosmos]

what exactly does that mean

i'm taking it all objects have certain attributes

what do other languages have things as if not objects

[agile sundial]

some languages have primitives, for example java, which are just the data, no attached methods

[opal oriole]

>>> (3.1).__ceil__()
4
>>> 

>>> (2).__mul__(4)
8
>>> 

etc

[fiery cosmos]

waoh

[opal oriole]

Python uses double underscore notation for private / hidden / special stuff.

It's just a method though.

__init__ is a method that is special too.

Yeah.

[fiery cosmos]

a method on the object of type int? in this case

[opal oriole]

>>> type(int(3))
<class 'int'>
>>> 

[fiery cosmos]

wow that's so interesting i never thought of integers as objects in python

[opal oriole]

Or just 3, because it's an int by default.

[fiery cosmos]

oh since i have y'all here, how would i do trace / test runs in vscode

[opal oriole]

Yeah Python does the whole everything is an object thing which a few other languages do too.

[opal oriole]

With the Python plugin there should be a debugger.

[fiery cosmos]

object oriented yeah

now i know what it means

[opal oriole]

You can be OOP without everything being an object, it's a special kind of OOP language.

[fiery cosmos]

ok. does most everything in python have inbuilt methods / functions? like every object type / class?

[opal oriole]

>>> dir(int)
['__abs__', '__add__', '__and__', '__bool__', '__ceil__', '__class__', '__delattr__', '__dir__', '__divmod__', '__doc__', '__eq__', '__float__', '__floor__', '__floordiv__', '__format__', '__ge__', '__getattribute__', '__getnewargs__', '__gt__', '__hash__', '__index__', '__init__', '__init_subclass__', '__int__', '__invert__', '__le__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__round__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__setattr__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', '__truediv__', '__trunc__', '__xor__', 'as_integer_ratio', 'bit_count', 'bit_length', 'conjugate', 'denominator', 'from_bytes', 'imag', 'numerator', 'real', 'to_bytes']
>>> 
``` I think so. But maybe there is one that has nothing. Doubt though. It would still be an object even if it has no methods.

[agile sundial]

they all inherit from object, though, which has methods

[opal oriole]

Yeah I just was not sure if in the implementation there was some special non-object objects.

But you can just assume they all do.

For simplicity (won't come up ever).

[fiery cosmos]

how did y'all learn so much? did you read the python documentation

[opal oriole]

Yes, and read the implementation source.

(And tried implementing my own languages before, so I have some idea of the patterns)

[fiery cosmos]

i'd love to focus more heavily on CS side of things. bioinfo has been really annoying (have to learn one thing then walk away)

thanks all for info

[opal oriole]

I think implementing a language is something that becomes part of many CS student's paths at some point.

(And on their own because it's fun)

[fiery cosmos]

it'd be great for comprehension purpose

[vestal citrus]

I have a directed graph with weighted edges (simple example in attached image). The graph is organized into a hierarchy. Given this, I have a “demand vector” where quantities correspond to nodes. How would I find the level 2 node values by having the values of nodes in higher levels “trickle down”? Sorry if my explanation is unclear.

I thought of using an adjacency matrix to represent the graph and then cubing it, but my implementation does not work if the demand vector has 0s for nodes at the top level. Any help is appreciated!

[vocal gorge]

I don't quite get the problem. What do the demand numbers for top-level nodes (A,B) mean, for example?

or for the other nodes, for that matter - e.g. I see that C has 1 flowing into it, but 4 flowing out of it, and has a demand of 2?

[vestal citrus]

The nodes represent items and the edge weights represent quantities needed to make those items. For example, you need 3 of H to make 1 of F, 3 of F and 1 of G to make 1 of C, etc. In retrospect, I should’ve reversed the order of the arrows. For this example, the problem is this: if I need 1 of A, 2 of C, 1 of D, 1 of E, and 1 of H, how much of F and G would I need in total?

[vocal gorge]

Oh, I see now.

I don't get how you make 1 H (as the demand vector requires) without using any H-es, but only Fs and Gs.

[vestal citrus]

H is excluded

because it’s in a level below the one you want to calculate for

[worn laurel]

HELP

[vestal citrus]

Make sure discord.py is installed by running the pip command. If it is, restart VS Code.

[vocal gorge]

So the value of H in the demand vector just doesn't matter here? Okay then

[worn laurel]

I've already done it and nothing

[fiery cosmos]

what would python import discord do

[worn laurel]

imported

[agile sundial]

this doesn't really fit in this channel

[vocal gorge]

Seems straightforward-ish then. You store, for each node, how much of that node is needed.
You start with the top-level nodes. Their counts is equal to their demand: so 1 A and 0 Bs.
Then for each of the level-3 nodes, you consider all level-4 nodes that need thing node to produce, plus the node's demand. For C, say, the count needed is 2 (demand) + 1(count of A)*1(Cs needed for one A). So the count of C needed is 3. For D it's 1+1*2=3, for E it's 1 + 0*1=1.
Then the same with level-2 nodes. For F you need 0 (demand) + 3(count of C) * 3(Fs per C) = 9, for G you need 0 (demand) + 3(count of C)*1(Gs per C) + 3(count of D)*2(Gs per D) = 9.

I think it'll even be pretty fast, something like O(E).

Actually, it can also be represented in linear-algebra fashion if instead of considering the full adjacency matrix, you split the graph into matrices connecting layers.
E.g. from level 4 to level 3 we have this linear tranformation, represented by a 3-by-2 matrix:

  A B
C 1 0
D 2 1
E 0 1

Then to get the layer-3 counts from layer-4 counts, we can do layer_3_counts = layer_3_demand + transition_mat@layer_4_demand. And so on for every layer until the target one.

[rocky iris]

Hello guys!
What kind of algorithm do I need to follow to collect all the stars?

<@&831776746206265384>

[uneven yarrow]

There was no reason to ping us.

[rocky iris]

sorry 😄

[uneven yarrow]

It's alright. Just call us if there's someone who's acting up or the sever's falling apart.

[vestal citrus]

Thanks! I’ll try to implement your suggestion. My previous solution used the Counter class from collections and iteration through each item (ordered by decreasing level), so I’ll see if the linalg one works out.

[royal apex]

You can try out greedy graph algorithms (Floyd's or dijkstra's ) or maybe DP (tweaked n-queen) might work

[lean junco]

i ran leetcode it gave cirrect answer but when i submitted it gave TLE ? does this also happen? why didnt it showed TLE before??

[ebon heron]

They usually test on small inputs then for the real submit they test on large inputs to test the efficiency and performance as well (not only correctness)

[fiery cosmos]

is learning B-trees in the age of SSDs a waste?

[lean junco]

i custom ran on very same case that gave TLE

[agile sundial]

I'm not sure how SSDs are relevant to the question

[fiery cosmos]

the chapter opens with the idea that B trees are designed specifically to work well on discs, SSDs have no such rotational architecture

[agile sundial]

interesting, I suppose that specific reasoning doesn't hold up then

[fiery cosmos]

i mean, to be fair the sentence also says "or other direct access secondary storage devices"

[agile sundial]

hmm, yeah, that makes a lot more sense

the reasoning is that disk access/io is expensive, so B-trees try to minimize this

it's not that they exploit something in the rotational structure of hard drives

[agile sundial]

your environment isn't necessarily the same, though

[blazing estuary]

Is there a straightforward way of unrolling a recurrent function into an iterable one?

I've always found that it varies case by case, curious if someone has an algorithm to do it for you

[agile sundial]

i'm not sure if you could even write such an algorithm

[fiery cosmos]

i just learned about machine code 😛

[lyric burrow]

so, i'm solving this problem

and i've come up with 2 solutions

there's this

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        checklist = set()
        nums.sort()
        for i in nums:
            if i in checklist:
                return True
            else: checklist.add(i)
            
        return False
            ```

and this

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1,len(nums)):
            if nums[i] == nums[i-1]:
                return True
            
        return False
            ```

i'm not sure which one's better?

[stray fractal]

nvm

didn't see the .sort()

[lyric burrow]

yeah

[stray fractal]

!timeit ```py
def containsDuplicate(nums: list[int]) -> bool:
checklist = set()
nums.sort()
for i in nums:
if i in checklist:
return True
else: checklist.add(i)
return False

from random import randint
n = [randint(-1000000000,1000000000) for _ in range(100000)]
py
containsDuplicate(n[:])

[halcyon plank]

@stray fractal :white_check_mark: Your timeit job has completed with return code 0.

10 loops, best of 5: 31 msec per loop

[stray fractal]

!timeit ```py
def containsDuplicate(nums: list[int]) -> bool:
nums.sort()
for i in range(1,len(nums)):
if nums[i] == nums[i-1]:
return True
return False

from random import randint
n = [randint(-1000000000,1000000000) for _ in range(100000)]
py
containsDuplicate(n[:])

[halcyon plank]

@stray fractal :white_check_mark: Your timeit job has completed with return code 0.

10 loops, best of 5: 29.5 msec per loop

[stray fractal]

@lyric burrow latter is better

[haughty mountain]

why are you sorting in the first one?

also consider something super simple like

return len(set(nums)) != len(nums)

I'm expecting that to be faster

[runic tinsel]

you meant nums[1:] == nums[:-1]

[haughty mountain]

no?

if any adjacent elements in a sorted list is equal, there are duplicates

[runic tinsel]

Yeah

So that would be way faster

More than 2x

[haughty mountain]

how does your thing do the right thing at all?

[runic tinsel]

By being precisely the same thing

Don't look for difference, it's not there

Oh I'm wrong, it's broken

[haughty mountain]

any and a zip would work

but prob not faster

[runic tinsel]

It checks if all elelements are the same

[haughty mountain]

yes

[lyric burrow]

WOAH, that's awesome, never thought of that, thank you

but why does this seem to be slower? @haughty mountain

[haughty mountain]

so, it's slower if there is a duplicate pretty early

but if there are no duplicates (the worst case) it's faster

I see 2-3x faster locally for the non dupe case

in a lower level language the other version is just better

in python you can often make stuff faster by having the main logic not be python, even though it does more work (my short solution)

[winged bough]

I want to learn data structures from where to learn i am beginner

[fiery cosmos]

i learned from an EdX course, python specific. they did not cover stuff like linked lists or binary trees

https://www.edx.org/course/computing-in-python-iii-data-structures

https://www.edx.org/course/python-data-structures

what is the time complexity of python's min() function

googled: O(n)

could one save time by saving a newly computed value as min and then when new values are computed replacing min if the new value is smaller? or would that still result in the same runtime for a given program

[onyx root]

min(a_collection) has to consider every element in the collection, so it's going to be O(n)

[haughty mountain]

yes, min must consider all elements, there are n elements, so min is Ω(n)

and as we have seen we can do it in O(n)

so it's Θ(n)

[fiery cosmos]

what about my question above regarding saving time over theta(n)

what is wrong with my code:

def insertionsort(array):
    for i in range(2,len(array)):
        element = array[i]
        j = i-1
        while j > 0 and array[i] > element:
            array[j+1] = array[j]
            j = j-1
        array[j+1] = element
    return print(array)


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

insertionsort(a)

runs with no errors but doesn't sort. i can see in the very first test of the while loop array[i] is not greater than element

[fiery cosmos]

found it

i'll leave the message up as a learning exercise for others

[haughty mountain]

does your thing consider all values in the input? if yes it's Ω(n), if no it's incorrect

[fiery cosmos]

hi @haughty mountain , any idea how i can get a tracing or logging function going in vscode?

[haughty mountain]

idk much about vscode

[fiery cosmos]

what about some other editor? it's part of my coding assignments that i haven't figured out yet

how to perform tracing/logging to analyze the algorithm's "cost"

cannot be cpu time/clock time

[haughty mountain]

you can always add counters manually, though there are probably better ways

[fiery cosmos]

yeah i do have the option of adding statements to the code directly but i'd rather find an IDE/editor which has a tracing or logging function, i've asked over in that other chan

[keen ivy]

hi how do i write a code block on here?

[haughty mountain]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[keen ivy]

def areaOfSquare(size):
    area = size * size
    return area

print (areaOfSquare(7))

oops, can someone help explain why this works please? as far as i have got is, 1) I define a function with the name areaofsquare, that has a parameter. The there is another variable that is basically the size times the size.

then the function returns area? returns it where though?

[vocal gorge]

To the caller? That's just how functions work. When you have a function f and you call it like f(a), the expression f(a) evaluates to whatever the function returns.

[keen ivy]

i see, so does the name size have to match twith whats in the vaiable area?

[agile sundial]

i'm not sure what you mean by that. you can't use variables that you haven't defined

[keen ivy]

yeah thanks i see,

im still not sure what happens when you return the area,

[agile sundial]

the caller gets the value

[keen ivy]

sorry whats the caller?

the parmaeter ?

[agile sundial]

the thing/person that used the function

using a function is called "calling"

[opal oriole]

areaOfSquare(7) "gets replaced" with what is being returned.

[vocal gorge]

Suppose you have an expression, 5 + 2*f(a) - 10. It's evaluated like this:

• f(a) is evaluated, by calling f with a as an argument. Let's say that f is actually your areaOfSquare and a is 5, then it evaluates to 25.
• 2*25 is then 50
• 5 + 50 is then 55
• 55 - 10 is then 45.

[keen ivy]

thanks man

[keen ivy]

got you, thanks very much

def areaOfSquare(thiscanbeanythingthenreally):
    area = thiscanbeanythingthenreally  * thiscanbeanythingthenreally
    return area

print (areaOfSquare(7))

so really tit doesn't matter what is written in here because they will get replace when you add something in the caller?

its like a placeholder?

[opal oriole]

Yea, a "variable". It "varies" with whatever the "input" is.

[keen ivy]

thanks so much, ithings like this make me question myself sometimes

i know its simple stuff, but can be very puzzling to wrap my head around

sorry to come back with the same query, but i was just playing around here and i found:

def areaOfSquare(big):
    
    return big * big

print (areaOfSquare(7))

you can just write it like this?

so whats the point in defining a variable area?

[vocal gorge]

No point at all.

if you got that example from somewhere, they probably just thought, for some reason, that writing it that way would be less confusing

def areaOfSquare(big):
    return big * big

is what anyone'd write in real applications

[opal oriole]

It might make what is being returned more clear, but it should be obvious from the function name, if the name is good. You may still see that choice made in larger functions.

Other than that, no purpose.

[toxic ivy]

Useful information thanks guys

[fringe zodiac]

will there still be 10 comparisons using an improved sequential search?

[twin vapor]

hey

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:    
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        curr = head
        prev = None
        while curr != None:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        print("Reversed: ", prev)
        print("Normal: ", head)
        if prev == curr:
            return True
        else:
            return False

how do i keep head

[haughty mountain]

what is "improved sequential search"?

[fringe zodiac]

it's where it will stop searching once the target matches the value

[haughty mountain]

huh, I would just call that sequential search, but ok

the value isn't there, so they behave the exact same

[fringe zodiac]

Yeah i realised the maximum number is 20

[haughty mountain]

of course it's not the max that matters, if I asked for 9 it would have been the same story

[fiery cosmos]

will binary searches typically run in log(n) time?

the big O complexity cheat sheet says log(n) for binary search tree, i'm asking however about an array

[jolly mortar]

yes log(n) for arrays too

[tacit nova]

is Google onsite harder than phone ? also what do they expect for L3 entry level ?

[fiery cosmos]

you have interview at google?

[tacit nova]

yesterday yes

[fiery cosmos]

congratulations. that's.. exceptional

also makes me glad i'm doing a deep dive into this stuff 😂

i have a friend who contracted w them, i'll see if he has any input

[fiery cosmos]

@tacit nova getting response now

[tacit nova]

hmm did you just post something, and delete it, and then tag me lol

[fiery cosmos]

i deleted obvious questions about python documentation that i've since figured out. ok his response (admittedly not super helpful and i told him this was post interview not pre):

Onsite is always a lot harder than phone

he should give "Cracking the Coding Interview" a read to learn how to prepare

[tacit nova]

lol, is a lot harder okay
ok i will continue to read the CtCI now

also i just talked to this Google dude

[tacit nova]

he said

and 1 bad round is fine, so i have hope, i'm not that bad 🙂

[fiery cosmos]

i'm somewhat surprised it comes down to such rudimentary things, maybe it's more complex than i'm thinking. i'm not a very gifted programmer

coming up with an algorithm is difficult. the runtime stuff not so much

that being said anyone could give me some code and ask me to analyze the runtime and i'd probably get it wrong 😵‍💫

[tacit nova]

same

[fiery cosmos]

did you go to school for this stuff? i'm working my way through CLRS now but i'm not comp sci undergrad

[tacit nova]

bro i have mock interview with 10 people, and i have to say 8 of them doesn't know how to communicate/ ask questions/ collect edge cases effectively

[tacit nova]

don't shame me 😢 i'm kidding lol, but i forgot all of them.

[fiery cosmos]

oh i'm not i didn't go into undergrad CS cause too much math

[tacit nova]

Zach is L3 at Google, so i think he understands

[fiery cosmos]

just wondering your background. but yes in the professional world you'd be shocked at how poor people are at communicating, been there

what is L3

[tacit nova]

L3 at Google is entry, L4 at Google is more senior, L4 at Amazon is entry
it's complicated

[fiery cosmos]

what's it stand for, lengineer 😂

[fiery cosmos]

can i get someone to help me with my mergesort implementation? i keep getting list index out of range errors

"IndexError: list assignment index out of range"

[agile sundial]

code?

[fiery cosmos]

import math

def merge(a,p,q,r):
    n1 = q-p+1
    n2 = r-q
    left = [0 for x in range(1,(n1+2))]
    right = [0 for x in range(1,(n2+2))]
    for i in range(1,n1):
        left[i] = a[p+i-1]
    for j in range(1,n2):
        right[i] = a[q+j]
    left[n1+1] = math.inf
    right[n2+1] = math.inf
    i = 1
    j = 1
    for k in range(p,r):
        if left[i]<=right[j]:
            a[k]=left[i]
            i = i+1
        if a[k] == right[j]:
            j=j+1

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

    return(print(a))

a = [0,9,5,4,6,2,3,7,1,12,15,48,59,72,83,42,53,62,51,42,15,48,78,85,84,86,95,52,53,62,51,41,42,20,15]

mergesort(a,1,len(a))

the error first occurs on line 12:

left[n1+1] = math.inf

[agile sundial]

n1 + 1 is out of range, since len(left) == n1 + 1

[fiery cosmos]

i thought it would be longer, as handled here?:

left = [0 for x in range(1,(n1+2))]

maybe its only the length that gets populated by the ```py
for i in range statement?

ok, i was able to fix that one by changing the list comprehension statement to begin at range 0. however, i now get the same error on line 17

if left[i]<=right[j]:

perhaps i and j must be changed to zero

nope

[opal oriole]

Python indexing starts at zero, in math they like to start at 1. So if you have some pseudocode that starts at 1, keep that in mind (need to convert).

[fiery cosmos]

yes i am aware. this really ruins things when they have their list indices statements

like ```py
n1 = q - p + 1

type thing

ok so i've got it running with no errors, however it isn't sorting

oh wait

now it's working...

ok thanks all. it's running and really scary fast. i cannot even get a time on it and when i do its around 1ms. not a giant input i know, i'm gonna tinker with some larger n

[agile sundial]

yeah, even bubble sort would crush your input, you need to get to like n=50000

[fiery cosmos]

hmm, i randomly generated an array of length 1000 for testing and ran it again and now its not sorting

super weird

maybe it never was maybe that was my insertion sort window open 🙄

idk what the problem is but it's running with zero errors but also not sorting.

[agile sundial]

that sounds like an error then

[fiery cosmos]

well i mean its not returning any errors but yes clearly something isn't working

insertion sort is sorting an array of 10k randomly generated integers, between 1 and 100k, in ~5.5s

unless i am accidentally also timing the time it takes to generate the array

my mergesort statement looks good, looking back over the merge definition

[fiery cosmos]

my algo is taking 2^n! runtime, is that good?

<this is a joke>

[fiery cosmos]

ok. my failure is the inability to properly convert pseudocode that looks like this:

let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1:
  L[i] = array[p+i-1]

i tried to handle it by making new arrays, and populating them with zeros at the proper length. i always got into trouble with list index assignments out of range later on down the line. so how would i convert this code to python properly?

i tried like this:

    left = []
    for i in range(1,n1+1):
        left.append(array(p+i-1))
``` but no dice

i really don't like their pseudocode for partitioning an input array into two arrays of first and second half, unnecessarily complex

[opal oriole]

range is [) (inclusive, exclusive).

>>> for i in range(1, 12):
...     print(i)
... 
1
2
3
4
5
6
7
8
9
10
11

[fiery cosmos]

i just need a better way of directly converting the pseudocode into the functionally equivalent thing in python... any ideas?

i don't know if what i wrote was functionally equivalent, i don't think it was bc i never incorporated the leftindex[i] statement

i never included the index statement like in the pseudocode

i think there are much easier ways to do this personally but i'm having trouble

[zenith kernel]

if i have an initialized global array M outside my function and set M[x] = -1, for 1 <= x <= i. Anyone know the big o notation for my function? i have it in pseudocode cuz i cant share my code here. ```python
function f(i)
if i <= 3 then
return 1
else
if M[i] != -1 then
return M[i]
else
M[i] = f(i-1) + max{f(i-2), f(i-3)}
return M[i]

[opal oriole]

Your loops should usually start at 0.

"to n" probably means inclusive, but range is exclusive on the end.

However, if you start at 0 instead of 1 you added 1 more iteration.

[fiery cosmos]

how would you convert this pseudocode:

let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1
   L[i] = array[p+i-1]

[opal oriole]

With n1 = 10 I want an array of length 11 right?

(for L)

[agile sundial]

this is my main beef with CLRS, the indexing. it's great for heaps, not so great for everything else

[fiery cosmos]

i mean they do to store the 'sentinel' value, but when i convert directly from their code i always get list index assignment out of range errors down the line. once again my code is now running but not actually sorting anything

a functionally equivalent thing would be simply appending their sentinel value to the end of the list

[opal oriole]

The +1 in length is for the sentinel.

From n.

[fiery cosmos]

does the append statement always add the value to the back of the list?

or like after all existing values i mean

[opal oriole]

Yeah, it appends to the end of the list.

[agile sundial]

i think O(2^N) worst case, when nothing is cached

[opal oriole]

How would you make a list with length n?

(With anything for the values, does not matter)

[fiery cosmos]

list = []
for i in range(n):
  list.append(i)```

[zenith kernel]

how did you get 2^n? i thought its linear since i need to calculate the numbers in M?

[opal oriole]

Ok, and in the pseudocode, what length do they want L to be in terms of n1?

[fiery cosmos]

n1+1

[haughty mountain]

L = [0]*(n1+1)
R = [0]*(n2+1)
for i in range(n1):
  L[i] = array[p+i-1]
```or probably nicer
```py
L = array[p-1:p+n1-1] + [0]
R = [0]*(n2+1)

[agile sundial]

oh, O(n), nevermind. i messed up

[opal oriole]

So same as before, except now n1+1 instead of n for that loop.

[opal oriole]

I will get to this in a bit, but yeah.

[opal oriole]

So with this method, what do you do to get the desired n1+1 length list?

[haughty mountain]

ah, I only now saw that you were discussing it, my bad

[zenith kernel]

@lament totem

i got O(n) as well but he said it wasnt lol

[lament totem]

Who said?

[zenith kernel]

you

[fiery cosmos]

list = []
for i in range(n1+1):
  list.append(i)

[lament totem]

Link the message that made you think I said it wasn't O(N)

[opal oriole]

Yup, now you know how to convert that pseudocode.

[fiery cosmos]

i've been tinkering with it all day and would always get list index assignment out of range errors down the line

[opal oriole]

You also seem to know about list comprehensions. So can you do the same thing with one of those?

[fiery cosmos]

well earlier i had it written as a list comprehension yes, something like:

left = [0 for x in range(n1+1)]

[haughty mountain]

translating 1 indexed code to 0 indexed code is very annoying and error prone, yeah

[opal oriole]

Yup, now, Python also has the ability to repeat a list over and over some N times by using the multiplication operator with a list and a number.

[opal oriole]

See this answer.

[fiery cosmos]

but i'm telling you it'll always lead to list index assignment out of range later in the code

[opal oriole]

We can get to that.

Just make sure everything is all set before that.

[fiery cosmos]

i wish i could go back to the direct interpretation of the pseudocode, let me re implement

which version of my code are you looking at

[opal oriole]

Yeah, you just need to memorize enough of these patterns and think about how going from 1 start to 0 start affects it, and what your end needs to be given that range goes to end - 1 (exclusive), while they do "to" which goes up to it.

Note that going from 1 to 0 and making the end exclusive results in a +1-1 change in number of iterations.

Shifted over 1 (left).

If you are unsure if you are out of bounds, consider the cases of i = 0 and i = end - 1. Would they be out of bounds (given the array length)?

[fiery cosmos]

so like, even if i take out some of their -1 statements its the same. it's like the left array isn't being populated far enough with the array[p+i-1] statement

[opal oriole]

You just need to make sure that minuses don't get you below 0 and pluses don't get you above end - 1.

So i - 1 is suspicious unless something else is added.

(If you are starting at 0)

(Because when i = 0, you would get -1, which is out of bounds)

[fiery cosmos]

i hate what they've done with 1 indexing in this book and adding a computed length plus +1 for their sentinel, it makes it sooo confusing i'

i've wasted all day on this

[opal oriole]

Yeah, it's shifted to the right because it's inclusive AND starts at 1.

[fiery cosmos]

basically i played with it all day until it'd run with zero errors, but then it wouldn't sort

[opal oriole]

And you can see why because summations like n = 1 to N are inclusive.

Like the 1 + 2 + 3 + 4 + ... + N.

[fiery cosmos]

what is shifted to the right my array relative to theirs

[opal oriole]

The indices.

[fiery cosmos]

no mine would be shifted to the left

[opal oriole]

Yeah.

So if you wanted the summation n = 1 to N of i.

What would you do?

(To make it start at 0 and all that)

[fiery cosmos]

why do you mention summation

[opal oriole]

Summations (the captial Sigmas) you see in math are like for loops that keep adding to some total value.

[fiery cosmos]

right

[opal oriole]

But in math they like i to start at 1, and end at N.

Both inclusive.

(Not always at 1, but often)

[haughty mountain]

as long as the limits are finite, sums of series get more weird

[fiery cosmos]

yeah like 1+2+..+n

[opal oriole]

How would do you that sum in Python if you wanted i to start at 1 and how if you wanted it to start at 0?

[fiery cosmos]

all we're trying to do here is split an array tho

we're not adding stuff

[opal oriole]

Yeah, i'm trying to get you used to converting math and pseudocode that deals with 1 start indices and inclusive ends.

[fiery cosmos]

starting at zero wouldn't change anything bc +0 makes the same outcome

but if its a list index

..

[opal oriole]

In this case yes, correct.

+0 does nothing.

[fiery cosmos]

i see what you're getting at. + the 0th element, where the zeroth element is some integer, changes things

[haughty mountain]

I think what is hinted at is, what happens to the loop/sum insides if we shift i=1..N to i=0..N-1

[opal oriole]

Yes, Python wants the latter.

[fiery cosmos]

its the same

[haughty mountain]

sum i=1..N   f(i)
sum i=0..N-1 ???

[opal oriole]

By default range(n) is 0 to n - 1.

[haughty mountain]

what would make these expressions the same?

[fiery cosmos]

damn i really want to go back and understand this in the context of the way i had the code written earlier

[haughty mountain]

basically, if something is ever used as an index it should end up one lower, if it's also used as something that is a non-index that usage should not be one lower

so if I have

for i=1..N
  i*arr[i]
```how would that be translated to python?

[opal oriole]

In programming languages such as Python, indices are not just indices, they are actually offsets. Which is why it starts at 0. You can think of it as being "the start of my array + 0 = the start of my array". But because they are offsets, if you use them as for more than that (as a value / part of a value) they don't align with the math / pseudocode.

[haughty mountain]

||for i in range(n):
(i+1)*arr[i]||

[fiery cosmos]

so this is the most recent and literal interpretation of the code i can find:

import time
import math
import random

def merge(array,p,q,r):
    n1 = q-p+1
    n2 = r-q

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

    left[n1] = math.inf
    right[n2] = math.inf

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

    #return(print(array))

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)

    return(print(array))
    

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

start=time.time()

mergesort(a,0,len(a))

print(time.time()-start)

which runs without error and does not sort

modelling it just like in the book, i get list index out of range statements, which is why where the book says

left[n1+1] = infinity

i had to instead write

left[n1] = math.inf

now i'm realizing i can just append those values to the ends

now i see a bunch of +1's and -1's

which i suspect are my culprits

i definitely need to increment my loop counters so it's not those

the book has i and j =1, if i try that it super breaks the whole thing

how could this be generating a list index out of range:

    i = 1
    j = 1

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

[agile sundial]

remember what you just talked about. if you use something as indices, from the book, you need to decrement it

[opal oriole]

Consider the smallest and largest values for i and j possible.

And the length of left and right.

[fiery cosmos]

alright so once again it is running and producing no errors but not sorting

again i think populating the lists with zeros is messing something up, which i don't have to do but idk how else to handle it

[agile sundial]

code?

[fiery cosmos]

let me try to work in a suggestion from algmyr and i'll post

import time
import math
import random

def merge(array,p,q,r):
    n1 = q-p+1
    n2 = r-q

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

    print(len(left))
    print(len(right))
    
    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 = i+1
        else:
            array[k] = right[j]
            j=j+1

    #return(print(array))

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)

    return(print(array))
    

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

start=time.time()

mergesort(a,0,len(a))

print(time.time()-start)

maybe those loop counters must be inside the loop?

no

[opal oriole]

(n1+1, yet you append inf, which makes n1+2)

[fiery cosmos]

left is populated by the statement:

for i in range(n1):
  left[i] = array[p+i-1]

[agile sundial]

basically, your list comps make a list of length n1 + 1, but your loop only goes to n1, and you also then append the inf

[opal oriole]

And left.append(math.inf)

The +1 on the n1+1 was already meant to hold 1 extra spot for the inf.

[fiery cosmos]

ok so i can do just n1 in both places

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

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

ignore those print statements

[opal oriole]

Did you run it?

[fiery cosmos]

yes

output:

[330, 330, 330, 330, 330, 330, 330, 373, 430, 430, 356, 430, 529, 401, 401, 401, 247, 247, 127, 401, 401, 401, 439, 439, 138, 439, 633, 378, 757, 757, 387, 313, 313, 313, 387, 387, 757, 609, 506, 609, 757, 689, 776, 459, 459, 459, 459, 625, 625, 776, 776, 46, 776, 787, 596, 528, 528, 528, 596, 596, 787, 787, 200, 787, 900, 70, 70, 70, 70, 758, 577, 900, 161, 161, 161, 900, 978, 256, 256, 256, 256, 256, 581, 581, 347, 581, 634, 401, 768, 978, 786, 786, 695, 786, 813, 18, 978, 529, 255]```

[opal oriole]

So lets say p = 0, as it is in the start when you first call mergesort. What does p+i-1 give you?

Your loop is going from i=0 to i=n1-1.

[fiery cosmos]

i could remove the -1 and i still error

[opal oriole]

n1 = q-p+1
n2 = r-q
``` Try drawing an array of length 5 with the values above the indices and show where p, q, and r are on the final merge.

[fiery cosmos]

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)
``` you mean this one:
```py
merge(array,p,q,r)

as shown above?

[opal oriole]

Yes.

What does the p, q, r splitting look like on an array of length 5.

[fiery cosmos]

i mean i have no idea what'd look like at that point after the other calls and the recursions

[opal oriole]

The values are not important / if they are sorted.

[tacit nova]

just heard the news that Google stops hiring for L3 today (not sure for L4, L5)

[fiery cosmos]

no!!!

[agile sundial]

oh no, I guess no one can get a job anymore

[fiery cosmos]

p = 0, q = 2, r = 4

[opal oriole]

Is r = 4 for length 5 array? Look at your code calling mergesort. What values did you pass in for p and r?

[fiery cosmos]

r = 5

[opal oriole]

So what is q-p+1?

And what is r-q?

(What are n1 and n2?)

[fiery cosmos]

so q is computed

[opal oriole]

p = 0, q = 2, r = 5

[fiery cosmos]

no q is 1 bc its 5 mod 2

wait

yes

[opal oriole]

// is integer division

[fiery cosmos]

uh oh

[opal oriole]

>>> 5 / 2
2.5
>>> 5 // 2
2
>>> 

Rounds down.

[fiery cosmos]

yeah thats what i want

[opal oriole]

Yes, so p = 0, q = 2, r = 5.

[fiery cosmos]

wait wait

sorry i want floor division

[opal oriole]

That is what integer division gives you for positive values.

Same thing.

[fiery cosmos]

so for an array of length 5 its making 2 subarrays of length 3 and 3?

[opal oriole]

Yes, but does it make sense to have a left and right half that add up to more than the original length?

[fiery cosmos]

no

[opal oriole]

So there is a mistake.

[fiery cosmos]

ok i tried len(a)-1.. no dice

[opal oriole]

Consider that given an array of odd length, one half must be longer than the other.

The best way you can split length 5 in half is 3 and 2 or 2 and 3.

[agile sundial]

// is just floor division, -5 // 2 == -3

[opal oriole]

Which is why n1 and n2 are two different values, if the halves were always the same length, you would only need 1 value, n1.

[opal oriole]

Ah, ok, forgot python handles it that way.

Passing in len(a)-1 for r is not working because the rest of the code in merge is using r as the end, rather than an index (end - 1).

Consider your loop later: for k in range(p, r)

if r = 5

and p = 0

So you can leave r as len(a), you need to fix the problem in another way.

n1 and n2 are clearly wrong. Because in the example they added up to 6 rather than 5.

When you split into two halves, the halves must add up in length to that of the original.

What if the indices started at 1?

Then p = 1, q = 3, r = 5 (r is still 5).

n1 = q - p + 1 = 3 - 1 + 1 = 3, n2 = r - q = 5 - 3 = 2

So the split is 3, 2.

@fiery cosmos

(You need to adjust for the indexing starting at 0)

[fiery cosmos]

i can't see it

[opal oriole]

The image?

[fiery cosmos]

I cannot comprehend the change I must make

[opal oriole]

Start with an even length, come up with how to compute n1 and n2, then in the case of an odd length, one must be larger, so start by picking which one you want to be the larger one.

Where n1 makes use of p and q, and n2 makes use of q and r.

For example with an array of length 4, what would n1 and n2 need to be?

The actual lengths, regardless of how it's computed.

[fiery cosmos]

2 and 2

[opal oriole]

Yes, so now: ```
2 = some combination of p and q
and
2 = some combination of q and r

Start with the first one.

First what are p, q, and r right now?

[fiery cosmos]

wdym

[opal oriole]

Like in the image above we had p = 0, q = 2, and r = 5.

For an array of length 5.

[fiery cosmos]

i'm sorry i have to step away from this rn

[fiery cosmos]

would anyone know where i would start trying to make a restaurant menu into a json (converting a restaurant menu image to json)

[tight patio]

anyone free helping me find the worst and best case time complexity of a function

[tight patio]

this is the algorithm btw

Algorithm Infect(cell,tomato,infected)

// Input cell of a matrix of n rows by m columns

// Input tomato symbol for tomatoes

// Input infected symbol

//    cells are numbered 1 to nm  so the cell corners of matrix

//    are numbered:     1, m, (n-1)m+1, nm     

//    - verify these corners for a n=4,m=3  matrix

If (cell is within the matrix) then

      If (cell is infected or a blank) then

// do nothing **base case

      Else if (cell has a frog) then

// frog jumps to a new random place and acts

newcell=random spot

remove frog from cell

// frog destroys whatever on newcell

Put frog on newcell

      Else if (cell is a tomato) then

// one step below the cell:  cell + m

 Infect(cell+m, tomato, infected)

 // one step above the cell:  cell - m

 Infect(cell-m, tomato, infected)

 // one step to the left of cell: cell - 1

 Infect(cell-1,tomato, infected)

 // one step to the right of cell: cell +1

 Infect(cell+1, tomato, infected)

     Endif

End if

 End Algorithm

[icy quest]

where should i start DSA?

any good reference book or a yt playlist to learn DSA from?

[haughty mountain]

oh yeah, their indexing standard is atrocious

the merge takes p, q, r which in represents the ranges [p, q], [q+1, r-1]

p, q, r such that it represents ranges [p, q) [q, r) would be so much more sensible

the lengths are p-q and r-q, no ±1 fiddling per case

[haughty mountain]

for the sanity of anyone who wants to try to help, blank lines removed and indented properly

Algorithm Infect(cell,tomato,infected)
  // Input cell of a matrix of n rows by m columns
  // Input tomato symbol for tomatoes
  // Input infected symbol
  //    cells are numbered 1 to nm  so the cell corners of matrix
  //    are numbered:     1, m, (n-1)m+1, nm
  //    - verify these corners for a n=4,m=3  matrix
  If (cell is within the matrix) then
    If (cell is infected or a blank) then
      // do nothing **base case
    Else if (cell has a frog) then
      // frog jumps to a new random place and acts
      newcell=random spot
      remove frog from cell
      // frog destroys whatever on newcell
      Put frog on newcell
    Else if (cell is a tomato) then
      // one step below the cell:  cell + m
      Infect(cell+m, tomato, infected)
      // one step above the cell:  cell - m
      Infect(cell-m, tomato, infected)
      // one step to the left of cell: cell - 1
      Infect(cell-1,tomato, infected)
      // one step to the right of cell: cell +1
      Infect(cell+1, tomato, infected)
    Endif
  End if
End Algorithm

best and worst case will depend a lot on the input grid, I can design situations where you end on the first iteration, I can design situations that run infinitely in the worst case