Lecture outline for Week 7 I. More dynamic programming - matrix multiplication - to multiply a pxq matrix by a qxr matrix requires pqr scalar multiplications (if we use traditional matrix multiplication) - Example: A is 10x5, B is 5x1, C is 1x6 and we want to compute A*B*C. If we multiply (A*B)*C we need 50+60 = 110 scalar multiplications, but if we calculate A*(B*C) we will use 30 + 300 = 330 scalar multiplications - so the order of multiplication matters - can you prove that a greedy method will not work? - a dynamic programming solution - Create a table T[n-1][n-1] if we have n matrices - entry T[i][j] will store the number of scalar multiplications to multiply the ith to the (j+1)th matrices together - thus, T[1][n-1] (assuming indexing from 1) will store the minimum scalar multiplication to multiply all n matrices - computing T[i][i] is easy - just the number of scalar mults. for multiplying matrix i and i+1 - for T[i][j], we need to try all combinations of parenthesizing M_i * ... * M_j -> (j+1 - i) possible ways for the outer parenthesis - and pick the minimum II. Dynamic programming vs. memoization - both use a table to reduce the amount of duplicated computations - dynamic programming is bottom up -> fill in the table from the "bottom" of the recursion - memoization is top down -> do the normal recursive algorithm, but fill in the table as you go - generally dynamic programming is better because memoization still required recusive calls and thus a lot of memory on the procedure stack - if we are not going to be filling in the entire table, memoization may be nicer since it only fills in the entries needed III. Graphs - our next data structure: graphs - a graph consists of: nodes (or vertices) and edges (or arcs) - many problems naturally translate to graphs - examples: distances between cities - each city is a vertex - each highway segment between 2 cities is an edge - find shortest highway route from city A to B? - mapping microchips - each vertex is a gate - each edge is a wire between gates - can we rearrange gates so that no wires cross? - power transmission - edges are powerlines - vertices are cities, buildings or plants - how much electricity can we ship to CA on the electric grid? - edges may have a direction (directed graphs) - ex. one-way streets - directed graphs indicate a flow in only one direction - non-directed edges allows flows in both directions - generally, we consider a graph to be undirected unless indicated - any binary relation can be represented by a graph - given a domain for the relation, each element in the domain is represented by a vertex. - if (xRy) is true for some relation R and elements x and y, then we add a directed edge from x to y. - if (yRx) also holds we may either add a directed edge from y to x or use a nondirected edge between x and y - if R is symmetric, we will use an undirected graph - formally, we define a graph by the pair (V, E) - V is a set of elements called vertices - E is a set of (possibly ordered) pairs of elements of V - ex: (x, y) for x,y, in V - also may be denoted as xy - notation: we usually denote a graph by G - V(G) indicates the vertices of G - E(G) indicates the edges of G - Definitions - two vertices are adjacent if there is an edge between them - the neighbors of a vertex are all its adjacent vertices - a path is a sequence of vertices such that there is an edge (possibly directed) between adjacent vertices on the path - in other words, a path starts at some vertex and visits other vertices of the graph by following the edges - a cycle is a path in which the first and last vertices are the same and no edge is repeated on the path. - for a simple cycle, the first and last vertices are the same and no other vertex is repeated on the path - in other words, a cycle starts at one vertex, follows the edges of the graph and returns to that vertex, visiting no vertex more than once. - for a directed graph, we must follow the direction of the edges (for both paths and cycles) - a graph is connected if there is a path from every node to every other node - for directed graphs (digraphs) we distinguish between "strongly connected" and "weakly connected" - strongly is same as above - weakly means there is a path if we ignore the direction of the edges - the components of a graph are its connected pieces - How to represent graphs - adjaceny matrix - A[i][j] = 1 if (i, j) /in E, 0 else - adjaceny list - have an array of linked lists. - the ith linked list contains the neighbors of i - storage size: n^2 vs n+m where n = |V| and m = |E| - so an adjacency list is more efficient until the number of edges is around n^2 - dense vs. sparse graphs - a graph is dense if there are around n^2 edges