Zoom Logo

CMSC420-0201: Lecture - Shared screen with speaker view
Bailey Fokin
08:38
when it comes to programming assignments, will we be getting a code skeleton or will we be starting from scratch everytime. If we will be getting skeletons, will we be using a repo that we can lin
Bailey Fokin
08:47
link to eclipse*
William Cao
08:58
What time are those usually uploaded?
Joshua McKelvey
12:20
Panopto seems to work better on my phone
Jane Li
13:03
panapto allows you to watch at different speeds whereas the class web pg videos don't have that speed feature
John Heide
15:58
Panopto also has titles for lectures like "Lecture 1 Basics", so we don't have to look at the date to figure out the video contents
Chandan Murthy
17:47
yea we see it too
Alvaro Szigethi Marcos
17:49
Yes but it doesn’t bother
Kevin Boby
20:51
Yes
Hongyu Tu
21:10
Will this note be posted after the lecture?
Luke Amato
21:41
He has the pdfs and videos with the same information already posted
Hyen Jeong
22:58
what's the difference btw "set" and "insert"?
James Brunner
23:11
Set changes a value
Eric Li
23:15
insert will increase the list length
Sonya Radichkova
23:27
Does set replace any existing value that may already exist in the index i?
Sonya Radichkova
23:38
I’m assuming that’s part of the difference?
James Brunner
23:42
yes
Kevin Boby
26:17
Did he say a list was a type of abstract data type?
Eric Li
26:22
yes
Kevin Boby
26:26
Alright ty
James Brunner
31:29
Do u have an example of when a duque would be useful?
Hongyu Tu
32:15
If you are using GoodNotes, you can simply wipe to right to create a new page
Kristen Twigg
34:27
You could use OneNote on your iPad too
Alvaro Szigethi Marcos
35:05
Is this what Python lists use?
Chandan Murthy
35:56
do we have to deallocate or just "free" it and let it be overwritten
Eric Li
38:41
what if n > 2m?
Kamtochukwu Okafor
38:52
Does the second question have something to do with amortized time?
James Brunner
44:27
Wouldnt it be better to start from like 10 rather than empty?
zhenghang
50:51
why realloc cost is 2m instead of m?
William Cao
51:15
Upper bound
Alvaro Szigethi Marcos
51:17
You copy m elements, and add another m
Kevin Boby
51:49
Where did that 5 come from, or is that a random value
Chandan Murthy
52:07
cant you also argue 3m, 2m for init and m for copy?
William Cao
52:29
no?
William Cao
52:34
because you don't init 2m
William Cao
52:41
you copy the first m?
William Cao
52:47
so you wouldn't have to init beforehand?
Coby Winfield
52:52
why is the cost model =< 5?
Chandan Murthy
52:55
oh ok
William Cao
53:51
cost model 5 is maybe taking into account that for low m that's an upper bound?
Hyen Jeong
57:22
+1 is when you push a new element right?
William Cao
57:35
Did you skip 3?
Alvaro Szigethi Marcos
57:51
If the original size of our data structure is n. Do we double its size when we enter the nth element, or when we try to insert the n+1th element and we are unable to do so?
Sonya Radichkova
57:52
It’s when u copy all the elements over to the new array
Bert Love
58:22
+1 is insertion
Bert Love
58:32
because we’re doubling list is never size 3
Alvaro Szigethi Marcos
58:33
+1 is inserting a new element
William Cao
59:08
ok
Sonya Radichkova
59:18
Alvaro I think it’s when you insert n+1th element and there’s no space so u have to realloc
Alvaro Szigethi Marcos
59:39
Sounds goodie, thanks
Sonya Radichkova
59:41
See how after 2 and he inserts the third but can’t so he doubles
Sonya Radichkova
59:50
np
Maya Fuchs
01:00:32
Why is it 17 + [evens]? shouldn't we be adding the totals, so 3 + 5 + 9 + 17 + 32?
James Brunner
01:01:13
Resizes + each push
Samantha Tang
01:01:56
The 3,5,9 etc at the bottom of the lines count the push. The 17 he uses is the pushes alone
Chandan Murthy
01:01:57
shouldn't the last term be 33
Maya Fuchs
01:02:10
So the nth push + the reallocs, I think I understand, thanks!
James Brunner
01:02:14
No, bc that push is included in the 17
Maya Fuchs
01:02:16
up to the nth
Maya Fuchs
01:02:27
?
Maya Fuchs
01:02:48
i think i get it lol
James Brunner
01:03:16
But wouldn’t you deallocate after a ton of pops?
Bailey Fokin
01:05:55
work tokens, ptsd flash backs to release tokens
Eric Li
01:05:56
in amortized analysis, we consider worst case, which is all pushes
Alvaro Szigethi Marcos
01:06:15
Wouldn’t it be easier to keep track of how many times each element is reallocated
Alvaro Szigethi Marcos
01:06:50
Since we reallocate to twice the size, we will have lgn reallocations
Karen Herrera Matus
01:07:08
So the 5 will only work for this specific example?
Alvaro Szigethi Marcos
01:07:13
The first element reallocates lgn times, 2nd and 3rd lgn-1 times and so on
William Cao
01:07:31
I think it works in general?
zhenghang
01:09:22
Isn't it 2n-1 more pushes?
Savyasachi Konkalmatt
01:09:23
wouldn't there be m more pushes?
Niall Williams
01:10:22
@Karen, the 5 comes from the fact that we double the size when the stack is full. if we did a different resize (such as 3x, or +1000 empty spaces in new stack), the 5 will be a different number
Karen Herrera Matus
01:11:28
@Niall oh gotcha thanks!
Savyasachi Konkalmatt
01:11:35
yup
Niall Williams
01:11:37
basically, the rule you choose for how much empty space to add to the stack when you resize determines the exact amortized cost
Michael Stephanus
01:12:29
so the stack with 4n size, there will be 2n -1 more pushes?
Luke Amato
01:13:39
Ya
Michael Stephanus
01:13:48
thanks!
Michael Stephanus
01:14:12
will there be a case where we need to reallocate the array, but there are enough tokens in the bank to pay for it?
Michael Stephanus
01:14:25
not enough*
Michael Stephanus
01:14:29
sorry
William Cao
01:14:33
Induction?
Luke Amato
01:14:52
Technically 2n because that last push we can still use the excess 4 'tokens' toward the reallocation operation
Hongyu Tu
01:15:38
Can you explain again where exactly does the 4n come from?
Hongyu Tu
01:16:05
And why we are adding 1 to 4n to get 5?
Anjola Olarinde
01:16:19
we add n+4n=5n, then divide that by n ops
Hongyu Tu
01:17:53
sounds good, thanks
William Cao
01:19:20
For big N that's the same as +1
William Cao
01:19:25
which is O(n^2)
Sahil Dev
01:21:31
thanks!
Samantha Tang
01:21:33
Have a good weekend!
Ishan Sen
01:21:33
Thank you!