48 lines
3.8 KiB
Plaintext
48 lines
3.8 KiB
Plaintext
[video output=day231 member=cmuratori stream_platform=twitch stream_username=handmade_hero project=code title="Order Notation" vod_platform=youtube id=jo9rfWct1OI annotator=Miblo]
|
|
[1:03][Set the stage for the day]
|
|
[2:57][Blackboard: Order Notation]
|
|
[4:13][Blackboard: "unit"]
|
|
[5:50][Blackboard: Linear "scale", e.g. stamping envelopes]
|
|
[8:39][Blackboard: Nonlinear "scale", e.g. checking if any envelopes are addressed to the same person]
|
|
[14:02][Blackboard: Why we care about linearity]
|
|
[15:57][Blackboard: How this determines scalability]
|
|
[18:00][Blackboard: Why we don't care about the constant when considering an algorithm's scalability]
|
|
[21:22][Blackboard: How this translates into code]
|
|
[23:37][Blackboard: Big O notation indicates "worst-case running time"]
|
|
[26:49][Blackboard: "randomized algorithms"]
|
|
[28:34][Blackboard: P (polynomial) vs NP (nondeterministic polynomial)]
|
|
[35:50][Blackboard: On classifying problems as P or NP, e.g. "Boolean satisfiability problem"]
|
|
[40:45][Blackboard: "NP-completeness"][quote 345]
|
|
[45:12][Blackboard: *Gotcha! e.g. "Travelling Salesman Problem"]
|
|
[52:14][Blackboard: Sorting]
|
|
[53:39][handmade_render_group.cpp: Note that the current SortEntries function is O(n^2)]
|
|
[54:02][Blackboard: Why SortEntries is O(n^2)]
|
|
[55:17][Blackboard: On how to make sorting not be O(n^2)]
|
|
[56:35][Blackboard: Walk through our current (Bubble sort) algorithm]
|
|
[58:13][Blackboard: Walk through a "divide and conquer" (Merge sort) algorithm]
|
|
[1:04:30][Blackboard: Compare these two algorithms]
|
|
[1:07:08][Blackboard: Divide and conquer algorithms are O(n log n)]
|
|
[1:08:35][Blackboard: Solidify the concept of the merge sort algorithm and "dynamic programming"]
|
|
[1:14:28][Q&A][:speech]
|
|
[1:14:56][@quartertron][NP stands for Nondeterministic Polynomial. Plus some other minor problems. Otherwise, well done]
|
|
[1:16:39][@cubercaleb][For the record the remark I made earlier about Rust was not serious. Also, isn't mergesort n*log(n)?]
|
|
[1:17:08][@Longboolean][So unit testing a function that computes a path for the traveling salesman problem would require writing the algorithm twice, the second one testing the first?]
|
|
[1:18:04][@fiveshot97][Do you think a computer science major is a good path to go? I'm in it now]
|
|
[1:19:05][@insofaras][You say "exponential"]
|
|
[1:19:08][@Busy_Beaver][To say that a problem is not solvable in polynomial time, you just say "The problem is not in P"]
|
|
[1:21:12][@cmuratori][Has anyone definitively proven that Travelling Salesman could not be in P, or is that still potentially NP-hard?]
|
|
[1:22:44][@Busy_Beaver][TSP is NP-complete, so it is also in NP, so it DOES have a polynomial verifier]
|
|
[1:23:12][@cmuratori][Have they proven that it doesn't have a P verifier?]
|
|
[1:25:33][@Busy_Beaver][Well it depends which TSP problem we are actually talking about]
|
|
[1:26:44][@quiensab3][Wouldn't saying that something is "NINPY" imply that P != NP? (Did we win a $1M prize?)]
|
|
[1:27:05][Blackboard: "in P" / "not in P" vs "NP-complete"]
|
|
[1:30:42][@Longboolean][Idea: The game should include a traveling salesman, who ponders these things...]
|
|
[1:30:54][@cubercaleb][Will we go into more complex sort algorithms like radix sort? Also, is the space requirement of mergesort something that needs to be take into consideration for Handmade Hero?]
|
|
[1:31:45][@quartertron][Since you didn't go to college, when did you first get interested in or at least start learning all about big O?]
|
|
[1:33:25][@insofaras][I'm not sure we can prove something is not in P unless it is undecidable or we can prove P != NP]
|
|
[1:33:54][@Connor_Rentz][By the way, 8^2 doesn't equal 16]
|
|
[1:37:31][@quartertron][I shall dig through my copy of Computers and Intractability by Gary and Johnson tonight]
|
|
[1:37:41][@quartertron][Hmm, first sentence contains the word whimsical so it's looking good so far]
|
|
[1:38:09][Wrap up with a recap][:speech]
|
|
[/video]
|