Math 405 Spring 2017 Test 3 Topics 4.1 Dijkstra’s Algorithm finding the shortest distance in a network from a specified vertex. Find a shortest – path by backtracking. You need to label all vertices that are a fixed distance from the initial vertex, not just those that you believe are on a shortest path. Each vertex has a unique ordered pair as a label where the first coordinate is the predecessor on a shortest path and the second coordinate is the shortest distance to the initial vertex. 4.2 we used Prim’s and Kruskal’s algorithms. You need to be able to list the edges in Minimal Spanning Trees – the order that they are added according to the respective algorithm. The weight of all minimal spanning trees is the same, but the trees may be different. 5.1 Addition and Multiplication Principles add, multiply; how does repetition being allowed or – “or” “and” not allowed affect problems 5.2 Simple Arrangements and Selections permutations (order matters), combinations (order does not – matter, selections), how do repeated entries affect the counting 5.3 Arrangements and Selections with Repetition Arrangements with repetition of n objects, ri of type i. Selections with repetition r items from n types – Represent each item with a * Use (n-1) slashes to designate the n types C(r+(n-1), r) = C(r+(n-1), n-1) 5.4 Distributions also non-negative integer solutions to – See charts p. 218 & 220 6.1 Generating function g(x) – g(x) is a function where ar ,the coefficient of xr, gives the number of ways to select r items in r items in a certain procedure Since the coefficient of xr is the sum of the exponent chosen in each of the factors, this problem is the same as the number of integer solutions of a linear equation with restrictions. 6.2 Calculating coefficients of generating functions we used the formulas in the chart below – Not on Tuesday’s test 7.1 Recurrence relation the relationship is expressed in terms of previous terms; approaches include finding – the first few terms and considering the last step. Math 405 Polynomial Expansions (Sec 6.2) (1)
Math 405 Spring 2017 Test 3 Topics 4.1 Dijkstra’s Algorithm – finding the shortest distance in a network from a specified vertex. Find a shortest path by backtracking. You need to label all vertices that are a fixed distance from the initial vertex, not just those that you believe are on a shortest path. Each vertex has a unique ordered pair as a label where the first coordinate is the predecessor on a shortest path and the second coordinate is the shortest distance to the initial vertex. 4.2 Minimal Spanning Trees – we used Prim’s and Kruskal’s algorithms. You need to be able to list the edges in the order that they are added according to the respective algorithm. The weight of all minimal spanning trees is the same, but the trees may be different. 5.1 Addition and Multiplication Principles – “or” add, “and” multiply; how does repetition being allowed or not allowed affect problems 5.2 Simple Arrangements and Selections – permutations (order matters), combinations (order does not matter, selections), how do repeated entries affect the counting 5.3 Arrangements and Selections with Repetition Arrangements with repetition of n objects, ri of type i. Selections with repetition – r items from n types Represent each item with a * Use (n-1) slashes to designate the n types C(r+(n-1), r) = C(r+(n-1), n-1) 5.4 Distributions – also non-negative integer solutions to See charts p. 218 & 220 6.1 Generating function – g(x) g(x) is a function where ar ,the coefficient of xr, gives the number of ways to select r items in r items in a certain procedure Since the coefficient of xr is the sum of the exponent chosen in each of the factors, this problem is the same as the number of integer solutions of a linear equation with restrictions. 6.2 Calculating coefficients of generating functions – we used the formulas in the chart below Not on Tuesday’s test 7.1 Recurrence relation – the relationship is expressed in terms of previous terms; approaches include finding the first few terms and considering the last step. Math 405 Polynomial Expansions (Sec 6.2) (1)
Test%203%20Topics.docx