Spring 2001 CS100M Project P5: 2D Array Mish-Mash 3 due dates (see below) =============================================================================== Submission -- all parts are to be submitted online =============================================================================== + P5.1 (P4.2 rewrite) deadline: 8am, Thursday morning, March 29. + P5.3 (polygon) deadline: 6pm, Friday afternoon, March 30. + P5.2 (Condorcet) deadline: 2am, Tuesday night, April 3 (Wednesday morning, April 4) =============================================================================== 5.1 Rewrite P4.2 write-up =============================================================================== Topics: Terminology, notation, style/formatting, program specification Task: (a) rewrite the entire posted p4.2 write-up to meet the goals listed below. if some parts of our write-up are good as-is, then you may leave them unchanged, but remember to explain why in part (b). goals: without giving away too much of the solution -- + use the same terminology, but explain it more clearly + specify the same set of functions/scripts, but explain things more clearly + improve the examples: + add to, modify, and delete provided examples + add more explanations if necessary + add helpful hints of things to do or try or think about + include helpful warnings of mistakes to avoid (b) briefly but clearly explain how/why your changes improve things or why the original is good and clear as-is. (c) briefly explain why E5.1 and E8.1 and their posted solutions did or did not help you with P4.2. Submission: + submit (a), (b), (c) together as one file. + submit P5.1 online by 8am, Thursday morning, March 29. Formatting requirements: + text only! no microsoft word .doc files, no html. + no tabs! + use and assume a fixed-width font, e.g. courier. + at most 80 characters per line. + under 330 lines (about 5 pages). + use $-notation for all program elements and math. + use *-notation for emphasis, e.g. like *this*. =============================================================================== 5.2 Condorcet voting =============================================================================== Topics: Plain and SSD Condorcet voting, sets and set operations, 2-D arrays, functions, sub-functions. Optional background: prominent links at http://electionmethods.org/ Condorcet: A Better Election Method Is Condorcet Voting Too Complicated? Why Approval Voting Should be Approved Now The Problem with Instant Runoff Voting Technical Evaluation of Election Methods Required background: http://electionmethods.org/ --> Tutorial --> Condorcet Voting Explained Pairwise Matrix Construction Cyclic Ambiguity Resolution + Plain Condorcet + Schwartz Sequential Dropping + new topic: 2-dimensional arrays _______________________________________________________________________________ Task Overview: Write function $condorcet$ and the other sub-functions below [plain,ssd] = condorcet(election): Plain and SSD Condorcet winners ($ssd$ is bonus) [i,j,v] = alldefeats(pwm): defeats in ascending order t = issubset(a,b): "$a$ is a subset of $b$?" pwm = tallies(election): pairwise matrix "in" an election pwm = tally(ballot): pairwise matrix for a single ballot top = topmost(pwm): innermost unbeaten sets (bonus) list = unbeaten(pwm,list): smallest unbeaten set containing $list$ (bonus) Bonus: implement sub-functions $topmost$ and $unbeaten$ and use them to compute the SSD winners The full specifications are given in the provided skeleton code. _______________________________________________________________________________ Submission: + write all the code in one file $condorcet.m$. + submit P5.2 online by 2am, Tuesday night, April 3 (Wednesday morning, April 4). _______________________________________________________________________________ Examples: forthcoming... (also in lecture) note: http://electionmethods.org/ has some test data Further Explanation: forthcoming... (also in lecture) _______________________________________________________________________________ P5.2 Hints (some might not make sense until after Thursday's lecture) suggested algorithm for $tally$: ballot --> pwm 0. if $x = 'E>D=B>A=C'$, then $x(1:2:end) = 'EDBAC'$ \ think of this as: E D B A C $x(2:2:end) = '>=>='$ / > = > = 1. we can assign ranks to each candidate: 1 2 2 3 3 note: the order of the ranks is the same as the order of the candidates: E=1 > D=B=2 > A=C=3 + assign rank 1 to first candidate, E + rank of next candidate is indicated by the comparisons: either the previous rank ($=$) or one higher ($>$) 2. reorganize parallel lists so that candidates are in alphabetical order candidates E D B A C ---> A B C D E <- can omit ranks 1 2 2 3 3 3 2 3 2 1 <- new $ranks$ vector 3. compute pairwise matrix using ranks (exactly the same results as in the 3/27 lecture sketch): 3 < [3 2 3 2 1] = [0 0 0 0 0] 2 < [3 2 3 2 1] = [1 0 1 0 0] 3 < [3 2 3 2 1] = [0 0 0 0 0] 2 < [3 2 3 2 1] = [1 0 1 0 0] 1 < [3 2 3 2 1] = [1 1 1 1 0] (advanced technique for $alldefeats$: pwm --> sorted list of defeats + the sorted list of defeats can be computed using logical arrays, $find$, and $sort$ ) simple but efficient algorithm for plain condorcet, given pairwise matrix: compute all defeats in sorted order count #defeats for each candidate while smallest #defeats > 0 drop lowest defeat(s) and decrement corresponding #defeats by 1 return all candidates with 0 defeats general programming + to develop sub-functions, either + initially write as separate functions (in separate files) + or use $keyboard$ inside main function to get access to sub-functions + you might want to include some diagnostic code to help you debug + use $if 0 ... end$ to effectively "comment out" portions of code + use $debug=0$ or $debug=1$ with $if debug end$ to turn $$ off or on + test each function as you go: don't wait until the end to debug =============================================================================== 5.3 Extension of E11 Plotting =============================================================================== Topics: line equation, distance to a line, half-plane equation, functions, 2-D arrays, strings, logical arrays, vectorization [3/27] careful: positions below are written as $(x,y)=(column,row)$, not as $(row,column)$. Task: Write a function $polygon(pic,px,py,boundary,interior)$ to return a char matrix that has a polygon plotted: + $pic$ is a char matrix holding the background, with coordinates $x = 1:size(pic,2)$, $y = 1:size(pic,1)$ + $px$, $py$ are row vectors of the same length $n$ + $px$, $py$ hold the $n$ vertices $(px(i),py(i))$ of a non-degenerate, convex $n$-gon; coordinates are not necessarily integers + [3/27] vertex $(px(i),py(i))$ is connected to $(px(i+1),py(i+1))$ for $i=1:n-1$, and vertex $(px(n),py(n))$ is connected to $(px(1),py(1))$ + $boundary$, $interior$ are strings that specify how to draw the polygon: + a single character is what to draw at each relevant position + an empty string means the characters at the relevant positions are left unchanged + a position is on the *boundary* if it has distance < .5 from any edge of the polygon + a position is in the *interior* if it is inside the polygon and is not on the boundary + clipping is performed: no drawing is done outside of $pic$ + except for clipping, error-checking is not necessarily performed Be sure to carefully test your function! Hints: + ideas from E11 can be helpful + work on the interior first: it is probably easier to do than the boundary + a pair of distinct points $(x1,y1)$, $(x2,y2)$ defines a unique line + if $A$ or $B$ is non-zero, then + $Ax + By + C = 0$ defines a unique line + $Ax + By + C < 0$ defines a unique half-plane + can multiply equation $Ax + By + C = 0$ by a non-zero constant + can set $A = dy$, $B = -dx$, where $dy = y2-y1$, $dx = x2-x1$, and plug in any point on the line to get $C$, e.g. plug in $(x1,y1)$ or $(x2,y2)$. + if $sqrt(A^2 + B^2) = 1$, then $abs(Ax + By + C)$ is the distance from point $(x,y)$ to the line defined by $Ax + By + C = 0$ + polygon interior = intersection of half-planes + Q: which half-plane, i.e. which side of a line? + A: same side as other vertices of the polygon, i.e. when plug a point into $Ax + By + C$, want the same sign as when plug in a vertex + matlab has a $sign$ function + polygon edge = intersection of a line with half-planes + to draw a line, we need it to have thickness + this is why we ask for distance $abs(Ax + By + C)$ less than $.5$ Submission: + submit P5.3 online by 6pm, Friday afternoon, March 30. Example: clear pic; pic(20,50) = '.'; pic(:,:) = '.' pic = polygon(pic, [2 60 40 10], [5 5 20 15], '+', 'o') pic = polygon(pic, [13 13 47 47], [8 12 12 8], '#', '*') pic = polygon(pic, [13 13 47 47], [8 12 12 8], '', '-') pic = polygon(pic, [1 30 1], [1 20 20], '\', '') Contents of $pic$ after executing each line of code in the example: pic; pic(20,50) = '.'; pic(:,:) = '.' .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. pic = polygon(pic, [2 60 40 10], [5 5 20 15], '+', 'o') .................................................. .................................................. .................................................. .................................................. .+++++++++++++++++++++++++++++++++++++++++++++++++ ..+ooooooooooooooooooooooooooooooooooooooooooooooo ..++oooooooooooooooooooooooooooooooooooooooooooooo ...++ooooooooooooooooooooooooooooooooooooooooooooo ....+ooooooooooooooooooooooooooooooooooooooooooooo .....+oooooooooooooooooooooooooooooooooooooooooooo ......+ooooooooooooooooooooooooooooooooooooooooooo ......++ooooooooooooooooooooooooooooooooooooooooo+ .......++ooooooooooooooooooooooooooooooooooooooo++ ........+oooooooooooooooooooooooooooooooooooooo+.. .........++++oooooooooooooooooooooooooooooooo++... ............+++++++ooooooooooooooooooooooooo++.... ..................+++++++oooooooooooooooooo+...... ........................+++++++oooooooooo++....... ..............................+++++++ooo++........ ....................................++++.......... pic = polygon(pic, [13 13 47 47], [8 12 12 8], '#', '*') .................................................. .................................................. .................................................. .................................................. .+++++++++++++++++++++++++++++++++++++++++++++++++ ..+ooooooooooooooooooooooooooooooooooooooooooooooo ..++oooooooooooooooooooooooooooooooooooooooooooooo ...++ooooooo###################################ooo ....+ooooooo#*********************************#ooo .....+oooooo#*********************************#ooo ......+ooooo#*********************************#ooo ......++oooo###################################oo+ .......++ooooooooooooooooooooooooooooooooooooooo++ ........+oooooooooooooooooooooooooooooooooooooo+.. .........++++oooooooooooooooooooooooooooooooo++... ............+++++++ooooooooooooooooooooooooo++.... ..................+++++++oooooooooooooooooo+...... ........................+++++++oooooooooo++....... ..............................+++++++ooo++........ ....................................++++.......... pic = polygon(pic, [13 13 47 47], [8 12 12 8], '', '-') .................................................. .................................................. .................................................. .................................................. .+++++++++++++++++++++++++++++++++++++++++++++++++ ..+ooooooooooooooooooooooooooooooooooooooooooooooo ..++oooooooooooooooooooooooooooooooooooooooooooooo ...++ooooooo###################################ooo ....+ooooooo#---------------------------------#ooo .....+oooooo#---------------------------------#ooo ......+ooooo#---------------------------------#ooo ......++oooo###################################oo+ .......++ooooooooooooooooooooooooooooooooooooooo++ ........+oooooooooooooooooooooooooooooooooooooo+.. .........++++oooooooooooooooooooooooooooooooo++... ............+++++++ooooooooooooooooooooooooo++.... ..................+++++++oooooooooooooooooo+...... ........................+++++++oooooooooo++....... ..............................+++++++ooo++........ ....................................++++.......... pic = polygon(pic, [1 30 1], [1 20 20], '\', '') \................................................. \\\............................................... \..\.............................................. \...\\............................................ \+++++\\++++++++++++++++++++++++++++++++++++++++++ \.+oooo\\ooooooooooooooooooooooooooooooooooooooooo \.++ooooo\\ooooooooooooooooooooooooooooooooooooooo \..++ooooo\\###################################ooo \...+ooooooo\\--------------------------------#ooo \....+oooooo#\\-------------------------------#ooo \.....+ooooo#--\\-----------------------------#ooo \.....++oooo####\\#############################oo+ \......++ooooooooo\\oooooooooooooooooooooooooooo++ \.......+oooooooooo\\oooooooooooooooooooooooooo+.. \........++++oooooooo\\oooooooooooooooooooooo++... \...........+++++++ooo\\oooooooooooooooooooo++.... \.................++++++\\ooooooooooooooooo+...... \.......................++\++++oooooooooo++....... \..........................\\.+++++++ooo++........ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\......++++..........