cinera_handmade.network/cmuratori/hero/code/code231.hmml

[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]
Cinera 0.7.0 Update Add output parameter to all of hero/code, hero/intro-to-c and hero/misc, preserving the current URLs while allowing different .hmml filenames, notably for hero/misc which now gets sorted chronologically. Update the cinera__*.css files 2020-05-09 20:59:36 +00:00			`[video output=day231 member=cmuratori stream_platform=twitch stream_username=handmade_hero project=code title="Order Notation" vod_platform=youtube id=jo9rfWct1OI annotator=Miblo]`
Relocate riscy and add newly converted hero The idea here is to reduce the amount of superfluous stuff downloaded to each server running cinera 2017-12-06 22:26:13 +00:00			`[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"]`
Fix some incorrectly converted annotations Also apply some :speech categorisation 2018-03-07 21:48:09 +00:00			`[1:14:28][Q&A][:speech]`
Relocate riscy and add newly converted hero The idea here is to reduce the amount of superfluous stuff downloaded to each server running cinera 2017-12-06 22:26:13 +00:00			`[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]`
Fix some incorrectly converted annotations Also apply some :speech categorisation 2018-03-07 21:48:09 +00:00			`[1:38:09][Wrap up with a recap][:speech]`
Relocate riscy and add newly converted hero The idea here is to reduce the amount of superfluous stuff downloaded to each server running cinera 2017-12-06 22:26:13 +00:00			`[/video]`