This week’s powerpoint can be found here.

This week, we took a look at a few of the different algorithms and data structures built for handling strings. Strings are a powerful component of computer science, but dealing with very large strings poses a huge challenge to programmers. Luckily, lots of brilliant minds in CS have put time into devising some clever ways to solve string problems.

Manacher’s Algorithm

This algorithm is built specifically for one purpose: finding the longest palindromic substring of a string. This may seem like a trivial task on the surface, but it is usually used as part of larger programs which just so happen to need the longest palindromic substring to be quickly retrieved. And quick, it is! This algorithm can provide a solution in O(n), while the brute force approach to this problem can only do it in O(n^3).

- Visualizing the algorithm
- Hacker Earth explanation and tuturial
- Leetcode article about the algorithm

Trie vs Tree

A *PATRICIA tree* is a type of *radix tree* is a type of compresed *trie* is a type of *tree*. Phew!

Radix Trees

The radix tree is a data structure that can help us store and work with strings in a pretty clever way. One example of its use in the real world is with predictive text.

- Article that explains the compression of a trie (aka, how radix trees are formed). Also goes into how the PATRICIA trees work.
- Gayle Laakmann McDowel (author Cracking the Coding Interview) talking about Tries
- Stack Overflow Radix Tree vs PATRICIA tree

Knuth-Morris-Pratt (KMP) Algorithm

The KMP algorithm was created to find a substring in a given string. Using some clever observations about string searching and mismatches, it is able to do this in O(n)! The video below does a pretty great job of explaining the mechanics behind this algorithm.

- Fantastic video from SpookyAlgorithms, this is where the bulk of the KMP information and all the examples came from. Hands down the most concise and well formed explanation I could find. It’s not perfect, but the idea is well conveyed.

SIG business:

- SIG Algorithm Challenge – finalized plan for this semester
- Points system where points are awarded for doing challenges and attending meetings:
- Working solution to weekly challenge problem = 200 points
- Working solution that somehow goes above and beyond (used a new or difficult language, implemented a difficult algorithm, GUI, etc.) = 500 points
- Attend a weekly SIG Alg meeting = 100 points

- Two award levels:
- Top two members with highest points at the end of the semester will get prizes (i.e. Raspberry Pi, Steam gift card, etc.)
- All other members will be able to trade in some amount of their points (TBD) for snacks from the ACM office.

- Points system where points are awarded for doing challenges and attending meetings:
- Discussed applying for the bi-weekly SIG fund from ACM.
- This round, we will be applying for a raspberry pi
- Matt mentioned that if we win we could use it to do an algorithm project with visual results, such as a Towers of Hanoi demonstration

Next week:

History of search engines, and all about the Google algorithms that helped them dominate the market