/* ***************************************************************************** * Name: * NetID: * Precept: * * Partner Name: N/A * Partner NetID: N/A * Partner Precept: N/A * * Operating system: * Compiler: * Text editor / IDE: * * Have you taken (part of) this course before: * Have you taken (part of) the Coursera course Algorithms, Part I or II: * * Hours to complete assignment (optional): * **************************************************************************** */ Programming Assignment 1: Percolation /* ***************************************************************************** * Describe the instance variables that you used to implement the * Percolation data type. **************************************************************************** */ /* ***************************************************************************** * Explain how you used the union-find data type to check efficiently * whether a system percolates. **************************************************************************** */ /* ***************************************************************************** * Perform computational experiments to estimate the running time of * PercolationStats.java for various values of n and T when implementing * Percolation.java with QuickFindUF.java (not QuickUnionUF.java). Use a * "doubling" hypothesis, where you successively increase either n or T by * a constant multiplicative factor (not necessarily 2). * * To do so, fill in the two tables below. Each table must have 5-10 * data points, ranging in time from around 0.25 seconds for the smallest * data point to around 30 seconds for the largest one. Do not include * data points that take less than 0.25 seconds. **************************************************************************** */ (keep T constant) T = 100 multiplicative factor (for n) = n time (seconds) ratio log ratio -------------------------------------------------------- ... ... ... ... ... ... (keep n constant) n = 100 multiplicative factor (for T) = T time (seconds) ratio log ratio -------------------------------------------------------- ... ... ... ... ... ... ... /* ***************************************************************************** * Using the empirical data from the above two tables, give a formula * (using tilde notation) for the running time (in seconds) of * PercolationStats.java as function of both n and T, such as * * ~ 5.3*10^-8 * n^5.0 * T^1.5 * * Briefly explain how you determined the formula for the running time. * Recall that with tilde notation, you include both the coefficient * and exponents of the leading term (but not lower-order terms). * Use two significant figures for each coefficient and exponent * (e.g., 5.3*10^-8 or 5.0). **************************************************************************** */ QuickFindUF running time (in seconds) as a function of n and T: ~ _______________________________________ /* ***************************************************************************** * Repeat the previous two questions, but using WeightedQuickUnionUF * (instead of QuickFindUF). **************************************************************************** */ (keep T constant) T = 100 n time (seconds) ratio log ratio -------------------------------------------------------- ... ... ... ... ... (keep n constant) n = 100 T time (seconds) ratio log ratio -------------------------------------------------------- ... ... ... ... ... WeightedQuickUnionUF running time (in seconds) as a function of n and T: ~ _______________________________________ /* ***************************************************************************** * Known bugs / limitations. **************************************************************************** */ /* ***************************************************************************** * Describe whatever help (if any) that you received. * Don't include readings, lectures, and precepts, but do * include any help from people (including course staff, lab TAs, * classmates, and friends) and attribute them by name. **************************************************************************** */ /* ***************************************************************************** * Describe any serious problems you encountered. **************************************************************************** */ /* ***************************************************************************** * List any other comments here. Feel free to provide any feedback * on how much you learned from doing the assignment, and whether * you enjoyed doing it. **************************************************************************** */