CCPS 209 Labs
CCPS 209 Computer Science II Labs
Ilkka Kokkarinen
Chang School of Continuing Education
Ryerson University
Version of March 17, 2022
Dramatis Personae
Lab 0(A): Plain Old Integers 9
Lab 0(B): Dublications 12
Lab 0(C): Reverse Verse 14
Lab 0(D): Lists Of Integers 16
Lab 0(E): All Integers Great And Small 18
Lab 0(F): Two Branching Recursions 20
Lab 0(G): ...Or We Shall All Crash Separately 23
Lab 0(H): More Integers Great And Small 27
Lab 0(I): Squaring Off 29
Lab 0(J): Similar Measures Of Dissimilarity 31
Lab 0(K): SufYix A
ays 33
Lab 0(L): I Can, Therefore I Must 35
Lab 0(M): Tower Blocks 36
Lab 0(N): Substring Parts 37
Lab 0(O): Chars To The Left Of Me, Integers To The Right... 40
Lab 0(P): Two Pointers 42
Lab 0(Q): Aboutturn Is Playfair 46
Lab 0(R): Frogs On A Box 49
Lab 0(S): Hamming Center 51
Lab 0(T): Clique Mentality 54
Lab 1: Polynomial I: Basics 57
Lab 2: Polynomial II: Arithmetic 60
Lab 3: Polynomial III: Comparisons 61
Lab 4: Extending An Existing Class 63
Lab 5: It's All In Your Head 64
Lab 6: Text Files I: Word Count 66
Lab 7: Text Files II: Tail 68
Lab 8: Concu
ency In Animation 69
Lab 9: Lissajous Curves 72
Lab 10: Computation Streams 74
Lab 11: And You Will Find Me, Prime After Prime 75
Lab 12: The Second Hand Unwinds 77
Lab 13: Recursive Mondrian Art 79
Lab 14: H-Tree Fractal 82
Lab 15: Zeckendorf Encoding 85
Lab 16: Egyptian Fractions 87
Lab 17: Diamond Sequence 90
Lab 18: Working Scale 93
Lab 19: Symbolic Distances I: Representation 97
Lab 20: Symbolic Distances II: Arithmetic 101
Lab 21: Symbolic Distances III: Comparisons 102
Lab 22: Truchet Tiles 104
Lab 23: Ulam-Wa
urton Crystals 106
Lab 24: Chips On Fire 110
Lab 25: Manhattan Skyline 113
Lab 26: FilterWriter 115
Lab 27: Stacking Images 117
Lab 28: All The Pretty Hues 119
Lab 29: In Timely Manner 122
Lab 30: Mark And Rewind 125
Lab 31: Region Quadtrees 127
Lab 32: Triplefree Sequences 130
Lab 33: Sardine A
ay 132
Lab 34: Preferential Voting 134
Lab 35: Multiple Winner Election 136
Lab 36: Rational Roots 137
Lab 37: Big Ten-Four 139
Lab 38: Euclid's Orchard 141
Lab 39: Hot Potato 144
Lab 40: Seam Carving 146
Lab 41: Geometry I: Segments 149
Lab 42: Geometry II: Polygons 153
Lab 43: Geometry III: Points In Polygons 156
Lab 44: Geometry IV: Convex Hull 160
Lab 45: Permutations I: Alge
aic Operations 164
Lab 46: Permutations II: Cycles 166
Lab 47: Permutations III: Lehmer Codes 169
Lab 48: The Curse Of The Clumpino 173
Lab 49: No Bits Lost 176
Lab 50: The Weight Of Power 181
Lab 51: Miller-Rabin Primality Testing 186
Lab 52: Linus Sequence 192
Lab 53: Tchoukaillon 194
Lab 54: All Hail The Mighty Xor 198
Lab 55: Accumulated Wisdom 201
Lab 56: Yind() Me A Find, catch Me A Catch 205
Lab 57: Flood Fill 208
Lab 58: Block Cellular Automata 211
Lab 59: Hitomezashi Golygons 214
Lab 60: Bit Deque 216
Lab 61: Save The Date 221
Lab 62: Worley Noise 226
Lab 63: Recursive Subdivision Of Implicit Shapes 231
Lab 64: Learning The Ropes I: Composition 235
Lab 65: Learning The Ropes II: Comparisons 239
Lab 66: Slater-Vélez Sequence 241
Lab 67: Lemire Dynamic Frequency Sampling 243
Lab 68: Interval Sets I: Dynamic Set Operations 246
Lab 69: Interval Sets II: Iteration 251
Lab 70: Cup Tournament Survival 254
Lab 71: The Gamma And The Omega 257
Lab 72: Lazy Generation Of Permutations 260
Lab 73: Newton-Raphson Fractals 263
Lab 74: Between The Lines 266
Lab 75: Square Coral 269
Lab 76: Sultan's Daughter 271
Lab 77: Generalized Chaos Game 273
This document contains the lab speciYications for the course CCPS 209 Computer Science II, as
compiled and taught over the years by Ilkka Kokkarinen for the Chang School of Continuing
Education, Toronto, Canada. It cu
ently offers a veritable buffet of 97 problem speci/ications for
students to freely pick their battles from, with new and exciting problems added on a semi-regular
asis as the author keeps coming up with them. These problems vary greatly in theme so that they
promise something for everyone, in spirit of The Love Boat. Students who have previously taken this
author's course CCPS 109 Computer Science I in Python should also note that unlike in the problem
set used in that course, these problems are not listed in their order of dif/iculty but in the order
in which they were created. Have no fear to take a look around all over this document to see which
topics interest you enough to raise the urge to hit the keyboard!
These problems drill in various aspects of the Java language and its standard li
ary, and introduce
(although occasionally between the lines) many classic ideas, concepts, techniques and algorithms
that will surely come handy in your future coding tasks in both school and working life. The Yirst
half of these labs mostly contains problems about the straightforward application of basic data
types such integers, a
ays and lists, whereas the problems in the second half are inspired by
discrete math, combinatorics and computational geometry. Occasionally these problems even reach
out into more remote areas such as fractal art, game theory and political science. (This last topic is
covered several problems about implementing and analyzing various voting systems.)
To work on these labs using IntelliJ IDEA, start by creating yourself new project named “209 Labs”
in which all your source code for these labs should go. Into that project, you will then manually copy
the automated JUnit tests from the instructor's GitHub repository CCPS209Labs for each lab that
you attempt to solve. First download this entire folder somewhere in your computer, and whenever
you embark on a new lab problem, copy the co
esponding JUnit test class in your labs project
folder. Once you have implemented all the methods of the labs so that they compile, IntelliJ IDEA
will allow you to run either one test or all the tests for that particular lab, for you to determine
whether your work passes the muster.
When IntelliJ IDEA initially complains about the import statements in the JUnit test class, you
should co
ect the problem once and for all by clicking the red lightbulb symbol to open a drop-
down menu from where you add JUnit 4 in your classpath. That is enough for IDEA to know to use
JUnit 4 for all the tests in the same project. Note that these tests are written in JUnit 4
framework, instead of JUnit 5, so be sure to add the co
ect framework in your classpath!
The fuzz acceptance tests in the JUnit test classes will try out your methods with a large number of
pseudorandomly generated test cases. These test cases are guaranteed to be exactly the same for
everyone working on the Java language and its standard li
aries, regardless of the particular
computer environment they cu
ently happen to be working on. Each pseudorandom fuzz test
computes a checksum from the results that your method returns for the test cases that were given
to it. Once this checksum equals the expected checksum computed and hardcoded into the test
method from the instructor's private model solution, The Man from Del Monte says yes and grants
you the green checkmark to cele
ate your beating this level with a nice glass of pineapple juice.
Your method is now co
ect and accepted as being black box equal to the instructor's private
solution, without having to have this private model solution available for comparison.
https:
github.com/ikokkari/JavaExamples
http:
www.scs.ryerson.ca/~ikokkari
https:
continuing.ryerson.ca
https:
continuing.ryerson.ca
https:
github.com/ikokkari/PythonProblems
https:
www.jet
ains.com/idea
https:
github.com/ikokkari/CCPS209Labs
https:
www.youtube.com/watch?v=YqmpVWzH4FM
Any discrepancy in the checksum reveals that your method returned a different answer than the
instructor’s private solution for at least for one test case. Unfortunately, such pseudorandom fuzzing
scheme makes it impossible to pinpoint any one actual test case for which your method is failing, or
determine for how many test cases your method disagrees with the instructor’s private model
solution. To alleviate this mechanism that may sometimes feel a tad bit passive aggressive, the JUnit
test classes also feature conventional tests with explicit test cases aimed to Ylush out the most
common bugs and edge case situations that seem to repeat in student solutions.
To test your code, you should also usually write your own main method in your classes and
hardcode your own test cases there. (No law of either nature or man prevents your classes from
having additional utility methods than merely those that our JUnit tests explicitly try out.)
All these JUnit fuzz tests are designed to run to completion within a couple of seconds at most per
each green checkmark, when executed on a modern off-the-shelf desktop computer at most Yive
years old. None of these automated tests should ever require minutes, let alone hours, to
complete. If any JUnit test gets stuck that way, that means your methods are doing something
algorithmically very inef/icient, either in time or in space. You should mercilessly root out all such
inefYicient designs from your method, and replace them with better algorithms that get to the same
end result at least an order of magnitude faster!
In all these labs, silence is golden. When it comes to your methods talking out of school all over the
text console, the rules for omertà are as strict as they are in the thorny badlands of Sicily. Since these
JUnit tests will pummel your code with a large number of pseudo-randomly generated test cases
harder than an old time detective giving a suspect the third degree under the hot lights, all
equired methods must be absolutely silent and print absolutely nothing on the console during
their execution. Any lab solution that prints anything at all on the console during its JUnit test
will be rejected and receive a zero mark. Make sure to comment out all your console output
statements you used for debugging before submitting your project.
Once you have completed all the labs that you think you are going to complete before the deadline,
you will and must submit all your completed labs in one swoop as the entire “209 Labs” project
folder that contains all the source Yiles along with the provided JUnit tests and any necessary text or
image data Yiles, compressed into a zip Yile that you then upload into the assignment tab on D2L. As
there is no partial credit given for these labs, please do not include any solutions that do not
pass the tests with /lying colours into your submission. To make it easier for the instructor to
tally up your working labs, you should make it clear in the project README Yile how many lab
problems you are claiming to have successfully solved.
Students should work on to solve these problems independently. Discussion of problems between
students is acceptable, as long as this discussion takes place solely at the level of ideas and no actual
solution code is passed between the students. This problem collection also has an ofYicial su
eddit
ccps209 to facilitate such discussion. Note that this su
eddit is intended only for the discussion
of these problems, and any course management issues should be handled elsewhere through the
appropriate channels.
http:
www.linfo.org
ule_of_silence.html
https:
www.reddit.com
ccps209
Lab 0(A): Plain Old Integers
JUnit: P2J1Test.java
The transition labs numbered 0(X) translate your existing Python knowledge into equivalent Java
knowledge all the way between your
ain and your Yingertips. You may already be familiar with
some of these problems from this author's other course CCPS 109 Computer Science I. Even if you
are coming to this second course via some other route, these problems are self-contained and
equire no speciYic background knowledge. Each 0(X) lab consists of up to four required static
methods that are effectively functions that involve no object oriented thinking, design or coding.
Inside your fresh new project, create the Yirst class that must be named exactly P2J1. If you name
your classes and methods anything other than how they are speciYied in this document, the JUnit
tests used to automatically check and grade these labs will not be able to even Yind your methods.
Inside the new class, the Yirst method to write is
public static long fallingPower(int n, int k)
Python has the integer exponentiation operator ** conveniently built in the language, whereas Java
unfortunately does not offer that. Exponentiation would be basically useless anyway in a language
that uses Yixed size integers that silently hide the overYlows that the integer exponentiation will be
producing in spades. (You should also note that in both Python and Java, the caret character ^
denotes the bitwise exclusive or operation that has nothing to do with integer exponentiation.)
Instead of integer exponentiation, your task is to implement the related operation of falling power
that is useful in many combinatorial formulas. Denoted syntactically by underlining the exponent,
each term that gets multiplied into the product is always one less than the previous term. For
example, the falling power 83 is computed as 8 * 7 * 6 = 336. Similarly, the falling power 105 equals
10 * 9 * 8 * 7 * 6 = 30240. Nothing essential changes here even for a negative base; the falling power
(-4)5 is computed with the same formula as -4 * -5 * -6 * -7 * -8 = -6720. Analogous to ordinary
exponentiation, n0 = 1 for any integer n.
This method should return the falling power nk where the base n can be any integer, positive or
negative or zero, and the exponent k can be any nonnegative integer. The JUnit fuzz tests are
designed so that your method does not have to wo
y about potential integer overYlow… provided
that you perform your arithmetic calculations with the long kind of 64-bit integers! If you use the
are 32-bit int type anywhere, a silent integer ove
low will make your method occasionally
eturn inco
ect results and fail the JUnit tests, even if that method worked co
ectly when you tried
it with your own small values of n and k.
public static int[] everyOther(int[] a
)
Given an integer a
ay a
, create and return a new a
ay that contains precisely the elements in
the even-numbered positions in the a
ay a
. For example, given the a
ay {5, 2, 3, 10, 2},
this method would create and return a new a
ay object {5, 3, 2} that contains the elements in
https:
github.com/ikokkari/CCPS209Labs
lo
maste
P2J1Test.java
https:
github.com/ikokkari/PythonProblems
the even-numbered positions 0, 2 and 4 of the original a
ay. Make sure that your method works
co
ectly for a
ays of both odd and even lengths, and for empty a
ays and singleton a
ays with
just one element. The length of the result a
ay that you return must also be exactly right so that
there are no extra zeros hanging around at the end of the a
ay.
public static int[][] createZigZag(int rows, int cols, int start)
This method creates and returns a new two-dimensional integer a
ay, which in Java is really just a
one-dimensional a
ay whose elements are one-dimensional a
ays of type int[]. The returned
a
ay must have the co
ect number of rows that each have exactly cols columns. This a
ay must
contain the numbers start, start+1, … , start+(rows*cols-1) in its rows in sorted order,
except that the elements in each odd-numbered row must be listed in descending order.
For example, when called with rows=4, cols=5 and start=4, this method should create and
eturn the two-dimensional a
ay whose contents show up as
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
when displayed in the standard matrix form that is more readable than the more truthful form
{{4,5,6,7,8},{13,12,11,10,9},{14,15,16,17,18},{23,22,21,20,19}},in reality a
one-dimensional a
ay whose four elements are themselves one-dimensional a
ays of integers that
serve as rows of this two-dimensional a
ay. In addition to rectangular grids of values, this scheme
can represent a
itrary ragged a
ays whose rows don't need to all be of the same length.
public static int countInversions(int[] a
)
Inside an a
ay a
, an inversion is a pair of two positions i
[i]>a
[j]. In
combinatorics, the inversion count inside an a
ay is a rough measure of how much “out of order”
that a
ay is. If an a
ay is sorted in ascending order, it has zero inversions, whereas an n-element
a
ay sorted in reverse order has n(n-1)/2 inversions, the largest number possible. (You will
encounter inversions again in this course, if you work through the labs 45 to 47 that deal with
permutations and their operations.) This method should count the inversions inside the given
a
ay a
, and return that count. As always when writing methods that operate on a
ays, make
sure that your method works co
ectly for a
ays of any length, including the important special
cases of zero and one.
Once you have written all four methods, add the above JUnit test class P2J1Test.java inside the
same project. Unlike in Python with its more dynamic nature, the JUnit test class cannot be
compiled until your class contains all four methods exactly as they are speci/ied. If you want
to test one method without having to Yirst write also the other three, you must implement the other
three methods as do-nothing method stubs that only contain some placeholder return statement
https:
github.com/ikokkari/CCPS209Labs
lo
maste
P2J1Test.java
that returns zero or some other convenient do-nothing value. Even better way to handle this
situation would be to have the method consists of the one-liner body
throw new UnsupportedOperationException();
that tells the caller in a controlled fashion that the method does not even pretend to achieve
anything at all, but gives up right away. Of course all such method stubs will immediately fail their
espective tests, as they properly should. However, their existence allows the JUnit test class to
compile and run cleanly so that you can start testing each one method the moment you have
properly replaced the above statement in its body with the actual Java code that solves the speciYied
problem. IntelliJ IDEA conveniently allows you to run all tests for that problem, or just one
individual test, just by clicking the green Play button next to each individual test in its source code.
Lab 0(B): Dublications
JUnit: P2J2Test.java
Create a new class named P2J2 inside the very same project as you placed your P2J1 class in the
previous lab. Inside this new class P2J2, write the following four methods.
public static String removeDuplicates(String text)
Given a text string, create and return a
and new string that is otherwise the same as text
except that every run of equal consecutive characters has been turned into a single character. For
example, given the arguments "Kokkarinen" and "aaaa
xxxxaaxa", this method would
eturn "Kokarinen" and "abxaxa", respectively. Only consecutive duplicate occu
ences of the
same character are eliminated, but the later occu
ences of the same character remain in the result
as long as there was some other character between these occu
ences. For the purposes of this
problem, the upper- and lowercase versions of the same character are considered different, so that
emoving duplicates from "Aaa
BBBCc" should return the result "AabBCc".
public static String uniqueCharacters(String text)
Create and return a new string that contains each character of text only once regardless of its
appearance count there, these characters listed in order that they appear in the original string. For
example, given the argument strings "Kokkarinen" and "aaaa
xxAxxaaxa", this method
should return "Kokarine" and "abxA", respectively. Same as in the previous problem, the upper-
and lowercase versions of the same character are treated as different characters.
You could solve this problem with two nested loops, the outer loop iterating through the positions
of the text, and the inner loop iterating through all previous positions to look for a previous
occu
ence of that character. But you can be more efYicient and use a HashSet
to
emember which characters you have already seen, and let that data structure help you decide in
constant time whether the next character is appended into the result.
public static int countSafeSquaresRooks(int n, boolean[][] rooks)
Some number of chess rooks have been placed on some squares of a generalized n-by-n chessboard.
The two-dimensional a
ay rooks of boolean truth values tells you which squares contain a rook.
(This a
ay is guaranteed to be exactly n-by-n in its dimensions.) This method should return the
count of how many remaining squares are safe from the rolling wrath of these rampaging rooks,
that is, do not contain any rooks in the same row or column.
Probably the best way to do this is to create and Yill in two one-dimensional boolean a
ays
safeRows and safeCols with n elements each. These a
ays keep track of which rows and
columns of the chessboard are unsafe. Initially all rows and columns are safe as far as we know,
since both a
ays are initially all false. However, to get count of the actual situation in the given
https:
github.com/ikokkari/CCPS209Labs
lo
maste
P2J2Test.java
https:
docs.oracle.com/javase/8/docs/api/java/util/HashSet.html
chessboard, loop through all the squares of the chessboard. Whenever you Yind a rook in some
position (row,col), mark that entire row and col as being unsafe in those respective a
ays.
After you have done this for all the squares throughout the entire chessboard, loop through the
safeRows and safeCols a
ays separately to count how many rows and columns are still safe.
Return the product of those two numbers as your Yinal answer.
public static int recaman(int n)
Compute and return n:th term in the Recamán's sequence, starting the count from term a1 = 1. See
the deYinition of this curious sequence on the linked Wolfram Mathworld page, or read more from
the page “Asymptotics of Recaman’s sequence”. For example, when called with n = 7, this method
would return 20, and when called with n = 19, return 62. (More values for debugging purposes are
listed at OEIS sequence A005132.)
To make your function fast and efYicient even when computing the sequence element for large
values of n, you should use a sufYiciently large boolean[] to keep track of which integer values are
already part of the generated sequence, so that you can generate each element in constant time
instead of having to loop through the entire previously generated sequence like some "Shlemiel"
tiring himself by running back and forth across the same positions. The size 10*n should be
enough, and yet this scheme uses roughly ten bits of heap memory for each number generated.
(Storing the encountered numbers into some HashSet
instance instead would burn
up memory at least an order of magnitude harder.)
http:
mathworld.wolfram.com/RecamansSequence.html
https:
XXXXXXXXXXgithub.io
log/2019/12/20/asymptotics-recamans-sequence.html
http:
oeis.org/A005132
http:
wiki.c2.com/?ShlemielThePainte
Lab 0(C): Reverse Verse
JUnit: P2J3Test.java
One last batch of transitional problems adapted from the instructor's collection of Python graded
labs. Only three methods to write this time, though. The JUnit test for these labs uses the
warandpeace.txt text Yile as source of data, so please ensure that this text Yile has been properly
copied into your course labs project folder.
public static void reverseAscendingSuba
ays(int[] items)
Rea
ange the elements of the given a
ay of integers in place (that is, do not create and return a
new a
ay) so that the elements of every maximal strictly ascending suba
ay are reversed. For
example, given the a
ay {5, 7, 10, 4, 2, 7, 8, 1, 3} (the pretty colours indicate the
ascending suba
ays and are not actually part of the argument), after executing this method, the
elements of the a
ay would be {10, 7, 5, 4, 8, 7, 2, 3, 1}. Given another argument
a
ay {5, 4, 3, 2, 1}, the contents of that a
ay would stay as {5, 4, 3, 2, 1} seeing
that its each element is a maximal ascending suba
ay of length one.
public static String pancakeScramble(String text)
This nifty little problem is taken from the excellent Wolfram Challenges problem site where you can
also see examples of what the result should be for various arguments. Given a text string,
construct a new string by reversing its Yirst two characters, then reversing the Yirst three characters
of that, and so on, until the last round where you reverse your entire cu
ent string.
This problem is an exercise in Java string manipulation. For some mysterious reason, even in this
day and age the Java String type still does not come with a reverse method built in. The
canonical way to reverse a Java string str is to Yirst convert it