Algorithms and Data Structures

Summary Notes by Carlos Melegrito

In this repo is everything I've learned while studying the FIT2004 unit at Monash University. It's a collection of summary notes, algorithms and their explanations useful in many areas of computer science. To use these notes, follow along the links in the contents below like a guidebook.

Contents

Formalities

• Abstract Data Types
• The List ADT
• The Tree ADT
• Correctness
• Complexity

Sorting Algorithms

• Selection Sort
• Insertion Sort
• Heap Sort
• Merge Sort
• Quick Sort

Dynamic Programming (Examples)

• Fibonacci Sequence
• Coins Change
• Subset Sum
• Edit Distance
• Hirschberg's Algorithm

Efficient Lookup and Retrieval

• Hash Tables
• Binary Search Trees
• AVL Trees
• B-Trees
• Retrieval Trees
• Suffix Trees

Compression

• Burrows-Wheeler Transform

Graph Algorithms

• Graphs
• Breadth-First Search
• Dijkstra's Algorithm
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm

Tree Algorithms

• Minimum Spanning Trees
• Prim's Algorithm
• Kruskal's Algorithm

Directed Acyclic Graphs

• Topological Sort
• Kahn's Algorithm
• Depth-first Search

Numerical Algorithms

• Interval Bisection
• Newton's Method
• Calculating Integrals

P vs NP

• The P vs NP Problem

Primes

• Primality
• Fermat's Little Theorem

Algorithmic Design Principles

• Strategies and Writing Algorithms