- gustavo's personal blog

Algorithms, 4th edition

My personal notes on the book Algorithms, 4th edition, by Sedgewick & Wayne.

1. Fundamentals

1.2 Data abstraction

1.3 Bags, queues and stacks


public class Bag<Item> implements Iterable<Item> {
    void add(Item item)
    Boolean isEmpty()
    int size()

FIFO queue

public class Queue<Item> implements Iterable<Item> {
    void enqueue(Item item)
    Item dequeue()
    Boolean isEmpty()
    int size()

LIFO stack

public class Stack<Item> implements Iterable<Item> {
    void push(Item item)
    Item pop()
    Boolean isEmpty()
    int size()

Linked lists

“A linked list is a recursive data structure that’s either empty (null) or a reference to a node having a generic item and a reference to a linked list.”

Data structures

1.3 Analysis of algorithms

2. Sorting

2.1 Elementary sorts

2.2 Mergesort

2.3 Quicksort

2.4 Priority queues

2.5 Applications

3. Searching

3.1 Symbol tables

3.2 Binary search trees

3.3 Balanced search trees

3.4 Hash tables

3.5 Applications

4. Graphs

4.1 Undirected graphs

A graph is a set of vertices and a collection of edges that each connect a pair of vertices.

4.2 Directed graphs

4.3 Minimum spanning trees

4.4 Shortest paths

5. Strings

5.1 String sorts

5.2 Tries

5.4 Regular expressions

5.5 Data compression