📖

Data Structures & Algorithms

The word algorithm itself is derived from the name of the 9th-century mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose nisba (identifying him as from Khwarazm) was Latinized as Algoritmi.
How do you find the shortest path in an undirected graph?

Using Breadth First Search

How would you find the shortest path in a weighted directed graph (with non-negative weights)?

Dijkstra's algorithm

How would you find the shortest paths to all vertices weighted directed graph with positive and negative from a single source?

Bellman-Ford

How would you find the shortest paths between all pairs of vertices in a weighted directed graph?

Floyd-Warshall Algorithm

How do you find a negative cycle in a weighted directed graph?

Floyd-Warshall Algorithm

What is the decision tree model?

The decision-tree model A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm on an input of particular size. The length of the longest simple path from the root of a decision tree to any of it's reachable leaves represents the worst-case number of comparisons that the corresponding sorting algorithm performs.

What is the binary search tree property?

The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property:

Let x be a node in a binary search tree.

If y is a node in the left subtree of x, then y.key <= x.key.

If y is a node in the right subtree of x, then y.key >= x.key

What is a tree? What are the properties of a tree?

A tree is an undirected connected acyclic graph

Properties:

  • A tree is acyclic
  • A tree is connected
  • A tree has exactly one path between any pair of vertices
  • All trees on n>1 vertices have exactly n−1 edges
What is unpacking in python?
def fun(a, b, c, d):
    print(a, b, c, d)

my_list = [1, 2, 3, 4]

# Unpacking list into four arguments
fun(*my_list)

An undirected acyclic connected graph is a ____. If the number of vertices n > 1, how many edges should this ____ have?

Tree

|E| === n - 1

What is a loop invariant
Why would you use an Adjacency list over a matrix to represent a graph?

One useful property is the sparsity of the graph’s edges.

  • If the graph is sparse, and the number of edges is considerably less than the max (e.g. m << n^2 *m<< n^2), then the adjacency list is a good idea.
  • If the graph is dense and the number of edges is nearly n^2, then the matrix representation makes sense because it speeds up lookups without too much space overhead.
How do you transpose a matrix in python?
t_matrix = zip(*matrix)
What are the different ways graphs can be represented?
  • An adjacency matrix uses an arbitrary ordering of the vertices from 1 to | V |.
    • The matrix consists of an n × n binary matrix such that the (i, j)-th element is 1 if (i, j) is an edge in the graph, 0 otherwise.
  • An adjacency list consists of an array A of | V | lists
    • Each list A[u] contains the edges (u,v) ∈ E (the neighbors of u).
  • As a collection of nodes and its neighbors
Anki todos
Complexity
Dynamic Programming
Encoding
General
Graph
Greedy
Hash Table
Heap
LinkedList
Counting / Math
Recursion
Sorting
Stacks
String
Techniques
Tree

Algorithm

NameTagsFiles
AlgorithmGraphSearch
Data StructureBST
AlgorithmSorting
AlgorithmGraph
AlgorithmSorting
AlgorithmGraphSearch
Data Structure
Data StructureLinkedList
AlgorithmSorting
AlgorithmTree TraversalTree
AlgorithmSorting
AlgorithmTree TraversalTree
Data StructureLinkedList
AlgorithmSorting
Data StructureHeap
AlgorithmTree TraversalTree
AlgorithmTree TraversalTree
Data Structure
AlgorithmSorting
AlgorithmSorting
AlgorithmGraph
AlgorithmGraph
Dynamic Programming
Search