/* ***************************************************************************** * 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 how you implemented Percolation.java. How did you check * whether the 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.1 * T^1.5 * * Recall that with tilde notation, you include both the coefficient * and exponents of the leading term (but not lower-order terms). * Round each coefficient and exponent to two significant digits. **************************************************************************** */ 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 = n time (seconds) ratio log ratio -------------------------------------------------------- ... ... ... ... ... (keep n constant) n = T time (seconds) ratio log ratio -------------------------------------------------------- ... ... ... ... ... WeightedQuickUnionUF running time (in seconds) as a function of n and T: ~ _______________________________________ /* ********************************************************************* * How much memory (in bytes) does a Percolation object (which uses * WeightedQuickUnionUF.java) use to store an N-by-N grid? Use the * 64-bit memory cost model from Section 1.4 of the textbook and use * tilde notation to simplify your answer. Briefly justify your answers. * * Include the memory for all referenced objects (deep memory). **********************************************************************/ /* ***************************************************************************** * 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. **************************************************************************** */