Posts about apcshttp://cestlaz.github.io/categories/apcs.atom2018-09-19T23:47:47ZMike ZamanskyNikolaHow early for APCShttp://cestlaz.github.io/posts/how-early-apcs/2018-07-15T07:11:03-04:002018-07-15T07:11:03-04:00Mike Zamansky<div id="outline-container-org09052d5" class="outline-2">
<h2 id="org09052d5"></h2>
<div class="outline-text-2" id="text-org09052d5">
<p>
In what grade should students take APCS? This question comes up from
time to time.
</p>
<p>
I've heard answers ranging from middle school through never. Infact,
years ago, my chairman relayed a conversation he had with Marvin
Minsky where he asked Minsky what the high schools should be teaching
with respect to CS. The answer was "nothing." This was then amended to
"teach them to type." Of course this was a long time ago but I believe
the sentiment was that college was the right time and the high schools
don't know what they're doing and will just screw up the
kids. Actually, I still see some of this attitude today and it gets
passed down where high school teachers sometimes don't want the
middle schools to "mess up their kids" and on down the line.
</p>
<p>
At this point, it's pretty clear that you can do good CS at the high
school level and as things are being pushed down the grades we'll
eventually figure out what's right and when.
</p>
<p>
Still, within the high school the question of what grade for APCS-A
remains.
</p>
<p>
There isn't a single right answer for this but I can share
my experience and what I ended up deciding when I developed things at
Stuy.
</p>
</div>
</div>
<div id="outline-container-orgb77322e" class="outline-2">
<h2 id="orgb77322e">MATH BOOKS and Physics First</h2>
<div class="outline-text-2" id="text-orgb77322e">
<p>
As parents, my wife and I learned early on that we'd have to
supplement what our kids would learn in school, particularly in terms
of math and science. I was in charge of math. Since I used assorted
books to help, math time came to be known simply as "MATH BOOKS." It's
funny that now while my kids don't look back super fondly on MATH BOOKS
they agree that it was an important thing for us to do.
</p>
<p>
I discovered, as I'm sure many parents do, that there are times when a
kid is just not ready for a subject. At one point I tried to introduce
Algebra too early and saw it wasn't going to take so I pulled back. A
while later, we tried again. This time it was clear that they could do
the mechanics and solve problems based on rules and formulae but they
really didn't "get it." A third attempt some time later, they were
ready. They mastered the subject with deep understanding easily. It
could be argued that the early exposure helped but I don't think it
did.
</p>
<p>
The takeaway here is that kids can do the mechanics and appear to
succeed but if it's too early, they don't really learn the subject.
</p>
<p>
I saw this on a larger scale with "Physics First." At Stuy, most
freshmen would take Bio in 9th grade followed by Chem and then Physics
in their Junior year. Physics first kids would take Physics in the 9th
grade. I don't have any evidence for this but based on my inquiries
over the years it seemed that the kids who took physics in their
junior year had a deeper understanding of the subject.
</p>
<p>
I also personally saw this when teaching math classes early on in my
career. Most Stuy freshmen take geometry. The math aces take
precalc or calc but a few weren't math aces but were the star in their
middle school. They were pushed through geometry in 8th grade and
started Stuy in Algebra 2 and Trig. The majority of these kids that I
taught could spit back all the formulas and theorems from geometry but
very few were actually ready for Alg2/Trig and struggled
considerably.
</p>
</div>
</div>
<div id="outline-container-org6027168" class="outline-2">
<h2 id="org6027168">APCS</h2>
<div class="outline-text-2" id="text-org6027168">
<p>
So what about APCS? At Stuy we always taught a superset of the old
APCS-AB. It's mostly APCS-A in the Fall semester and Data Structures
in the Spring. When I started, there was no prerequisite for APCS so I
had students in all grades. Mostly Juniors and Seniors but a few
Sophomores. I think I only had a freshman in APCS once and they were
an outlier.
</p>
<p>
Some of my sophomores were ready, more could merely spit back material
and do the mechanics - enough to pass the APCS-AB exam but they really
didn't get it. There were some, however that weren't ready. These were
very bright kids and while I can't say for sure, deep down I very much
suspect that if they took my class a year later they would have done
much better and they might have followed a very different path towards
their future.
</p>
<p>
As a teachers we can change lives for the better and in fact save
lives. We can also do great damage. Because of the latter, teachers
should follow the mantra "first do no harm." This led me to a general
rule of taking kids into APCS-AB until their junior year. If I were to
allow a sophomore in I wanted to be pretty sure that the kid was
ready.
</p>
<p>
Later we were able to create a sophomore year CS requirement which
gave all kids exposure to CS prior to APCS-A (we still taught AB but
by now only the A exam was offered) and also gave us a platform to vet
the outliers who might be ready for APCS. For those kids, in addition
to an interview we had them self study APCS-A, do a project and sit
for the APCS-A final exam and then we'd add them to the second half of
our AP class.
</p>
</div>
</div>
<div id="outline-container-orgd8cee81" class="outline-2">
<h2 id="orgd8cee81">Has it worked?</h2>
<div class="outline-text-2" id="text-orgd8cee81">
<p>
By and large the system has worked. Kids now get an intro in the 10th
grade followed by APCS in 11 and more electives if desired in the
12th. For the kid that's truly ready for APCS in the 10th grade, we
have a path. We don't make it easy but the path is there.
</p>
<p>
Over the years we've had some CS superstars come through the
program. Some have pushed back – "why do I have to take the intro?"
"Why can't i start right away in APCS?" – after all was said and
done, all but one came back to say that we did it the right way and
that they benefited from all our classes.
</p>
<p>
At Stuy, it seems that for most students, 11th grade is right for our
APCS. Between academic maturity, other classes, scheduling and
everything else, it seems that this works the best for us.
</p>
</div>
</div>
<div id="outline-container-org795a0b8" class="outline-2">
<h2 id="org795a0b8">Why the rush?</h2>
<div class="outline-text-2" id="text-org795a0b8">
<p>
Frequently the question as to when to teach APCS revolves around how
early it can be taught. I have to ask - why are we so caught up with
doing things so early?
</p>
<p>
If we're just pushing college level courses down to high school then
what's the point? The kids will have to take the classes again if
they're going to major in CS anyway.
</p>
<p>
If you have a program that doesn't duplicate college courses you might
want to have kids finish APCS-A earlier but I wonder how early you
really need.
</p>
<p>
As a society we keep pushing things down younger and younger. We're
pushing AP classes like history or APCS-P down to 10th grade or even
earlier. You have to ask, is a course that's developmentally
appropriate for a 18-22 year old developmentally appropriate for a 14
or 15 year old? Probably not. You also have to ask that if it makes
more sense to push further ahead or if it's better to do enrichment at
a level the kids can handle.
</p>
<p>
I'm an enrichment over acceleration guy but other people differ. Just
like the question of when for APCS, there's probably not a single
right answer to this.
</p>
</div>
</div>
<div id="outline-container-orgd302a34" class="outline-2">
<h2 id="orgd302a34">Last words and what should you do?</h2>
<div class="outline-text-2" id="text-orgd302a34">
<p>
As I said up front, there's no right answer to this. I'm still
convinced that 11th grade is probably the best general entry point for
APCS-AB but if I were only teaching APCS-A maybe I'd shift it down a
year. My gut tells me no, partially based on teaching non APCS to 8th,
9th, and 10th graders but maybe. Of course, we all teach different
students in different environments so your mileage may vary.
</p>
<p>
There are also those outlier kids that can truly master the subject at
an earlier age, I'm not really considering them here but they should
be accommodated when possible.
</p>
<p>
If you've been running a program for a while, look at the data - not
how many kids pass the exam - look at how many master the next level
material. If your kids next class is data structures in college, find
out how well prepared they were and see if and how it maps to the
grade in which they took APCS. If you're just starting, I'd recommend
erring on the side of caution - remember "do no harm."
</p>
<p>
If you have to teach CS and it turns out you have to teach it when the
kids are too young to master APCS-A then don't teach APCS-A, teach
great CS at a level that's appropriate.
</p>
<p>
All of this will work itself out in time. Until we get there, there
will be some mis-steps - I know I've had mine. As long
as we continue to move the kids forward and give them something that they
wouldn't have been getting otherwise while we figure all this out,
we're doing pretty good.
</p>
</div>
</div>Teaching APCS-A for the first timehttp://cestlaz.github.io/posts/teaching-ap-first-time/2017-08-23T15:56:46-04:002017-08-23T15:56:46-04:00Mike Zamansky<div id="outline-container-orgbbdb472" class="outline-2">
<h2 id="orgbbdb472"></h2>
<div class="outline-text-2" id="text-orgbbdb472">
<p>
I got an email from a friend the other day. Among other things, he
mentioned that he would be teaching APCS-A for the first time this
year. He's a little trepidatious. He knows his stuff but he hasn't
really done much using Java.
</p>
<p>
I was going to respond in an email but thought I might share here
instead.
</p>
<blockquote>
<p>
TL;DR - for all you APCS teachers who are new or new to Java - learn
your core CS, lean on your resources and support and it's OK to tell
your kids "I don't know, I'll get back to you.". Don't worry, you'll be great.
</p>
</blockquote>
<p>
The first time I taught APCS was some time around 1991 or 1992. It was at
<a href="http://www.sewardparkhs.com/Famous-Alumni/">Seward Park</a> <a href="http://www.sewardparkhs.com/History/">High School</a>. It was the AB curriculum - that is one
semester of programming in Pascal and one semester of Data Structures
and Algorithms. Being a computer science major the core material was
never a concern. I had taken APCS the first time it was offered in May
1984 in Pascal and while most of my college and pre-teaching professional work
was in C, my college started it's CS sequence with Pascal. I was more
concerned with the actual teaching part. I had taught math for a year
and a half at that point but never CS and by any measure I was still
wet behind the ears. I never finished that first experience because I
was excessed to Stuy mid semester. I wasn't particularly happy with my
performance but looking back, I think I did a pretty good job given
the situation and my experience.
</p>
<p>
After teaching math for a year and a half I was back in APCS at
Stuy. Still in Pascal. I spent the next few years figuring out how to
teach CS and APCS in particular along with starting a couple of new
classes. When the College Board decided to move the AP class to C++ I
was happy, sad and a little worried. Pascal had a bunch of limitations
but I had never used C++. True, I was a C programmer at heart but I
had never really done the OOP thing. I did, as it turned out, design a
number of my C systems in an Object Typed design: I would use a single
file per "class" where local variables were de facto instance
variables and functions in the file were methods and each file was a
singleton class. I read <a href="https://www.amazon.com/Object-Oriented-Analysis-Design-Applications-3rd/dp/020189551X/ref=sr_1_1?ie=UTF8&qid=1503519770&sr=8-1&keywords=Grady+Booch">Booch</a> and <a href="https://www.amazon.com/Object-Oriented-Software-Construction-Book-CD-ROM/dp/0136291554/ref=asap_bc?ie=UTF8">Meyer</a> on my own but I had no
schooling in OOP and no professional experience.
</p>
<p>
As it turned out, I didn't have to worry. I knew my CS and while it
took me a while to become comfortable with OOP, the class, and of
course I knew this from the get go, started from nothing and built
up complexity a step at a time. The worst that might have happened is
that some of my solutions might have been more C-esque than C++.
</p>
<p>
The move to Java was a little more jarring. Now we had a totally new
language. I couldn't fall back on C. It removed memory management and
explicit pointers and it had to be used in an Object Oriented
manner. I remember asking Mike Schidlowsky, a former student turned
friend who was the Java consultant on the Java edition of Sedgewick's
<a href="https://www.amazon.com/Robert-Sedgewick-Algorithms-Fundamentals-Structures/dp/B008VR3ZH4/ref=sr_1_4?ie=UTF8&qid=1503520269&sr=8-4&keywords=schidlowsky">Algorithms</a> book how to do something. It had to do with passing and
modifying arrays. In C there were a number of ways to accomplish what
I wanted to do. In Java, I couldn't figure out how to do it the way I
wanted. My friend Mike told me "you just don't do it that way in
Java." Again, it turned out that I didn't have to worry. The basic
coding was still the same as were the data structures and
algorithms. The only challenge was that I had to get into a Java OOP
mindset which it turned out wasn't that hard.
</p>
<p>
While I never really warmed up to OOP - I find other paradigms more
natural for me, I knew my CS and got more and more comfortable with
the Java (or C++) way of doing things as time wore on. Sometimes I
would say "I don't know" or "let's figure it out" but that's OK.
</p>
<p>
Nowadays, there are many more resources available for CS teachers. If
you're new, lean on them. Use the mailing lists, stackexchange,
facebook groups. Online resources like repl.it, codehs.com etc. Yes,
it's true that you'll be better next time around and even better years
down the road but right now, you're probably better than you think.
</p>
<p>
A number of my former students volunteer for <a href="https://www.tealsk12.org/">TEALS</a> - a really great
program that brings software engineers into the classroom to work with
non-CS teachers to deliver instruction. A number of my kids have
shared the following sentiment:
</p>
<blockquote>
<p>
</p>
<p>
I don't know if I'm really helping
the teacher to become self sufficient or if I'm a great teacher but I
do know one thing - while I'm there, the kids are getting a hell of a
lot more than if I wasn't there."
</p>
</blockquote>
<p>
– Remember that as well.
</p>
</div>
</div>A Plea to AP teachers- don't measure yourself by your scoreshttp://cestlaz.github.io/posts/teachers-you-arent-your-test-scores/2017-07-06T17:22:10-04:002017-07-06T17:22:10-04:00Mike Zamansky<div id="outline-container-orgc367f28" class="outline-2">
<h2 id="orgc367f28"></h2>
<div class="outline-text-2" id="text-orgc367f28">
<p>
AP scores just came out. As usual, I see the posts and take part in
conversations where teachers talk about their results. Some are happy
about their results, some aren't, some don't really care.
</p>
<p>
I just want to make a plea to all AP teachers out there:
</p>
<p>
<b><b>Don't let your value be dictated by the college board or any other
exam.</b></b>
</p>
<p>
I never really cared much about my students' actual AP scores. There
were a number of years when I never even saw the results. Of course, I
had a population that would do reasonably well regardless of teacher
so I was never placed under any pressure to "do better." One year -
while the APCS-AB exam was still offered, my principal called me down
to discuss the results to see if we could get more kids scoring 4s and
5s (which most of the kids already did). I told him that I thought
we were doing fine, explained why I couldn't advocate more teaching to
the test (such as more than paying lip service to the case study or
more rote practice on the multiple choice), and told him how I
measured our success as a program. He was happy with my answer and
that was that.
</p>
<p>
The AP exam is one test on one day and in my opinion the least
valuable measure of my students' achievement. This is one of
the reasons I was so dismayed by the CSEd community's efforts in
pushing the AP exams - not the class or the subject but the actual exam.
</p>
<p>
So, how should you judge your success? That's up to you. I can only
tell you how I judge myself.
</p>
<p>
First and foremost - and I know this sounds cheesy - are you a "force
for good" in your student's lives. Do you leave them in a better
place? Have you opened the door to a possible future for them? Have
you helped them grow? Beyond that, have they progressed in your
subject and as students in general.
</p>
<p>
I've had kids "fail" the AP exam and go on to wonderful careers in
tech and come back to thank me for giving them their start. I've also
had kids that have gone into other fields but appreciate what we've
done for them. I've also had my failures and I do mean my
failures. Students I couldn't reach or couldn't figure out how to
help.
</p>
<p>
As teachers, we work day to day trying to improve but we can get a
great overview of how we're doing by using a much longer feedback
loop - looking at what our graduates are up to. When young teachers
would comment on former students coming back or running into them at
tech events that they would have graduates of their own in a few years
and invariably they do.
</p>
<p>
To really evaluate how you're doing you have to go with the long
game. Very few people get that. I remember talking to a Google
Executive while I was designing CAPE 2010. He said something to the
effect of "I know we won't know if this program works for about ten
years but we'll have to come up with something short term to satisfy
the powers that be." That so few "get it" and need instant feedback
is one of the reasons that our society is so test driven. We shouldn't
be. Our focus should be on helping the students learn and progress.
</p>
<p>
So don't get distressed over AP results and don't get to high on them
either. Certainly don't use them to drive what and how you teach. Let
your students and your conscience be your guide.
</p>
</div>
</div>Advent of Code 2016http://cestlaz.github.io/posts/advent-of-code-2016/2016-12-03T15:25:26-05:002016-12-03T15:25:26-05:00Mike Zamansky<p>
Once again, it's time for <a href="http://adventofcode.com">Advent of Code</a> - a series of small
programming problems released once a day.
</p>
<p>
I wrote a bit about it <a href="http://cestlaz.github.io/posts/2015-12-15-advent.html/">last</a> <a href="http://cestlaz.github.io/posts/2015-12-17-im-an-idiot.html/#.WEMqBB9ieYQ">year</a> and you can still find last years
problems <a href="http://adventofcode.com/2015/">here</a>.
</p>
<p>
It's only day three but so far, all of the problems look really nice
for students in APCS-A or any similar intro course. I'm thinking of
looking at a couple of the problems this week with my class at Hunter.
</p>
<p>
I didn't think about this much last year but one thing I really like
about the competition is that each problem comes in two parts. You're
first presented with the problem and the input and once you put in the
correct answer, you're presented with part two.
</p>
<p>
This can be annoying at times, particularly when it requires a large
code rewrite but it also means that well designed, not too specific
solutions are rewarded.
</p>
<p>
It's not quite the same as changing the specs on a project mid way but
it does encourage thinking about more than just solving a super
specific problem.
</p>
<p>
Check out <a href="http://adventofcode.com">Advent of Code</a> and see if it's something you or your classes
might enjoy.
</p>I guess I'm a dumbasshttp://cestlaz.github.io/posts/2014-02-27-dumbass.md/2014-02-27T00:00:00-05:002014-02-27T00:00:00-05:00Mike Zamansky<div><p>I like a fairly informal atmosphere in my classes. Students have to
know that there's a line between teacher and student but I also want
them to feel like we're all part of the Stuy CS family.</p>
<p>Whenever we start a new term, it takes a while to break down the
walls. The students don't know what to expect of me, can they trust
me? Am I a bozo? Who knows.</p>
<p>It helps when some of the class had me as a teacher before, but it still takes time.</p>
<p>I'm glad that this term, things are coming along nicely.</p>
<p>Let me share what happened in class today.</p>
<p>I was introducing merge sort - their first nlgn sorting
algorithm. Before class, one of the students slipped off his seat and landed on the floor with a thud. He
was fine although the brief butt, if you would, of jokes.</p>
<p>I relayed a story - many years ago, Ilya, one of the gang, was accused
of being a dumbass. He responded "hey, it's never missed the seat." The
class had a good laugh over it.</p>
<p>Fast forward a bit.</p>
<p>I had a deck of cards I wanted sorted. As a Stuy grad, I'm as lazy as
the next guy so I didn't want to sort them, but I also didn't want to
violate one of our two class tenets "Don't be a jerk" so rather than
giving the cards to a student to sort, I split the deck in half and
gave each half to a student.</p>
<p>They quickly caught on and subdivided the deck and gave away their
halves. We did this until all the students had, at some point had one
or more cards.</p>
<p>Then we got to the merge part. Each student sorted his or her pile and
passed it back to the student who they got the cards from. This
student then merged the two piles and passed the cards back.</p>
<p>As the cards made their way back to me a student noted "hey, one of my
piles isn't in order." I commented that "the algorithm might fail if
at some points you give your cards to a dumbass." This got a good
laugh.</p>
<p>Finally, two pile of cards made their way to me and I started to merge
then. At which point, I promptly dropped the cards all over the floor.</p>
<p>One of my students exclaimed: "That's what happens when you give you
cards to a dumbass!!!!!"</p>
<p>It was awesome. We all cracked up.</p>
<p>I don't think I've been "insulted" quite so perfectly since my daughter
called me an idiot in class last year (I fed her the straight line and
she didn't disappoint).</p>
<p>I love it that my kids feel comfortable enough to joke but also know
where the line is.</p></div>Bucket Sortinghttp://cestlaz.github.io/posts/2013-11-27-bucket-sorts.md/2013-11-27T00:00:00-05:002013-11-27T00:00:00-05:00Mike Zamansky<div><p>In spite of the Java based annoyances I mentioned last time, I decided
to go ahead and do Radix sort with my AP students. I usually don't
cover it in AP Computer Science, but I like getting the kids to think
about using arrays as buckets as it's a new way of thinking for them and it does give a non-trivial application that combines ararys and ArrayLists.</p>
<p>It's a nice little algorithm. You start with an Array of integers:</p>
<div align="center">
<a href="http://cestlaz.github.io/img/radix/array1.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/radix/array1.png" class="" alt="">
</a>
</div>
<p>Then, place them in buckets based on the least significant digit:</p>
<div align="center">
<a href="http://cestlaz.github.io/img/radix/buckets1.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/radix/buckets1.png" class="" alt="">
</a>
</div>
<p>We then copy the numbers from the buckets back into the original array, keeping the order of the buckets (0->9).</p>
<div align="center">
<a href="http://cestlaz.github.io/img/radix/array2.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/radix/array2.png" class="" alt="">
</a>
</div>
<p>We then repeat this process on the 2nd least significant digit:</p>
<div align="center">
<a href="http://cestlaz.github.io/img/radix/step2.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/radix/step2.png" class="" alt="">
</a>
</div>
<p>And so on until we're done:</p>
<div align="center">
<a href="http://cestlaz.github.io/img/radix/step3.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/radix/step3.png" class="" alt="">
</a>
</div>
<p>It's a nice algorithm to teach on a number of fronts. </p>
<p>First, we get to combine Arrays and ArrayLists. Since we'll always
have 10 digits, the "bucket list" is of fixed size, while the
individual bucket lengths vary. This leads to the Array of ArrayLists
and we've got a single platform to compare and contrast the two. Which
is better when and why?</p>
<p>The algorithm itself is also worth talking about. </p>
<ul>
<li>It's relatively simple - we did it by hand before implementing it.</li>
<li>It's got some history worth discussing.</li>
<li>There are a number of other questions we can approach</li>
<li>How can we deal with negatives?</li>
<li>What about strings?</li>
<li>Will it always work (what about floating point numbers).</li>
</ul>
<p>Finally, we can talk about speed -- they're testing that now and we'll discuss our Radix sort vs the built in Arrays.sort() on Monday.</p>
<p>We'll do the n^2 and nLog(n) sorts a little later, but I think this
was a detour well worth taking.</p></div>Teaching Languageshttp://cestlaz.github.io/posts/2013-11-23-teaching-languages.md/2013-11-23T00:00:00-05:002013-11-23T00:00:00-05:00Mike Zamansky<div><p>Java's never been my favorite language either for using or for
teaching.</p>
<p>As a programmer, after starting with languages like Fortran
and Pascal, I really cut my teeth with C. More recently, Python has
been my go to language to get real work done. </p>
<p>From a teaching point of view most languages have good points
and bad ones. When the AP class went from Pascal to C++ I lamented
losing the simplicity and the low cost of entry. On the other hand,
C++ gave us objects (not that I'm a big OOP guy), separate files, the
ability to use tons of real world libraries and more.</p>
<p>Moving to Java simplified things in a number of ways but removed
memory management. If we didn't teach that along with the stack frame
in our Systems class, I think our kids would be missing something very
important.</p>
<p>I was reminded of some of Java's limitations as a teaching language over the past couple of days.</p>
<p>As posted earlier, I had my AP students create their own class to
mimic the Java ArrayList. Before introducing the ArrayList in Java, I
wanted to introduce generics:</p>
<pre class="code literal-block"><span></span>public class myList<T> {
T[] data;
public myList() {
data = new T[10];
}
// much more not shown
}
</pre>
<p>Turns out, you can no longer do this.</p>
<p>After doing some searching, there does appear to be a way to get this
effect but it was certainly not something I wanted to do with my
classes. I was looking for something more pedagogically sound - an
easy way to show the concept and a way to springboard to an ArrayList.</p>
<p>Oh well...</p>
<p>So, we finished ArrayLists and I was mapping out a plan for Monday. I
thought Radix sort would be cool -- we already introduced using an
array to tally votes when we did the mode. This seemed to be a natural
extension. It would combine Arrays and ArrayLists and illustrate when each is appropriate.</p>
<p>First the kids would set up an array of 10 buckets, each being an ArrayList:</p>
<pre class="code literal-block"><span></span>public class Buckets {
ArrayList<Integer>[] buckets;
public Buckets() {
buckets = new ArrayList<Integer>[10];
for (int i=0;i<10;i++)
buckets[i] = new ArrayList<Integer>();
}
// much more not shown
}
</pre>
<p>Unfortunately, Java type safety once again reared its ugly head. OK,
maybe not ugly to a programmer, but ugly to a teacher. You can't do
it. You can do it with an old school ArrayList without the generic:
<code>ArrayList[] buckets = new Arraylist[10];</code> but of course, this
leaves you open to type mismatch problems.</p>
<p>Once again, Java provides a convoluted workaround that might be fine
for a professional programmer, but for a student, it would be nuts.</p>
<p>I might go ahead with the Radix sort lesson anyway, we'll see, but it
would be nice if I could teach this level of course without having to
fight the implementation language.</p></div>Stuyablo IIhttp://cestlaz.github.io/posts/2013-10-27-stuyabloII.md/2013-10-27T00:00:00-04:002013-10-27T00:00:00-04:00Mike Zamansky<div><p>Last week in my AP classes, we were working on inheritance.</p>
<p>So, what to do?</p>
<p>Last time around I had my classes work on a "speed dating" program -
StuyDater. Back then JonAlf had his classes work on Stuyablo, that
classic dungeon crawl.</p>
<p>I still plan on reworking the StuyDater project, but first I decided
to do my take on Stuyablo. Of course, we've improved on it. This time
it's <strong>Stuyablo II</strong>. The next guy will have to do <strong>Stuyablo III - in
3D</strong>.</p>
<p>We used the concept of a base class <strong>Character</strong>:</p>
<pre class="code literal-block"><span></span>public class Character {
private int health;
private String name;
public String toString() {
return Name;
}
// etc
}
</pre>
<p>And then some derived classes such as:</p>
<pre class="code literal-block"><span></span>public class Wizard extends Character {
private int mana;
// etc
}
</pre>
<p>We spend time dealing with public vs private vs protected, issues with
constructors, super and the like but then the weekend was upon us.</p>
<p>So, what was the assignment - we broke up into groups. Each group had
to design one aspect of the project. Some groups had to decide on what
would make up a player character. Perhaps a fighter or a wizard. What
base level attributes are needed? What methods? What do they need as
parameters and what do they return? What will the combat system look
like? </p>
<p>Another groups had to work on non player characters. Yet others
designed the game driver.</p>
<p>None of them were supposed to actually write finished code. </p>
<p>I asked them to bounce around ideas on our mailing list over the
weekend.</p>
<p>It's been amazing to watch the discussion. It's now Saturday evening
and throughout the day there's been a constant flow of ideas and
discussion. I love it when the classes are into the projects. </p>
<p>Monday we're going to sync up, finalize the design, and then start
writing this thing.</p>
<p>It's going to be fun.</p></div>Who won the election -- Quadratic to Linear Time!!!!!http://cestlaz.github.io/posts/2013-03-23-Who_won_the_election-Quadratic_to_Linear_Time.md/2013-03-23T00:00:00-04:002013-03-23T00:00:00-04:00Mike Zamansky<div><p>Last week was crazy. Busy, stressful, late night after late night. It
ended, though, on a great note.</p>
<p>A young lady in my intro class found me in my office near the end of the day:</p>
<blockquote>
<p>Student: Mr. Z, I wanted to make sure to catch you before vacation!</p>
<p>Me: What's up?</p>
<p>Student: I wanted to tell you that today's lesson was AWESOME!!!!!!</p>
</blockquote>
<p>Wow. I've been teaching 23 years and that's never happened before!!!!</p>
<p>So, what was the hubbub about?</p>
<p>We've been doing list processing in Python over the past few days. We already did the basics, such as finding the largest element in a list:</p>
<p _="%" endhighlight>{% highlight python linenos %}
def find_max(L):
maxval = L[0]
i=0
while i<len if l>maxval:
maxval=L[i]
i += 1
return maxVal</len></p>
<p>We've also done basic searching, counting elements, removing elements, etc.</p>
<p>Today we started with finding the mode of a list of grades.</p>
<p>Most students approached the problem as a maximum problem. Assume the
first item is the mode and find it's frequency, then proceed through
the list each time seeing if the current node occurs more fequently
than the "mode so far." Pretty much the same idea as find_max (but in this case, returning a list of all the modes).</p>
<p _="%" endhighlight>{% highlight python linenos %}
def mode(L):
modecount = L.count( L[0] )
modes = [ L[0] ]
i = 1
while i < len(L):
c = L.count(L[i])
if c > modecount:
modecount = c
modes = [ L[i] ]
elif c==modecount and L[i] not in modes:
modes.append( L[i] )
i += 1
return modes</p>
<p>Pretty cool. The kids are doing something pretty sophisticated here. </p>
<p>Time to look deeper. We started running this on larger and larger data
sets. Things started really slowing down at about 20K. We then timed
things to get some numbers (thanks
<a href="http://stackoverflow.com/questions/5998245/get-current-time-in-milliseconds-in-python">StackOverflow</a>). </p>
<p>What was going on. The students pretty quickly honed in on the line
that called L.count(L[i]) -- <strong>Hidden Complexity</strong>. </p>
<p>We haven't done big-O notation but the class easily saw that count had
to go through the entire data set and we ended up with an N^2
algorithm. For example, if we have 10 items, the main loop executes 10
times and each time, count goes through the entire list (10 items) as
well. If we go to 100 items, it becomes 100x100.</p>
<p>What to do????</p>
<p>Time to talk about what's probably the most discussed instance of mode
finding - elections. The winner is "the mode of the ballots."</p>
<p>Of course we don't use the above algorithm. We usually tally or count the ballots. We go through the ballots once, each time adding one to the appropriate candidates "bucket." </p>
<div align="center">
<a href="http://cestlaz.github.io/img/tally.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/tally.png" class="" alt="">
</a>
</div>
<p>From here, it's a short step to see that we can use a list. It's
indices represent the grade values and the data in the list the counts
or tallies:</p>
<p _="%" endhighlight>{% highlight python linenos %}
def fastmode(L):
i=0
counts = []
while i<max(L)+1:
counts.append(0)
i+=1
i=0
while i < len(L):
counts[ L[i] ] += 1
i += 1
modecount = max(counts)
modes = []
i=0
while i < len(counts):
if counts[i]==modecount:
modes.append(i)
i=i+1
return modes</p>
<p>We go through the list once to build the tallies and then the "tally"
list once to get the modes. Simple, straightforward, and linear
time!!!!!!!!!</p>
<p>The original routine started to hit a roadblock at about 20K items,
here we got to one million without breaking a sweat.</p>
<p>The take away:</p>
<ul>
<li>Get it working first.</li>
<li>Then profile to find your bottleneck</li>
<li>Look at the problem in a different way</li>
<li>Using data structures in a clever way can really improve performance.</li>
</ul></div>Pretty sneaky, Sishttp://cestlaz.github.io/posts/2012-01-11-pretty-sneaky-sis.html/2012-01-11T00:00:00-05:002012-01-11T00:00:00-05:00Mike Zamansky<div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"></div><div style="margin-left: 1em; margin-right: 1em;"><img height="200" id="il_fi" src="http://ecx.images-amazon.com/images/I/5103F3DHQ0L._SL500_AA300_.jpg" style="padding-bottom: 8px; padding-right: 8px; padding-top: 8px;" width="200"></div><br><div style="margin-left: 1em; margin-right: 1em;"></div><br><br><a href="https://www.google.com/search?q=connect+4&hl=en&prmd=imvns&source=lnms&tbm=isch&ei=Y74NT7zGJoTX0QHxv8zsBQ&sa=X&oi=mode_link&ct=mode&cd=2&ved=0CBUQ_AUoAQ&biw=1016&bih=623#"></a><br><a href="https://www.google.com/search?q=connect+4&hl=en&prmd=imvns&source=lnms&tbm=isch&ei=Y74NT7zGJoTX0QHxv8zsBQ&sa=X&oi=mode_link&ct=mode&cd=2&ved=0CBUQ_AUoAQ&biw=1016&bih=623#"></a><br><br>I've always lamented the fact that we don't have the time or structure to really teach our kids to program.<br><br>In their early classes, they learn syntax, algorithms, and some ways of storing data and while they will probably work on some larger projects as they study CS, kids seem to be mostly left on their own in terms of how to take a project from problem or idea to completion.<br><br>This frequently leads to poorly designed projects that are harder for the kids to write, debug, and modify. They end up with huge functions/methods no overall plan or design and everything's pretty much a mess<br><br>To try to address this, and having finished most of the A.P. curriculum and not wanting to diverge from the other teachers, I figured we'd develop a class project before I gave the class time for their final projects.<br><br>I'm not a huge game person, but since they decompose well, we decided on writing connect 4 - a game that can be described as tic-tac-toe but with four in a row, on a larger board, and WITH GRAVITY!!!!!!<br><br>Actually, the choice of project didn't matter that much so long as it was the right size -- this was more about how we develop a program than about the actual program itself.<br><br>I started by giving my classes about ten or so minutes to talk among themselves to design the program -- no guidance was given. About seven minutes in, I asked them to reflect on whatever they were discussing - if they were discussing a data structure, why? If class design, why? What was so important about whatever they were discussing that made it their first order of business.<br><br>After a while, we started to share thoughts as a group. Most suggestions revolved around details -- how to you check for a winner, how do you make a move. This made sense - we've spent much of the term dealing with writing code fragments to do things and not too much time thinking about overall design.<br><br>This lead to a healthy discussion of looking at things from the top down as well as bottom up.<br><br>By the end of the class, we had identified the key classes we'd need (Board, Player, UI, Game Driver) and had some idea as to how they would relate to each other. By the next morning, we added a data structure for the board.<br><br>Over the next few days we filled in the missing pieces. We moved up and down levels of abstraction being careful to discuss why we designed things the way we did and adapting pieces as needed.<br><br>By the end of the project we were able to accomplish the following:<br><ul><li>Students saw how to have classes refer to each other - that is, the Player class had an instance variable to hold the board, while the Game class had instances for Players as well as the Board). </li><li>We were able to use different user interfaces for the program -- starting with simple console input and then moving to a GUI -- all we had to do was extend the UI class.</li><li>Likewise, implementing a computer player (albeit a rather limited one) was trivial.</li><li>I also tried to show frequent testing and the idea of developing one concept at a time.</li><li>We discussed the idea that while design is important, there's a point where you can over design. Be aware of the scope of a project, what can generalize, and what shouldn't.</li><li>With a good design, it was also trivialize to change things like game rules, how to move, board size. etc.</li></ul><div><br></div>Based on preliminary feedback, I think the students have a much better ideas as to how to break down, design, and build up a project from design to implementation.<br><br>If any one's interested, the code is available <a href="http://code.google.com/p/ml1x-z-src/source/browse/#svn%2Ftrunk%2Fsrc%2Fc4">here</a>.<br><br>We'll see if it helps with the final projects, but I'm optimistic. Spending time highlighting the design and development process while building a project can only help.<br><br>Anyone else have interesting mid-size projects they do with their classes?<br><br><div class="blogger-post-footer"><img width="1" height="1" src="https://blogger.googleusercontent.com/tracker/468689896075458340-5982145998594622193?l=cestlaz.blogspot.com" alt=""></div>Where's Waldo - Text stylehttp://cestlaz.github.io/posts/2011-12-03-wheres-waldo-text-style.html/2011-12-03T00:00:00-05:002011-12-03T00:00:00-05:00Mike Zamansky<br><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-hMHnHYdTs4s/TtplhsggjFI/AAAAAAAAGqs/AwPiobAINw0/s1600/Screenshot%2Bat%2B2011-12-03%2B12%253A55%253A43.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="100" src="http://3.bp.blogspot.com/-hMHnHYdTs4s/TtplhsggjFI/AAAAAAAAGqs/AwPiobAINw0/s200/Screenshot%2Bat%2B2011-12-03%2B12%253A55%253A43.png" width="100"></a></div><br>Ok, it's a word search.<br><br>We're always looking for interesting applications to build lessons around. Over the years, I've tried different things when teaching 2 dimensional arrays. Simple game boards, representing a crossword puzzle, tables of various sorts, etc.<br><br>This year, <a href="http://www.jonalf.com/">JonAlf</a>, one of my amazingly talented colleagues, decided to go with building a word search. I decided to steal the idea. It's a great one.<br><br>I thought I'd use this post to go through the project and why I like it.<br><br>Ultimately, the students end up with a program that will generate an n by m word search filled with random words from a dictionary. We gave the kids a skeleton of the base class. The only actual code we had to supply was the method that loaded a dictionary file into memory. You can check out the assignment <a href="https://sites.google.com/a/stuycs.org/home/courses/ml1x/zamansky/work/hw-20-duetbd">here</a> and the finished code <a href="http://code.google.com/p/ml1x-z-src/source/browse/#svn%2Ftrunk%2Fsrc%2FWordSearch">here</a> (we updated the repository as the project developed).<br><br><br>The first part of the project are pretty mundane. The kids write a couple of constructors and toString. Basically just practice traversing a 2D array. The project starts to get interesting at part 2, when they write the methods that add words into the grid. First horizontally:<br><br><script src="https://gist.github.com/1428475.js?file=addWordH"></script><br><br>After they write the method to add words vertically, we can start to refine things. We notice that the routines are essentially the same. The only difference between adding a word horizontally and vertically is what we add to the row and column each time. For one, there is a delta column of + 1, for the other it's a delta row. Further, they realize that adding diagonal words just needs both deltas. This leads us to factoring out the common aspects of the code and writing something like:<br><br><script src="https://gist.github.com/1428495.js"></script><br><br>All of a sudden, they've written one piece of code that can add words in 8 orientations.<br><br>After filling the rest of the grid with random letters, we turn our attention to building a random puzzle.<br><br>This part of the project involves using an ArrayList of words. Our students frequently mix up array and ArrayList notation early on so by having a project that uses both but in clearly delineated areas, the students can be more comfortable with each.<br><br>For this piece, the code is again straight forward. Students run a loop that gets a random word from our dictionary and tries to place it in our grid at a random location choosing one of our possible orientations randomly. We get to see another nice little refinement again when we move from the typical first take at building a random puzzle which uses a three (or more) way if statement to select how to add words:<br><br><script src="https://gist.github.com/1428594.js?file=addWords1"></script><br><br>to using our more general addWords method described above:<br><br><script src="https://gist.github.com/1428599.js?file=addWords2"></script><br><br><br>When we're all done, we had some time to project the word search on the board and fun was had by all.<br><br>Peter, another one of our CS teachers had a great suggestion that I think I'll try. Start a competition to have the students modify the program so that it generates as densely packed a wordsearch as possible (giving higher scores first for longer words, then number of words).<br><br>Between the way the project broke down, the topics covered and the little refinements, I really enjoyed working with my classes on this project -- I'm hoping they enjoyed it as well.<br><br><br><br><div class="blogger-post-footer"><img width="1" height="1" src="https://blogger.googleusercontent.com/tracker/468689896075458340-2041316883816388484?l=cestlaz.blogspot.com" alt=""></div>