Bede Kelly
  • home

notes

A collection of 6 posts

notes

Hashing with Chaining

Notes taken from "8. Hashing with Chaining"; MIT OpenCourseware 6.006: Introduction to Algorithms. Dictionary: Abstract Data Type Maintain a set of items, each with a key. The interface looks like

  • Bede Kelly
    Bede Kelly
6 min read
notes

Lower Bounds on Sorting

Lower Bounds can also be important within Computer Science. We can use different comparison models to show that with certain algorithms, we can get linear time sometimes with a sort. Comparison Model: All

  • Bede Kelly
    Bede Kelly
3 min read
notes

AVL Insert - Maintaining the AVL Invariant

The algorithm for the insert operation on an AVL tree: Perform a standard BST insert: a. Traverse the tree looking for where to insert an item, then insert it there. Fix the AVL

  • Bede Kelly
    Bede Kelly
1 min read
notes

The Pumping Lemma (for Regular Languages)

So apparently, this is the bit of formal logic at which all computer science undergrads quake in their boots. Guess I've got that to look forward to at uni. In the meantime, let's

  • Bede Kelly
    Bede Kelly
3 min read
notes

Reverse Polish Notation

Using brackets in computing is sometimes an unnecessary complication. Using post-fix expressions ensures that only one order of operation is needed. Postfix is another name for 'reverse Polish' notation. Infix: 38 + y Postfix:

  • Bede Kelly
    Bede Kelly
1 min read
notes

Regular and Formal Languages

Any language has an 'alphabet': the valid characters making up 'words' in this language. A notion expressing the rules governing the construction of a valid word in a language is known as a

  • Bede Kelly
    Bede Kelly
1 min read
Bede Kelly © 2023
Latest Posts Ghost