CSC263H1 Study Guide - Final Guide: Priority Queue, Topological Sorting, Quadratic Probing
12 Jan 2016
School
Department
Course
Professor
Document Summary
V = set of vertices {a, b, c} E = set of edges {(a, b), (c, a): types. Dense (connected to every other vertex) / sparse. Length of path = number of edges: operations on graph. Undirected graph takes v + 2e space. Check whether edge (vi, vj) is in e. Go through list a[i] see if j is there. Depth first search: compute an expectation (10 points, quick sort (6 points) Algorithm: pick a pivot (last integer, swap elements so that left is smaller than pivot, right larger than pivot. Worst input for quick sort is an already sorted array. Compare with last element (which is largest) most once: average-case analysis of quick sort. X_ij = 1 if values i and j are compared, 0 otherwise n n. Monte carlo algorithm: worst case o(nlogn, gain time efficiency by sacrificing correctness, compare x = y (x mod p) == y(mod p, amortized analysis (10 points)
