Here we introduce the idea of "smart recursion", which is better known as "dynamic programming". We illustrate this with the calculation of the Fibonacci numbers, which give a horrendously slow algorithm if we don't keep previous calculations stored (i.e., we will repeat them). So we use "smart" recursion by saving calculations in a table, leading to a much faster algorithm. Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Youtube Live Streaming (Sundays) - subscribe for when these occur. Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=OF_cTYUIHN0

Here we show that decidable languages are closed under the five "main" operators: union, intersection, complement, concatenation, and star. The key is to assume deciders exist for the original language(s), and then to construct a decider for the desired language based off of the originals. Most of them are simple, but some require to examine all possible cases of the input being "split" into multiple pieces. Patreon: https://www.patreon.com/easytheory Twitch: https://www.twitch.tv/easytheory Discord: https://discord.gg/SD4U3hs Facebook: https://www.facebook.com/easytheory/ Twitter: https://twitter.com/EasyTheory Teespring: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ADDITIONAL QUESTIONS◀ 1. Are decidable languages closed under homomorphism? 2. [Hard] Find an operation that decidable languages are NOT closed under. Bonus points if you can find one such that regular languages ARE closed under it (or to show one doesn't exist)! ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory. ▶ABOUT THIS CHANNEL◀ The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions. This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define. However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-free grammars and pushdown automata. For example, we can model a piece of hardware (a circuit) as a finite-state system and solve whether the circuit satisfies a property (like whether it performs addition of 16-bi ... https://www.youtube.com/watch?v=nZhAWPPDrF8

Yeah, so that happened. *sigh* Easy Theory Website: https://www.easytheory.org Discord: https://discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. The views expressed in this video are not reflective of any of my current or former employers. ... https://www.youtube.com/watch?v=PZeS180_RPw

Here we show why binary search is often taught with a subtle bug that would be really hard to detect without really thinking about how binary search actually works. We show a pseudocode implementation and go over why some languages would cause such a bug to occur, and a possible fix. Specifically, the bug is an overflow when computing the midpoint. This algorithm is taken from leetcode.com, which shows that you shouldn't just blindly implement an algorithm taken from something you read online. Easy Theory Website: https://www.easytheory.org Discord: https://discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. The views expressed in this video are not reflective of any of my current or former employers. ... https://www.youtube.com/watch?v=MhEQdHLyrcg