Episodes

  • Finite Automata - What you need to know

    Finite Automata - What you need to know
    Apr 2 2025
    Automata theory: it's a computational model study, focusing on finite automata (DFA and NFA) and push-down automata (PDA). The course explores regular languages, their properties and proofs of non-regularity using concepts like the pumping lemma and Myhill-Nerode theorem. Foundational mathematical concepts such as set theory, sequences, relations, alphabets, strings, and languages are reviewed. The equivalence between NFAs and DFAs is established through the powerset construction, demonstrating that both recognize the class of regular languages, which are shown to be closed under various operations.
    Show more Show less
    26 mins
  • Shamir's Secret: A PayPal Near-Disaster

    Shamir's Secret: A PayPal Near-Disaster
    Mar 29 2025
    This account recounts a nightmarish incident at PayPal where a flawed implementation of Shamir Secret Sharing, a cryptographic technique for distributing a secret key among multiple parties, nearly caused a catastrophic system failure. The author, a PayPal engineer, explains the process of Shamir Secret Sharing and how he implemented it to improve security by distributing the master encryption key. However, a seemingly minor incompatibility between the Linux and Solaris operating systems, involving a function that truncated long passphrases, led to the team's inability to recover the key. The crisis was ultimately resolved by discovering and correcting the incompatibility. The story concludes with a humorous postscript regarding a backup copy of the key.
    Show more Show less
    8 mins
  • SLAP and FLOP: Apple Silicon Speculative Execution Attacks

    SLAP and FLOP: Apple Silicon Speculative Execution Attacks
    Mar 18 2025
    SLAP and FLOP are two new speculative execution attacks targeting Apple's M-series chips. SLAP exploits the Load Address Predictor (LAP) to leak data by predicting incorrect memory addresses, while FLOP leverages the Load Value Predictor (LVP) to predict incorrect data values. Both attacks allow unauthorized access to sensitive information from web browsers like Safari and Chrome, compromising data ranging from email content to financial details. Researchers demonstrated proof-of-concept attacks recovering data like browsing history and even book excerpts. Mitigation requires software patches from vendors and updated operating systems.
    Show more Show less
    16 mins
  • Subaru Starlink Security Flaw

    Subaru Starlink Security Flaw
    Mar 12 2025
    Security researchers discovered and exploited a vulnerability in Subaru's Starlink connected car system. This flaw allowed unauthorized access to sensitive data, including vehicle location history, and control over features like door locks. The vulnerability stemmed from weaknesses in the Starlink admin panel, which was accessible using readily available information and easily bypassed security measures. Subaru patched the issue after being notified, but the incident highlights potential risks in connected car technology. The researchers responsibly disclosed the vulnerability before making it public.
    Show more Show less
    11 mins
  • Hash Tables: Theory, Implementation, and Universal Hashing

    Hash Tables: Theory, Implementation, and Universal Hashing
    Feb 16 2025
    In this episode, we explore hash tables, a data structure designed for efficient insertion, deletion, and searching of data using keys. The document contrasts direct addressing with hashing, highlighting the space efficiency of hash tables when dealing with large key universes. It discusses collision resolution techniques like chaining and open addressing, exploring the trade-offs between them. Different hashing methods, including division and multiplication, are analyzed for their suitability in diverse contexts. We also introduce more advanced concepts like universal and adaptive hashing to optimize performance and handle dynamic data sets.


    Show more Show less
    16 mins
  • Suffix Trees: Construction, Properties, and Applications

    Suffix Trees: Construction, Properties, and Applications
    Feb 14 2025
    Today, we are exploring suffix trees, a data structure used for solving string problems.We begin with basic definitions related to strings and alphabets, then introduces suffix trees as compressed tries containing all suffixes of a given text. Applications include substring searching, finding repeated substrings, and data compression. The discussion covers the construction of suffix trees using tries and compressed suffix trees, along with the properties that define them, modifications needed for linear time construction, and concludes with problems suffix trees help solve and an overview of Ukkonen's algorithm, which builds suffix trees in linear time by iteratively adding suffixes and leveraging various operational types and an "active position" notation. The active position notation is coupled with suffix links which help to efficiently traverse from one suffix to another, which allows Ukkonen's algorithm to work.
    Show more Show less
    10 mins
  • Disjoint Sets: Data Structures and Algorithms

    Disjoint Sets: Data Structures and Algorithms
    Feb 11 2025
    We discuss disjoint sets, also known as union-find data structures. Disjoint sets maintain collections of elements partitioned into non-overlapping sets, each with a representative element. Key operations include Make-Set (creating a new set), Find-Set (locating a set's representative), and Union (merging two sets). Different representations are explored, such as arrays, linked lists, and inverted trees, along with their associated time complexities. Heuristics like weighted union and union by rank are introduced to improve efficiency, and path compression is discussed as a way to optimize the Find-Set operation. The notes culminate in discussing the inverse Ackermann function in the context of the time complexity of the union by rank and path compression methods.
    Show more Show less
    12 mins
  • B-Tree Data Structure: Search, Insertion, and Deletion

    B-Tree Data Structure: Search, Insertion, and Deletion
    Feb 9 2025
    Jump in and discover the B-tree data structure, a fundamental tool for processing queries on one-dimensional data stored on disk. We explain how B-trees efficiently support range reporting, successor/predecessor searches, insertion, and deletion operations.
    Show more Show less
    18 mins
adbl_web_global_use_to_activate_webcro768_stickypopup