Posts about pedagogyhttp://cestlaz.github.io/categories/pedagogy.atom2018-09-19T23:47:47ZMike ZamanskyNikolaTwo Faces of Project Based Learninghttp://cestlaz.github.io/posts/two-faces-of-pbl/2018-07-28T15:59:45-04:002018-07-28T15:59:45-04:00Mike Zamansky<div id="outline-container-org168d8a6" class="outline-2">
<h2 id="org168d8a6"></h2>
<div class="outline-text-2" id="text-org168d8a6">
<p>
If one looks at my twitter feed they'll notice that in addition to CS
Ed, another issue I'm passionate about is school reform or rather
resistance to what is popularly known as and mislabeled as school reform. I'm anti
vouchers, charter schools, high stakes testing and more. One of the
heroes of this resistance is education historian Diane Ravitch. I'm a
big fan of Diane's and she's one of the true great champions of public
schools, kids, and teachers. She blogged today about how a superintendent on Long Island <a href="https://dianeravitch.net/2018/07/27/new-york-district-on-long-island-shows-that-problem-based-curriculum-produces-better-results-than-test-prep/">replaced test
prep with project based learning</a>. The post which talks about how this
superintendent improved test results is worth a read. My only
quibble was that we shouldn't read anything into the results for a
variety of reasons including the fact that the group of students who
did the project based learning (PBL) units instead of test prep were
self selecting volunteers.
</p>
<p>
One of the comments caught my eye:
</p>
<blockquote>
<p>
PBL is just another “student-centered” fad…
</p>
<p>
PBL operates on the myth of “transference” perpetuated by non-educators.
</p>
<p>
…
</p>
</blockquote>
<p>
The comment continues on with a number of good points.
</p>
<p>
Why am I writing about it here? Because PBL is a big CS Ed buzzword
and like most buzzwords there's both truth at the root of the hype and
hype that distorts the truth.
</p>
<p>
When done right with the right group of kids, project based learning
can be wonderful but it takes a lot of time and effort. You can't just
set the kids loose to learn. You've got to train them to work
together, set up the project, as the teacher, you've got to know the
subject so as to know when to guide, when to tell, when to prod, and when to leave
them alone. Doing it right, at least for most students, is certainly
not giving them the instruction sheet and going off the check your
email.
</p>
<p>
On the other hand, it's easy to do it wrong. If you've got high
performing kids, they'll figure things out. If you've got a few high
performing kids, they can mask the fact that the majority of a group
isn't getting things. You might have an assignment where a kid figures
out a formula from discovered data and might be able to then use it to
make predictions but there's a good chance they won't understand why
it works or it's root derivation. That's where we need the teacher.
</p>
<p>
One of the dangers of bad PBL is that it's sexy. Kids are engaged and
it appears to work - particularly when the teacher doesn't know the
subject area. This is my great fear whenever I hear things about
teachers being "Lead Learners." Sure, when you're a converted
something else teacher moving into CS you won't know the subject
matter but that has to change over time. I've seen enough instances of
cases where teachers never develop their chops and just throw projects
at the kids augmented by scripted curricula or computer driver
content. The kids get through the class or program but are not
prepared for the next class or next level. I've seen this with the old
Cisco curriculum, any number of after school and summer programs -
some VERY highly regarded ones and I think we'll see more and more of
this in states that are pushing CSforAll without developing the
necessary pre and in service programs for their teachers.
</p>
<p>
Don't let my last two paragraphs leave you feeling that I'm anti
PBL. I'm not. It's great when done right and if you have thee time and
resources in your school and classes you should be using it when
appropriate.
</p>
<p>
If you want some pointers on how to get going in the right direction with PBL in CS check out <a href="https://www.amazon.com/Computer-Science-K-12-Imagining-possibilities-ebook/dp/B07DYDXBSH/ref=sr_1_1?ie=UTF8&qid=1532808363&sr=8-1&keywords=doug+bergman">this
book</a> by my buddy Doug Bergman. It's a great getting started guide by a
great teacher. He's basically Mr. PBL and he does it right. If you're new to CS you'll still need to learn content
and if you're new to teaching, you'll be developing your chops for
your entire career but it's a great resource to get you and then your
kids started on the journey.
</p>
</div>
</div>PD for people who know CShttp://cestlaz.github.io/posts/pd-for-cs/2018-06-27T14:41:59-04:002018-06-27T14:41:59-04:00Mike Zamansky<div id="outline-container-org6242d00" class="outline-2">
<h2 id="org6242d00"></h2>
<div class="outline-text-2" id="text-org6242d00">
<p>
I saw a couple of tweets from Sarah Judd this morning:
</p>
<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">A lot of CS Ed PD assumes you are new to CS. I really want CS Ed PD for people like us that came from a CS background and want to understand the pedagogy for CS in particular better. Do you know of some?</p>— Sarah Judd (@SarahEJudd) <a href="https://twitter.com/SarahEJudd/status/1011785286693552139?ref_src=twsrc%5Etfw">June 27, 2018</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr">Yes! I love SIGCSE and CSTA. I just feel like... Math teachers don't get PD that starts with "and this is how you add and subtract!" and I'd love more CS PD that assumes the content is there, and can focus on the pedagogy.</p>— Sarah Judd (@SarahEJudd) <a href="https://twitter.com/SarahEJudd/status/1011966102795059200?ref_src=twsrc%5Etfw">June 27, 2018</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
<p>
It wasn't the first time I've heard this refrain. Last year I attended
my first CSTA conference. I had numerous conversations with CS
teachers on the fact that everything was on an intro level in terms of
both content and teaching. Further conversations with local teachers
with stronger CS backgrounds led me to run a professional development
session at Hunter this past election day for more experienced CS
teachers at schools that offered more than the basics.
</p>
<p>
While it's not surprising that most of the PD opportunities for CS teachers are
rather rudimentary given that nationally most programs are new and
most teachers are new to the subject but there are a few deeper
reasons.
</p>
<p>
To start, there are big players in the CS Ed movement that are pushing
curricula and specific programs and that leads to scripted PD for
their products and not depth of knowledge nor deep pedagogical content
knowledge let alone basic pedagogy. Add to this the fact that many of
the "thought leaders" in the space don't have experience teaching CS
at the K12 level and in many cases don't have a background either in
teaching nor tech and you can see where the problem comes from. On top
of this we have the erosion of respect for teaching as a profession
where reformers are trying to take the teacher out of teaching and are
trying to reduce pedagogy to following scripts. This problem goes well
beyond CS Ed but as the new kid on the block it probably hits us
hardest.
</p>
<p>
In any case, preparing beginners is both necessary and appropriate for
the time being but we can and must do a better job than what's
currently "state of the art." At the same time we have to do something
with the CS teachers who indeed do have strong content knowledge but
don't feel comfortable with imparting that knowledge.
</p>
<p>
So, what should we do?
</p>
<p>
For new teachers the solution will ultimately have to come
from pre-service programs but what we end up getting is going to
largely be dictated on what's required by individual states. If states
merely require passing an exam like the Praxis CS exam which, from
what I can gather isn't a horrible content exam then we're going to
see CS teachers bumble through their early to mid careers while trying
to figure out how to teach CS much like I did way back when. If they
end up endorsing pre-service programs that are focused on specific
curricula - APCS-A for teachers, APCS-P for teachers, <a href="https://cestlaz.github.io/posts/math-for-math-teachers/">Math for Math
teachers</a> if you will but for CS, we're also not going to get strong
well prepared pedagogues. On the other hand if you can design a
program that has a strong pedagogical component to go along with the
content, you have a chance. Even with a well designed program
implementation will still be a challenge. Who will teach it? Education
professors who don't have CS backgrounds? CS professors with little
pedagogical training? Neither of those groups necessarily have any
real experience as actual K12 teachers. If you can find honest to
goodness experienced, strong K12 CS teachers to teach your pedagogy
courses that's a big win but that's going to be hard in most cases.
</p>
<p>
I think we designed a great program at Hunter and have a practical and
strong implementation plan. If you're going to be
at CSTA2018 you can hear all about it and why we designed it as we did
in the talk I'm giving.
</p>
<p>
For the more experienced I don't have a universal answer but I can say
what I'm planning. Teachers in NY have to complete 100 CTLE hours
every five years. For beginners, there are plenty of options, at least
content wise. For teachers who know CS, not so much. I was at a meetup
talking to a few friends a couple of weeks ago and one mentioned that
they get most of their hours in Math for America CS
workshops. Unfortunately more than a few of my CS teacher friends who
are in MFA tell me that the CS content in these workshops, while they
do satisfy the hours, are somewhat lacking on the CS / CS pedagogy
side.
</p>
<p>
Here's what I'm planning - we (Hunter) will host a once a month
dinner/session for CS teachers who are a little farther along CS
wise. I haven't worked out all the details yet but I've got a few tech
companies that are already interested in sponsoring and helping out
should we need anything and we'll probably set most of our agenda for
the year at the first session where I'll make my best guess at a
useful agenda. This is something I'm pretty excited about. It should
help create a network of more experienced CS teachers which will both
help bolster that segment of the community and provide a long term
resource to newcomers and it should be a lot of fun.
</p>
<p>
In some ways, this is why I ended up joining Hunter. Regardless of
what the city and state do, we're going to prepare the teachers and if
you have a well prepared teacher, you've got a shot.
</p>
</div>
</div>Teaching recursion early? Make sure to use a good tool.http://cestlaz.github.io/posts/recursion-early/2018-05-30T08:42:29-04:002018-05-30T08:42:29-04:00Mike Zamansky<div id="outline-container-org757f010" class="outline-2">
<h2 id="org757f010"></h2>
<div class="outline-text-2" id="text-org757f010">
<p>
I replied this tweet yesterday and thought I'd expound a bit.
</p>
<blockquote class="twitter-tweet" data-lang="en"><p lang="en" dir="ltr">We started kids using scheme on 10th grade at stuy so did recursion early. Not everyone got all of it but it think it made things much easier for those that you more CS later.</p>— Mike Zamansky (@zamansky) <a href="https://twitter.com/zamansky/status/1001508028439519233?ref_src=twsrc%5Etfw">May 29, 2018</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
<p>
We introduced recursion very early in our intro course at Stuy and I
think it worked well. In that course we started by using Racket (nee
Scheme) as the first programming unit. Originally we
started the kids out first using NetLogo or StarLogo and followed with
Scheme but after a few years we switched the order.
</p>
<p>
I wouldn't always recommend Scheme for a first course and in fact
frequently don't but given how the Stuy course was introduced and
developed it made sense and worked.
</p>
<p>
Was it worth doing things this way? I think so. Prior to that intro
course becoming a requirement I got to see students coming in from
different pathways to APCS. Some came in raw with zero formal
experience, some self taught, some through that intro course and some
having taken another more traditional intro programming course or
experience. The kids who started on Scheme had no more difficulty
mastering loops and iteration but had an easier time getting to the
more advanced recursive techniques. This wasn't a surprise - it wasn't
their first rodeo. This also jived with reports I read at the time
that felt that when students did recursion first, iteration was just
as easy but when they did iteration first, recursion was harder.
</p>
<p>
You can of course make a strong case that recursion isn't necessary
for a kid that isn't going to study more CS. I'll merely argue that
what we did at Stuy worked with that population and I wouldn't change
it. At the same time, I've helped a number of teachers design classes and programs
where we agreed that recursion first was not the way to go.
</p>
<p>
In any event, it wasn't that I specifically wanted to do recursion
early but rather, there were a number of things I wanted to do with
the class for which Scheme made sense and recursion was just one of
them.
</p>
<p>
Some reasons to like (or for some, to dislike) Scheme early:
</p>
<ul class="org-ul">
<li>It's functional – everything is a function. While this is
technically not true, we can fudge it a bit at this level. You put
things in parens so instead of add(a,b) you write (add a b) or
really (+ a b). You can also do (+ a b c). Things that would be
statements are also functions: (if Booelean TruePart FalsePart) is the <b>if</b>
statement. For example <code>(if (>= a b) a b)</code> returns the larger of a
and b.</li>
<li>Because it's functional it avoids the issue kids have with <code>=</code> being
for assignment rather than comparison.</li>
<li>It has great support for list processing.</li>
<li>Recursion is much more natural.</li>
<li>It's a super simple language with simple rules and a simple, small syntax</li>
</ul>
<p>
Of course, Scheme isn't perfect and some people dislike the above
reasons. It's also easy to come up with a number of other good reasons
not to use a language like Scheme.
</p>
<p>
On the recursion front, it makes things much easier. There are no
loops so recursion develops as a natural form for repetition:
</p>
<div class="highlight"><pre><span></span><span class="p">(</span><span class="k">define </span><span class="nv">f</span> <span class="p">(</span><span class="k">lambda </span><span class="p">(</span><span class="nf">x</span><span class="p">)</span>
<span class="p">(</span><span class="nb">* </span><span class="nv">x</span> <span class="p">(</span><span class="nf">f</span> <span class="p">(</span><span class="nb">- </span><span class="nv">x</span> <span class="mi">1</span><span class="p">)))))</span>
</pre></div>
<p>
This defines a function that takes one parameter and returns
<code>x*(x-1)*(x-2)...</code>. It repeats, but never ends. This leads to adding
a base case:
</p>
<div class="highlight"><pre><span></span><span class="p">(</span><span class="k">define </span><span class="nv">f</span> <span class="p">(</span><span class="k">lambda </span><span class="p">(</span><span class="nf">x</span><span class="p">)</span>
<span class="p">(</span><span class="k">if </span><span class="p">(</span><span class="nb">< </span><span class="nv">x</span> <span class="mi">2</span><span class="p">)</span>
<span class="mi">1</span>
<span class="p">(</span><span class="nb">* </span><span class="nv">x</span> <span class="p">(</span><span class="nf">f</span> <span class="p">(</span><span class="nb">- </span><span class="nv">x</span> <span class="mi">1</span><span class="p">))))))</span>
</pre></div>
<p>
Which is your basic factorial function.
</p>
<p>
Since this use of recursion for repetition develops naturally as we
introduce language concepts it's easier for kids to get their heads
around it as opposed to when they've seen loops already and have an
"easier" alternative. You can make the case that you could introduce
recursion this way in a language with loops like Python but once loops
are available and particularly when loops are idiomatic, students will
find them and getting them to think recursively will be more
difficult.
</p>
<p>
Scheme and most other functional programming languages also have
strong support for lists and list recursion. This means you don't have
to limit yourself to mathy problems. Think about a todo list:
</p>
<ol class="org-ol">
<li>Go to the market</li>
<li>Buy a gallon of milk</li>
<li>If they have eggs, get a dozen (heh heh)</li>
<li>Go home</li>
</ol>
<p>
Processing a todo list is really a recursive problem:
</p>
<ol class="org-ol">
<li>If the list is empty you're done</li>
<li>Take the first item off the list</li>
<li>Do it</li>
<li>Recurse</li>
</ol>
<p>
Once you start working with lists, you can play with all sorts of
recursive examples.
</p>
<p>
At the end of the Scheme unit the big project is creating a sentence
generator. The kids don't know it but they're learning about grammars
and in fact are writing a recursive descent parser - they just think
they're writing a program that creates silly sentences. It's a really
nice project that uses recursion in a way that's different and I'd
argue more fun and interesting than the usual approaches.
</p>
<p>
I chose Scheme for a variety of reasons. I also chose NetLogo for
specific reasons. Unlike Scheme (or most other popular learning
languages), NetLogo is really all about agent based parallel
processing. There are concepts that we can explore easily and in depth
with NetLogo that would be tremendously difficult in any other
language and at the same time, there are things that are easy to
explore in other languages that Netlogo doesn't lend itself to.
</p>
<p>
So, in the end, this post really isn't about when to teach
recursion. It's more about how languages lend themselves to solving
different problems and teaching different concepts in different
ways. If all you have is a hammer, everything looks like a
nail. Fortunately, we can do better.
</p>
</div>
</div>Do It The Dumb Wayhttp://cestlaz.github.io/posts/do-it-the-dumb-way/2018-03-30T08:24:09-04:002018-03-30T08:24:09-04:00Mike Zamansky<div id="outline-container-org7f03035" class="outline-2">
<h2 id="org7f03035"></h2>
<div class="outline-text-2" id="text-org7f03035">
<p>
There's so much to like in the shape drawing lessons I talked about
in my <a href="http://cestlaz.github.io/posts/refactoring/">refactoring</a> post that I thought I'd share a little more here.
</p>
<p>
It can be argued that the most important things for a program to do is work. The
most clever, elegant, creative program is worthless if it doesn't
produce the desired result. All too often, beginners and hot shot beginners in particular try to
be too clever too early and get themselves into trouble.
</p>
<p>
When doing the shape drawing lessons the first couple of shape are
pretty easy
</p>
<pre class="example">
| **** | | * |
| **** | | ** |
| **** | | *** |
| **** | | **** |
| **** | | |
| | | |
</pre>
<p>
but things get more interesting with the right justified triangle:
</p>
<pre class="example">
----* *
---** **
--*** ***
-**** ****
***** *****
</pre>
<p>
For this triangle, students want to come up with the formula for the
number of spaces. They usually figure out something like this with
<code>h-i-1</code> spaces and <code>i+1</code> stars:
</p>
<div class="highlight"><pre><span></span><span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">tri2</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="n">line</span><span class="p">(</span><span class="n">h</span><span class="o">-</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="s">"-"</span><span class="p">)</span> <span class="o">+</span> <span class="n">line</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="s">"*"</span><span class="p">)</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>
The formulas become harder to figure out as the shapes become more
complex and sometimes students get stymied.
</p>
<p>
The truth is that while they're struggling to find the perfect
solution, it's sometimes better to do it the dumb way.
</p>
<p>
Consider drawing a trapezoid like this example of height 5 and
starting width 12:
</p>
<pre class="example">
************
**********
********
******
****
</pre>
<p>
A student could come up with the "formulas" for spaces and stars but
sometimes there's a more straightforward way.
</p>
<p>
Consider the number of spaces on each line on the left hand side of
the shape. First line is 0 then 1, 2 etc. Why not start a variable
<code>spaces</code> at 0 and increment it on each loop iteration.
</p>
<p>
For the number of stars, it's starting at the width and being reduced
by 2 each time.
</p>
<p>
This leads to a solution similar to this (using the line routine from
the earlier refactoring post):
</p>
<div class="highlight"><pre><span></span><span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">trap</span><span class="p">(</span><span class="kt">int</span> <span class="n">height</span><span class="p">,</span> <span class="kt">int</span> <span class="n">width</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">spaces</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">stars</span> <span class="o">=</span> <span class="n">width</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span> <span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">height</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="n">line</span><span class="p">(</span><span class="n">spaces</span><span class="p">,</span><span class="s">" "</span><span class="p">)</span> <span class="o">+</span> <span class="n">lines</span><span class="p">(</span><span class="n">stars</span><span class="p">,</span><span class="s">"*"</span><span class="p">)</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="n">spaces</span> <span class="o">=</span> <span class="n">spaces</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="n">stars</span> <span class="o">=</span> <span class="n">stars</span> <span class="o">-</span> <span class="mi">2</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>
This solution is simple to construct, simple to understand, and quite
frankly, hard to get wrong.
</p>
<p>
It can also lead a student to discovering a pattern or "formula" such
as what was used to solve the earlier problems.
</p>
<p>
This might seem to some as a cheap way out, the dumb approach -
creating extra variables and have them count along the way but I
don't. There's nothing wrong with simple and straightforward. Yes, you
could come up with an elegant formula but the bottom line is you need
something to count 0,1,2,3… so create a variable to do it. You need
something to count 12,10,8,… create one for that as well.
</p>
<p>
Now, I'm not advocating writing 100 if statements rather than a loop
but I think you get the idea.
</p>
<p>
The best solution is one that works and Sometimes the "dumb" approach is the best approach.
</p>
</div>
</div>Refactoringhttp://cestlaz.github.io/posts/refactoring/2018-03-21T08:11:38-04:002018-03-21T08:11:38-04:00Mike Zamansky<div id="outline-container-org15eecc3" class="outline-2">
<h2 id="org15eecc3"></h2>
<div class="outline-text-2" id="text-org15eecc3">
<p>
One of my laments on teaching computer science is that students are
rarely taught and given the chance to develop good programming
practices. There's usually not enough time. Beginners work on small
"toys" which don't lend themselves to good software development
practices and later on, there's so much other material like
algorithms, data structures etc. to teach and
learn that programming practices usually amount to lines like:
</p>
<blockquote>
<p>
"Make sure to comment your code.."
</p>
<p>
"Indent properly…"
</p>
<p>
"Use functions…"
</p>
<p>
"It's important to test your code…"
</p>
</blockquote>
<p>
so when I see an opportunity to use a simple example to drive home a
good practice, I try to jump on it.
</p>
<p>
Drawing shapes with text is a typical early project. I've seen it in
text books and online and have been doing it for years. I recall doing
it back in the 80s in Fortran IV when the programs we wrote were on <a href="https://en.wikipedia.org/wiki/Punched_card">punch cards</a>, run
overnight on an <a href="https://en.wikipedia.org/wiki/IBM_1130">IBM 1130</a>, and printouts picked up the next day.
</p>
<p>
It's a nice use of nested loops. The students will write functions to
create assorted shapes out of asterisks like rectangles and
triangles. Typical solutions look like this:
</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf"><iostream></span><span class="cp"></span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">box</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">w</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"*"</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">tri</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"*"</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>
Which results in shapes like these:
</p>
<pre class="example">
| **** | | * |
| **** | | ** |
| **** | | *** |
| **** | | **** |
| **** | | |
| | | |
| | | |
| *************** | | * |
| *************** | | ** |
| *************** | | *** |
| *************** | | **** |
| *************** | | ***** |
| *************** | | ****** |
| *************** | | ******* |
</pre>
<p>
Then there will be more interesting shapes including things like:
</p>
<pre class="example">
* * *****
** *** * * and more
*** ***** * *
**** *** *****
*
</pre>
<p>
This is a great time to talk about refactoring. All of the shape
drawing functions follow the same pattern - there's an outer loop for
the height and then one or more inner loops to draw each line. We can
factor out the inner loops in to a separate <code>line()</code> function.
</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf"><iostream></span><span class="cp"></span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">box</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">w</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="c1">//</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"*"</span><span class="p">;</span> <span class="c1">// <----- This can be factored out</span>
<span class="p">}</span> <span class="c1">//</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">tri</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="c1">//</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"*"</span><span class="p">;</span> <span class="c1">// <---------------- along with this</span>
<span class="p">}</span> <span class="c1">//</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>
It's just like factoring in algebra:
</p>
<div class="LATEX">
<p>
</p>
<p>
(RectangleOuterLoop × Line) + (TriangleOuterLoop × Line) ⇒ Line (Rectangleouterloop × TriangleOuterloop)
</p>
</div>
<p>
We end up with:
</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf"><iostream></span><span class="cp"></span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">line</span><span class="p">(</span><span class="kt">int</span> <span class="n">w</span><span class="p">,</span> <span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">c</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">w</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="n">c</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">box</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="n">line</span><span class="p">(</span><span class="n">w</span><span class="p">,</span><span class="s">"*"</span><span class="p">)</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">tri</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="n">line</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="s">"*"</span><span class="p">)</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>
It's simpler, cleaner, and also can lead us to thinking about the
"harder" shapes in an interesting way. Instead of looking at the right
justified triangle as a triangle, we can think of each level as two
lines - one of spaces (shown here as dashes) followed by a line of
stars:
</p>
<pre class="example">
----* *
---** **
--*** ***
-**** ****
***** *****
</pre>
<p>
Noticing that for a height of 5, the dashed lines count down in
length 4,3,2,1,0 and the star lines count up 1,2,3,4,5, we get:
</p>
<div class="highlight"><pre><span></span><span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">tri2</span><span class="p">(</span><span class="kt">int</span> <span class="n">h</span><span class="p">){</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="s">""</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">h</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">r</span> <span class="o">+</span> <span class="n">line</span><span class="p">(</span><span class="n">h</span><span class="o">-</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="s">"-"</span><span class="p">)</span> <span class="o">+</span> <span class="n">line</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="s">"*"</span><span class="p">)</span> <span class="o">+</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">r</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="n">main</span><span class="p">()</span>
<span class="p">{</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">r</span> <span class="o">=</span> <span class="n">tri2</span><span class="p">(</span><span class="mi">5</span><span class="p">);</span>
<span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="n">r</span> <span class="o"><<</span> <span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span>
<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>
Here we have typical early CS assignment that really lends itself to
talking about structuring programs and refactoring. Where else can we
inject good programming practices in ways that make sense early on?
</p>
</div>
</div>Sigcse2018 Bootstrapworld on Creativity in CS classeshttp://cestlaz.github.io/posts/sigcse2018-bootstrap/2018-03-02T09:27:33-04:002018-03-02T09:27:33-04:00Mike Zamansky<div id="outline-container-org70bfbd0" class="outline-2">
<h2 id="org70bfbd0"></h2>
<div class="outline-text-2" id="text-org70bfbd0">
<p>
I really didn't know what to expect at the <a href="https://dl.acm.org/citation.cfm?id=3159471">Creativity, Customization,
and Ownership: Game Design in Bootstrap: Algebra</a> session. I've been a
big fan of <a href="http://www.bootstrapworld.org/">Bootstrep</a> for years and looking at the authors, <a href="http://blog.acthompson.net/2017/10/cs-teacher-interview-emmanuel.html">Emmanuel
Schanzer</a>'s been a freind forever. I've never met <a href="https://twitter.com/ShriramKMurthi">Shriram Krishnamurthi</a>
in person but am looking forward to it. We've traded emails and blog
comments. I'd like to consider him a friend and I certainly respect
him and his work even though we frequently disagree around the
edges. The third author and presenter, Kathi Fisler was new to me.
</p>
<p>
The Bootstrap program is embedded in algebra classes. In it, students
use Racket (nee scheme) to reinforce math skills while building
computer science skills. The big student project is a graphical game.
</p>
<p>
When designing the project, students are asked to decide on and find
four resources:
</p>
<ol class="org-ol">
<li>The background image</li>
<li>The player image</li>
<li>The target image</li>
<li>The enemy image</li>
</ol>
<p>
Students are given a short amount of time to decide on and find these
four images. I think it was about ten minutes and that's it. That's
all the "creativity" in the assignment. After that, all the students
are essentially creating the same game with different skins.
</p>
<p>
This design makes sense. You can't have students going all over the
place. Constraining the assignment in this way allows teachers who
might now be strong in computer science to guide the kids through the
program to completion.
</p>
<p>
At the time I was thinking: I really like all of this but is it really
open ended creativity and discovery with respect to math or computer
science? As it turned out, Fisler addressed this point at the end of
the talk in a way that made me vary happy.
</p>
<p>
Fisler went on to describe the rest of the student experience and then
went on to talk about the statistics they gathered.
</p>
<p>
One big takeaway was that while all the students were essentially
writing the same game varying only the graphical elements, this
encouraged students to create very different themes. They also created
rich stories around their games. The project might not have been
"creative" with respect to the CS or Math directions but it was certainly
creative in other important areas. The other takeaway was that
survey's indicated all sorts of positives from the program as a whole
so the project didn't seem to have suffered by having the students
essentially write the same program. Participants were proud of their
work, they felt their games were different from their peers and in
general the experience was good.
</p>
<p>
During questions, someone asked about adding a fifth element - a
projectile or missile. It turns out that at one point the program had a
projectile component but that led to the vast majority of projects to
be themed in very similar ways. Even though not the same, it reminded me to something Randy
Pausch said in his <a href="https://www.youtube.com/watch?v=ji5_MqicxSo">Last Lecture</a>:
</p>
<blockquote>
<p>
You make whatever you want. Two rules: no shooting violence and no
pornography. Not because I’m opposed to those in particular, but you know, that’s been done with
VR, right? [laughter] And you’d be amazed how many 19-year-old boys are completely out of ideas
when you take those off the table.
</p>
</blockquote>
<p>
At the very end, Fisler addressed my questions about creativity and
discovery. She posed these questions of her own: "Do we overstate the
case for creativity?" and "Is pure constructivism a win?"
</p>
<p>
I've ranted on contructivism before. It can be great but a
constructivist lesson takes a knowledgeable educator and a lot of time,
preparation, and effort. It's a big ask for, say, a high school
teacher who's already taking home hours of work every evening. Too
often I've seen the following "contructivist" model instead:
</p>
<ul class="org-ul">
<li>Take an isntructor that doesn't know their craft, the content, or
niether.</li>
<li>Let the kids play with stuff.</li>
<li>Show off the couple of autodidacts that figure it out as success
stories.</li>
</ul>
<p>
I'll rant more about this "model" with respect to the new buzz word
"lead learner" at some point in the future.
</p>
<p>
On the creativity side, it's important but there are also times for
the instructor to lead and for guidelines to be followed.
We want to foster creativity but that doesn't mean that it's 100%
creativity 100% of the time. Education is like life, a balance. The
Bootstrap program had to constrain the CS and math learning but
allowed for creativity in other areas. It's smart and it's a win.
</p>
<p>
I still want to meet Shriram in person one day and now also Kathi
Fisler. I didn't know what to expect walking in but I left the talk
reminded of why I'm such a fan of Emmanuel, his team, and their work.
</p>
</div>
</div>Sigcse2018 - Malloc Labhttp://cestlaz.github.io/posts/sigcse2018-Malloc-Lab/2018-03-01T16:59:31-04:002018-03-01T16:59:31-04:00Mike Zamansky<div id="outline-container-orgcc9558f" class="outline-2">
<h2 id="orgcc9558f"></h2>
<div class="outline-text-2" id="text-orgcc9558f">
<p>
I wasn't going to go to this session. I started out in a panel on
integrating social good into CS Ed. With the panel not meeting my
expectations I moved over to my second choice - the system programming
sessions where I saw <a href="https://dl.acm.org/citation.cfm?id=3159597">Implementing Malloc: Students and Systems
Programming</a>, a paper presented by <a href="http://www.cs.cmu.edu/~bpr/">Brian Railing</a> of CMU.
</p>
<p>
I really liked both the paper and the talk.
</p>
<p>
CMU computer science students all take a systems course that uses
<a href="https://www.amazon.com/Computer-Systems-Programmers-Perspective-3/dp/9332573905/ref=pd_lpo_sbs_14_t_0?_encoding=UTF8&psc=1&refRID=Y5ZKG2V8ZYZZPZHQP8SQ">Computer Systems: A Programmer's Perspective</a>. It's a great book. I
read through the first edition years ago and felt it was great
resource not only in a systems course but also for self study. One of
the labs has the students implement their own memory allocation calls,
or <b>malloc</b> for us old time C wonks.
</p>
<p>
There were a number of self perceived deficiencies with the
assignment such as encouraging bad programming style by modeling
less than ideal practices but the biggest deficiency as that students
could game the assignment. Students could do very well on the
assignment by exploiting knowledge of the assignment rather than by
writing a full and correct malloc implementation. One example is that
students were able to figure out that no allocation would be more than
100MB so they really didn't have to deal with 64 bit pointers. They
could use smaller offsets thus simplifying the assignment. The
assignment became more about figuring out how to get it through the
grader and less about learning memory management. I'm sure I'm
overstating it but that's the idea.
</p>
<p>
Railing explained all of the deficiencies and then how they changed
the assignment to address them.
</p>
<p>
At the end of the day, the assignment had fewer loopholes to game so
students had to really write the malloc library and presumably learn
about memory management.
</p>
<p>
They also added an intermediate deliverable so students couldn't leave
everything for the last minute.
</p>
<p>
Near the end of the talk, Railing discussed results where he pointed
out that students final exam scores didn't change but they did better
on the malloc questions. It wasn't clear if the overall scores didn't
change, meaning that the students did better on the malloc questions
but worse somewhere else or if they did similarly to past students on
the other sections and in addition they scored better on the malloc
questions. I'm not sold on the final exam questions being the best way
to evaluate learning but it is an easy data point.
</p>
<p>
I loved the presentation and paper and I love what Railing is doing
but my big takeaway was…
</p>
<p>
Well, Duh…
</p>
<ul class="org-ul">
<li>students aren't doing as they should</li>
<li>teacher realizes students are gaming assignment</li>
<li>teacher reworks assignment</li>
<li>students do better</li>
</ul>
<p>
Teachers do this all the time. Of course when we do it, it's not
"research." This was a recurring theme for me at SIGCSE2018 and I
tweeted it. While it's true that K12 teachers can learn a lot about CS
content from higher ed, people in higher ed can learn a lot about
teaching from teachers.
</p>
<p>
What Railing presented was terrific and important as changing
assignments like this will now be considered by people who haven't
thought about this before but this is second nature to a teacher. Of
course I'm talking about a good teacher, not one who blindly follows
scripted lessons.
</p>
<p>
I don't mean this as a slight to professors. They're hired and
promoted based on research so much of their job involves another skill
set. I know many professors who care very much about teaching but they
might only teach one or two classes a semester that meets once or
twice a week while a typical high school teacher meets 150 students a
day five days a week over five different classes a day. Much more of
an opportunity for deliberate practice.
</p>
<p>
This presents a huge challenge. How can professors who are hired and
promoted as researchers be given the time and ability to develop as
teachers? What about adjuncts or Teaching Assistants? I'd imagine it's
even harder for them. I know that colleges have lines for teaching
faculty but from what I can see, those instructors are usually super
overloaded with classes and students so that doesn't solve the
problem. Even if you do have teaching faculty that have the time to
develop their craft, how do you get those teaching chops over to the
research faculty?
</p>
<p>
After the session, I was talking about this with <a href="http://www.cs.cmu.edu/~mjs/">Mark Stehlik</a>,
Assistant Dean at CMU's School of Computer Science. Mark was telling
me about CMU's efforts to develop teaching faculty across the
disciplines. I was happy to hear about the efforts CMU was taking but
it sounds like they have the same challenges with respect to pedagogy
as everyone else. If it's a challenge for CMU with all their
resources, what does that mean for the rest of us?
</p>
<p>
Still, it was encouraging to go to a number of sessions where it was
clear that professors - both teaching and research faculty are serious
about the craft of teaching and conferences like SIGCSE can bring them
together with those of us who don't have the chops as researchers but
do so as teachers.
</p>
</div>
</div>Tools can shape how we thinkhttp://cestlaz.github.io/posts/advent-2016-6-4/2017-12-06T16:01:15-04:002017-12-06T16:01:15-04:00Mike Zamansky<div id="outline-container-orgc46ef18" class="outline-2">
<h2 id="orgc46ef18"></h2>
<div class="outline-text-2" id="text-orgc46ef18">
<p>
I've been having fun with this years <a href="http://adventofcode.com">Advent of Code</a> competition. So
far, I've been able to keep up but with I expect that to change in
another couple of days since I'll be traveling for the weekend.
</p>
<p>
After solving a problem, I like looking over some of the other
solutions on the Advent of Code <a href="https://www.reddit.com/r/adventofcode/">subreddit</a>. Even with similar
agorithmic solutions there's a decent amount of variation in the
actual code and solutions in different languages can look radically
different.
</p>
<p>
That got me thinking about how the tools we know and use both shape the ways we
approach solving problems and creating things and either limit or
empower us to go from a mental model of a solution or creation to an
actual artifact.
</p>
<p>
Relating to this are the common themes that come up in the CS
Education world. The idea that it's computer science not programming
and certainly not merely coding. That's true but the tools and
languages we use shape the whole thinking part and can also give the
students a valuable practical tool that they can leverage to great
advantage in both future classes and work and life endeavors.
</p>
<p>
I decided to do this rant as a video. I hope you enjoy it:
</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/x8cZgEogWNw" frameborder="0" gesture="media" allow="encrypted-media" allowfullscreen></iframe>
</div>
</div>A new first language? What's the follow up plan?http://cestlaz.github.io/posts/first-language-changing/2017-04-21T14:46:07-04:002017-04-21T14:46:07-04:00Mike Zamansky<div id="outline-container-org8cde2cc" class="outline-2">
<h2 id="org8cde2cc"></h2>
<div class="outline-text-2" id="text-org8cde2cc">
<p>
This morning, <a href="https://twitter.com/guzdial">Mark Guzdial</a> wrote about Stanford possibly <a href="https://computinged.wordpress.com/2017/04/21/cs-department-updates-introductory-courses-java-is-gone/">moving away
from Java</a> as their intro language. This comes on the heels of a
semi-regular thread on one of the lists I'm on asking about what
languages are used at assorted colleges around the country. Invariably
the Pascal -> C++ -> Java progression of APCS turns up in these
threads.
</p>
<p>
There are plenty of arguments to be made both for and against pretty
much any language or platform. There's no single best universal
answer. Each choice giveth and each choice taketh away.
</p>
<p>
What I'm really curious about is who's looking at intro languages in
the context of complete programs or even complete educations that
could span multiple institutions.
</p>
<p>
Early language choices can make a big difference in engaging and
exciting newcomers but there are ramifications later on that few seem
to consider.
</p>
<p>
Take the APCS change from C++ to Java. It removed memory management
from the first year course. It also simplified issues relating to
pass by value vs pass by reference (or, rather, passing address by
value), bought much more strongly into OOP and moved more towards
using built in implementations of data structures like Lists rather
than rolling your own.
</p>
<p>
Removing memory management from the first year course in and of itself
isn't a problem as long as it's taught and taught effectively
somewhere later on. It could be argued that "memory is already covered
in our required systems course." That could be the case, but there are
many concepts that kids don't get the first time around. Is an
institution that covered memory management in CS1/2 and then came back
to it in a later Systems course giving their students the same
understanding now that they've eliminated the CS1/2 experience?
</p>
<p>
What about OOP buy in. Personally, I've never been a big OOP fan but
that's neither here nor there. What I have found is that depending on
how a student is exposed to programming in CS1/CS2 can have a big
influence on how they approach problems later. Did the move to Java
cause more of our students to try to use shoehorn OOP into a problem
that really shouldn't be approached in an OOP manner?
</p>
<p>
I suspect that the use of built in data structures has had a
negative impact. A few years after the switch to Java, I was talking
to a senior tech worker. He was having a bad day - interviewing
potential internees and full time engineers. My friend was complaining
that the kids couldn't come up with solutions to what he thought were
pretty straightforward questions. He felt that had the kids actually
implemented algorithms like the nlogn sorts rather than just learning
java .sort method and just talking about the algorithm they'd be
better prepared. I've heard this sentiment repeated over and over
throughout the years.
</p>
<p>
This is not to say that Java is a horrible language or horrible for
teaching - that's another debate. The point is that you can't just
look at the intro class and who it draws in. You have to consider how
it will prepare students for the next level and you have to look at
the big picture – will our students get everything they need by the
time they leave us.
</p>
<p>
Many schools have moved to Python. Will that effect students take on
type systems later on? Will the flexibility and constructs like list
comprehensions make it harder to teach recursion since there are
"easier" ways to do it?
</p>
<p>
None of these are really problems so long as the CS1/2 (or even CS0)
isn't taught in a vacuum.
</p>
<p>
I fear, however that too often we're paying attention to the intake of
the pipe and not so much the output.
</p>
</div>
</div>GitHub as a tool for educationhttp://cestlaz.github.io/posts/sigcse-2017-github-4/2017-04-11T19:11:30-04:002017-04-11T19:11:30-04:00Mike Zamansky<p>
When I started using git and GitHub with my students it was a natural
progression having started with started with CVS and then, as
technology changed moving through Subversion and then Mercurial. It
was all about using sensible professional software development
techniques while making it easier for students to submit work and for
me to evaluate their submissions.
</p>
<p>
Over time, I found that git and GitHub in fact provided some extra
support for educators right out of the box.
</p>
<p>
In my <a href="http://cestlaz.github.io/posts/sigcse-2017-github-3">last github post</a> I talked about using the results of <code>git log</code>
and looking at diffs. Both provide ways of seeing what a student did
and when. The commit log and history make it easier to hold students accountable to working
through a project and not leavings for the last minute. The diffs make
it easier to see what's changed both to see progress and also to help
support students as they develop their projects.
</p>
<p>
If you use Emacs, as I do, you can use the <a href="https://github.com/pidu/git-timemachine">git timemachine</a> package
which does a great job visualizing changes:
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/sigcse-github/timemachine.gif" alt="timemachine.gif" align="center">
</p>
</div>
<p>
Other editors might have a similar feature.
</p>
<p>
The contribution graphs also provide a quick snapshot which shows what
team members are contributing and when:
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/sigcse-github/githubgraph.png" alt="githubgraph.png" align="center">
</p>
</div>
<p>
The punchcard graph is also useful to see when students actually do
their work.
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/sigcse-github/githubgraph2.png" alt="githubgraph2.png" align="center">
</p>
</div>
<p>
GitHub also make it easy to set up starter code or to have students
"take over" each others projects by forking.
</p>
<p>
I'm very happy using git and GitHub as is but if you want more
support, check out <a href="https://classroom.github.com/">GitHub Classroom</a>. Had it existed when I started,
I'd probably have used it but since I had already gotten used to my
work flows I've stuck with raw git and github.
</p>
<p>
In case you missed the earlier posts describing the process I use to
introduce github to my classes here they are:
</p>
<ul class="org-ul">
<li><a href="http://cestlaz.github.io/posts/sigcse-2017-github-1">Part 1</a></li>
<li><a href="http://cestlaz.github.io/posts/sigcse-2017-github-2">Part 2</a></li>
<li><a href="http://cestlaz.github.io/posts/sigcse-2017-github-3">Part 3</a></li>
</ul>
<p>
I'm hoping some of you have found this set of four posts useful or at
least interesting.
</p>A free multi-state clicker with built in redundencyhttp://cestlaz.github.io/posts/thumb_clickers/2017-04-01T17:23:21-04:002017-04-01T17:23:21-04:00Mike Zamansky<div id="outline-container-orgbf38cb1" class="outline-2">
<h2 id="orgbf38cb1"></h2>
<div class="outline-text-2" id="text-orgbf38cb1">
<p>
Last Friday, <a href="https://twitter.com/guzdial">Mark Guzdial</a> wrote about the woes of <a href="https://computinged.wordpress.com/2017/03/31/the-need-for-better-software-and-systems-to-support-active-cs-learning/%0A">using clickers</a> in a
class. The amount of effort required to use his school's approved
clicker technology sounds ridiculous so while we need tools to better
engage students in large class settings we need better tools that can
be integrated into our classes more easily.
</p>
<p>
I've never used clickers. On top of stories like Mark's, there are a
number of problems with using clickers in a public school.
</p>
<p>
You can't force students to buy them and in NYC, until recently,
students couldn't use their phones (which they also might not have).
Forgetting the expense, if the school provides them, is it one per
student? If so, who's going to administer the clicker to student
mapping and how will that be communicated to the teachers. If college
tech infrastructures are sometimes lacking, high schools are orders of
magnitudes worse. The resources just aren't there. Then we have to
deal with loss and breakage.
</p>
<p>
If a teacher somehow gets a class set of clickers, they have to deal
with mapping clickers to students for all of their classes and make
sure the right student has the right clicker. Again, loss and
breakage is a problem.
</p>
<p>
Then you have to create the question content and hope that everything
works in class.
</p>
<p>
The value added given the overhead just doesn't seem worth it
particularly since high school classes, while large, are not in the
hundreds and there are other methods of student engagement.
</p>
<p>
Here's what I use instead. It's not perfect but it's low cost and low
effort with a pretty high return.
</p>
<p>
The basic configuration, is a simple three state broadcast device.
</p>
<p>
It's not without its problems and I don't think it would work as well
in a large lecture but given the cost, it's well worth it.
</p>
<p>
So, what is it?
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/thumbs/fonzup.jpg" alt="fonzup.jpg" align="center">
</p>
</div>
<p>
Thumbs.
</p>
</div>
</div>
<div id="outline-container-org038e1e6" class="outline-2">
<h2 id="org038e1e6"></h2>
<div class="outline-text-2" id="text-org038e1e6">
<p>
Periodically, I'll poll my class.
</p>
<span>
<img width="30%" src="http://cestlaz.github.io/img/thumbs/sidethumb.png">
<img width="30%" src="http://cestlaz.github.io/img/thumbs/upthumb.jpg">
<img width="30%" src="http://cestlaz.github.io/img/thumbs/downthumb.jpg">
<p>
Thumb to the side? Everything's OK. Keep going as you're going. I get
it. Basically, things are good.
</p>
<p>
Thumb up? Speed up, you're going too slow, I got it five minutes ago or
some similar big positive.
</p>
<p>
Thumb down? I have no idea what you're talking about.
</p>
<p>
It's cheap, easy, quick, and once you can get your class to buy in,
you can get a quick sense of the class.
</p>
<p>
The downsides?
</p>
<ul class="org-ul">
<li>The class has to have a level of comfort so that students vote
honestly and don't just give you positive feedback.</li>
<li>No data collection.</li>
</ul>
<p>
The upsides?
</p>
<ul class="org-ul">
<li>quick</li>
<li>cheap</li>
<li>works on any topic on the fly</li>
<li>even if the votes are artificially skewed towards positive, it does
forces the class to be at least a little attentive and to engage in
some physical response</li>
<li>can get analog responses by allowing students to adjust wrist
rotation</li>
</ul>
<p>
As to the redundancy? I've never had a kid leave their thumb at home
or lose it and even if they did, they've got a second hand.
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/thumbs/fonztwo.jpg" alt="fonztwo.jpg" align="center" height="200">
</p>
</div>
<p>
This also works in extreme environments. Try using a clicker or mobile
app with gloves or mittens on or underwater.
</p>
<p>
I don't teach large lectures so I don't know how this would work in a
huge class. I'd imagine it's still worth it given that it's so low
friction and low cost of entry even if it's not perfect.
</p>
</span></div>
</div>A Teacher looks at Advent of Code 2016 #2http://cestlaz.github.io/posts/advent-of-code-2016-2/2016-12-08T08:40:49-05:002016-12-08T08:40:49-05:00Mike Zamansky<p>
Today we're looking at <a href="http://adventofcode.com">Advent of Code</a> 2016 <a href="http://adventofcode.com/2016/day/2">number 2</a>.
</p>
<p>
To change things up, I thought I'd do a video where I live code a solution.
</p>
<p>
The solution I present is pretty straightforward - use a 2D array (or
technically, an array of strings) to represent the keypad, parse the
input, and follow the input instructions to build the code.
</p>
<p>
One of the things I really like about Advent of Code is that every
problem has two parts and depending on how you solved part 1, you may
or may not have extra work to do for part 2.
</p>
<p>
A couple of years ago, I wrote about one of the coding techniques I
try to convey to my students. The idea of <a href="http://cestlaz.github.io/posts/2014-02-26-change-the-data.md">changing the data</a> to take
away edge and special cases.
</p>
<p>
Part two of this problem is a perfect time to use that technique.
</p>
<p>
Here's the video, I hope you enjoy it:
</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/EC8gSrYQ11g" frameborder="0" allowfullscreen></iframe>A Teacher looks at Advent of Code 2016 #1http://cestlaz.github.io/posts/advent-code-2016-1/2016-12-06T10:46:17-05:002016-12-06T10:46:17-05:00Mike Zamansky<p>
I recently <a href="http://cestlaz.github.io/posts/advent-of-code-2016/">posted</a> about <a href="http://adventofcode.com">Advent of Code</a> - a series of programming
problems relseased one a day. While they vary in terms of level of
difficulty, a number of them make nice problems for introductory to
mid level programming classes.
</p>
<p>
I thought I'd share some of my thoughts on a few of them starting with
the first problem from this years competition.
</p>
<p>
<a href="http://adventofcode.com/2016/day/1">Take a minute to read it over.</a>
</p>
<p>
At first glance, it might seem to a young programmer that this problem
requires a two dimensional array - all about (x,y) coordinates but
then there's a problem - there are no limits on coordinates and we
can't make an unlimited size array.
</p>
<p>
After thinking a bit, hopefully the programmer realizes that all they
need to do is keep track of the how the <b><b>(x,y)</b></b> location changes over
time. In the solution below, we start at <b><b>(0,0)</b></b> and count the steps as
we update two variables <b><b>x</b></b> and <b><b>y</b></b>.
</p>
<p>
When we finish processing the moves, we have our current location in
<b><b>(x,y)</b></b> and we have the number of steps taken to get there.
</p>
<p>
The solution below hsa a couple of niceties that a beginning
programmer might not know or use (and I'm not arguing that what's written is
superior in any way, it's just what I ended up writing).
</p>
<p>
I make use of tuple destructuring:
</p>
<div class="highlight"><pre><span></span><span class="n">x</span><span class="p">,</span><span class="n">y</span> <span class="o">=</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span>
</pre></div>
<p>
which assigns <b><b>x</b></b> to the first item in the tuple and <b><b>y</b></b> the
second. I used that a number of times
</p>
<p>
I also use a list I call <b><b>dirs</b></b> to hold dx and dy values for the
four direcitons:
</p>
<div class="highlight"><pre><span></span><span class="n">dirs</span><span class="o">=</span><span class="p">[(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">),(</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">)]</span>
</pre></div>
<p>
This made it easier to to update the location based on the 4
directions. I could also have just used if statements.
</p>
<p>
Here's all the code:
</p>
<div class="highlight"><pre><span></span><span class="n">x</span><span class="p">,</span><span class="n">y</span> <span class="o">=</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span> <span class="c1"># assume our starting location is 0,0</span>
<span class="c1"># we start with d=0 -> facing north</span>
<span class="c1"># as we turn left or right, we can just increment or decrement d</span>
<span class="c1"># and dirs[d] will give us the appropriate dx and dy to update</span>
<span class="c1"># our locatoin for the next step</span>
<span class="n">dirs</span><span class="o">=</span><span class="p">[(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">),(</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">)]</span>
<span class="n">d</span><span class="o">=</span><span class="mi">0</span>
<span class="c1"># This is only needed for part 2 - We track visited locations</span>
<span class="c1"># by adding them to the dictionary. If we try to add a location</span>
<span class="c1"># that's already been visited we know that we've found our final </span>
<span class="c1"># location</span>
<span class="c1"># locs={} # uncomment this line for part 2</span>
<span class="n">totalsteps</span><span class="o">=</span><span class="mi">0</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">l</span><span class="p">:</span>
<span class="c1"># the first char in i is the direction to turn in (L or R)</span>
<span class="c1"># the rest represents the number of steps.</span>
<span class="nb">dir</span><span class="o">=</span><span class="n">i</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="n">steps</span><span class="o">=</span><span class="nb">int</span><span class="p">(</span><span class="n">i</span><span class="p">[</span><span class="mi">1</span><span class="p">:])</span>
<span class="k">if</span> <span class="nb">dir</span><span class="o">==</span><span class="s2">"L"</span><span class="p">:</span>
<span class="n">d</span> <span class="o">=</span> <span class="p">(</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">%</span><span class="mi">4</span>
<span class="k">else</span><span class="p">:</span>
<span class="n">d</span> <span class="o">=</span> <span class="p">(</span><span class="n">d</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">%</span><span class="mi">4</span>
<span class="p">(</span><span class="n">dx</span><span class="p">,</span><span class="n">dy</span><span class="p">)</span> <span class="o">=</span> <span class="n">dirs</span><span class="p">[</span><span class="n">d</span><span class="p">]</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">steps</span><span class="p">):</span>
<span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">)</span> <span class="o">=</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">dx</span><span class="p">,</span> <span class="n">y</span> <span class="o">+</span> <span class="n">dy</span><span class="p">)</span>
<span class="n">totalsteps</span><span class="o">=</span><span class="n">totalsteps</span><span class="o">+</span><span class="mi">1</span>
<span class="c1"># Uncomment this block for part 2</span>
<span class="c1"># each time we have a new location, see if it's already in</span>
<span class="c1"># locs, if it isn't, add it.</span>
<span class="c1"># if it is, we're visiting somewhere twice so we're done.</span>
<span class="c1">#if ((x,y) not in locs):</span>
<span class="c1"># locs[(x,y)]=1</span>
<span class="c1">#else:</span>
<span class="c1"># print((x,y))</span>
<span class="c1"># print(abs(x)+abs(y)) # the answer</span>
<span class="c1"># sys.exit(0)</span>
<span class="c1"># break</span>
<span class="k">print</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">)</span>
<span class="k">print</span><span class="p">(</span><span class="nb">abs</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="o">+</span><span class="nb">abs</span><span class="p">(</span><span class="n">y</span><span class="p">))</span> <span class="c1"># the answer</span>
</pre></div>
<p>
Overall, a nice little problem for beginning and intermediate
students.
</p>New Term, New Tool - repl.ithttp://cestlaz.github.io/posts/new-term-new-tool-replit/2016-09-02T09:26:02-04:002016-09-02T09:26:02-04:00Mike Zamansky<div id="outline-container-org044f1fc" class="outline-2">
<h2 id="org044f1fc"></h2>
<div class="outline-text-2" id="text-org044f1fc">
<p>
We're now a week in to my first class at Hunter. It's a little early
for me to really compare and contrast the high school to college
experience but I thought I'd share some thoughts on a tool that I've
recently started to play with.
</p>
<p>
My students were all supposed to be issued laptops at the beginning of
the semester. The plan was to have them learn Linux, the command line,
and a little DevOps along the way. I guess I shouldn't have been too
surprised to learn that the laptops weren't going to come in until
late September.
</p>
<p>
Scratch all that advance lesson planning. A brief scramble and I was
able to relocate the class into a computer lab but now we can't
customize the kids environments.
</p>
<p>
Time to look for an online solution.
</p>
<p>
We're starting the kids off in Python, a choice that I'll talk about
in some future post and normally my online go to for Python is
<a href="http://codesters.com">codesters.com</a>. I'm a big fan of the codesters team and product. This
time, though, I decided to try something else. Specifically <a href="http://repl.it">repl.it</a>. Partly because, as with
codesters, I like the people behind it. It's also pretty simple and it
supports a lot of different languages:
</p>
<blockquote>
<p>
APL, ES2015 ,Bloop, BrainF, C, CoffeeScript, C++, C++11, C#, Emoticon,
Forth, F#, Go, Java, JavaScript, LOLCODE, Lua, Nodejs, PHP, Python,
Python3, QBasic, Roy, Ruby, Rust, Scheme, Swift, Unlambda, and HTML, CSS, JS
</p>
</blockquote>
<p>
It's still a pretty new product so there are occasional hiccups but
I'm really liking things so far. Some of the things I like include:
</p>
<ul class="org-ul">
<li>a simple clean interface.</li>
<li>sharing and embedding code:</li>
</ul>
<script src="//repl.it/embed/DF3m/19.js"></script>
<ul class="org-ul">
<li>project mode which allows multi file projects</li>
<li>examples to get you started</li>
</ul>
<p>
But the thing I'm really liking are the teacher features they're
working on. The teacher interface isn't fancy. I like that. Things are
simple and clean and they let me get the job done.
</p>
<p>
I had two extra minutes in class yesterday and in that time, I was
able to:
</p>
<ol class="org-ol">
<li>Make a classroom</li>
<li>Invite all my students by email</li>
<li>Create 2 quick assignments.</li>
</ol>
<p>
The assignment page lets you give starter code as well as instructions
and it also lets you put in tests that are run when a student submits
their work for instant feedback.
</p>
<p>
I really like the tests feature on projects. So far, I've only played
with Python unit tests. Repl.it uses a really easy to follow
interface and has a sample test to guide you. There's also an option
for input/output matching which includes flexible matching and regular
expressions but I haven't played with it yet.
</p>
<p>
Overall, I'm liking this tool. When the kids get their laptops we'll
probably use it somewhat less as they start to learn to use their own
systems but I'm glad to have repl.it in my teaching arsenal.
</p>
</div>
</div>Lesson plans - scripts to springboardshttp://cestlaz.github.io/posts/lesson-plans/2016-06-23T19:31:11-04:002016-06-23T19:31:11-04:00Mike Zamansky<div id="outline-container-orgd5cb09a" class="outline-2">
<h2 id="orgd5cb09a"></h2>
<div class="outline-text-2" id="text-orgd5cb09a">
<p>
I spent last Saturday up at the Microsoft offices in Times Square
observing a <a href="https://www.tealsk12.org/">TEALS</a> training session. My fried <a href="https://twitter.com/nathanielgranor">Nathaniel Granor</a>, Teals
Regional Manager in the east has invited me a number of times and this
time I was able to make it.
</p>
<p>
If you don't know, TEALS is a program that takes volunteers in the
tech industry and places them in classrooms. Unlike other programs,
the TEALS volunteers work with the teachers while the kids learn some
CS. The idea is that the teacher will learn about CS from the
volunteer and the volunteer will learn something about teaching.
</p>
<p>
It's not the same as having a strong, knowledgeable CS teacher in the
classroom but until we get there, TEALS is doing great work giving
kids something that they need and otherwise wouldn't get.
</p>
<p>
At one point, Nathaniel started to talk to the volunteers about lesson
plans emphasizing the fact that TEALS would provide all the lesson materials and
the plans so these new to teaching tech volunteers wouldn't have to
make curricular decisions.
</p>
<p>
The lesson plan form was pretty traditional and pretty formulaic:
</p>
<ul class="org-ul">
<li>warm up</li>
<li>hook</li>
<li>instruction</li>
<li>practice</li>
<li>Assessment</li>
</ul>
<p>
Very similar to what I was shown back in the day during my two day
"teaching boot camp" that kicked off my career <sup><a id="fnr.1" class="footref" href="http://cestlaz.github.io/posts/lesson-plans/#fn.1">1</a></sup> and very
appropriate as an effective and efficient way to prepare these
volunteers for their first days.
</p>
<p>
This got me thinking about my lesson planning over the years.
</p>
<p>
When I started, I was teaching math but I wasn't really a math
guy - I was CS all the way. I had to remember the math from high
school, learn the new topics, and figure out how to teach it.
</p>
<p>
I had a very supportive department but they were busy with their own
classes and this was pre internet. Fortunately, the NYC DOE published
lesson plan books. They were basically bound volumes of xerox copies
of hand written and typed lesson plans provided by experienced
teachers.
</p>
<p>
I spent many hours copying them, studying them, and then later
tweaking them.
</p>
<p>
They were a life saver back then. How was the teaching? OK. Not
great. I got the material to the kids but I was nothing special. This
is where I started to form my bias against the scripted teaching
that's being pushed down today.
</p>
<p>
As I developed my chops, I started to design my own experiences for my
classes and things improved. By the time I was done teaching math -
maybe 4 years in, I was just scratching the surface of being a math
teacher.
</p>
<p>
One year in, I started teaching CS along with math at Seward
Park. When I was bumped to Stuy, I went back to math for a year and a
half and then it was all CS all the time.
</p>
<p>
For CS, we didn't have lesson plan books so I had to craft everything
from scratch. It was a lot of work but the results were much better.
</p>
<p>
At first, I would actually write out lesson plans a la math lesson
plans. A "do now," "instructional objectives," "applications,"
"Homework," etc. The only thing I never formally wrote out was a
"medial summary."
</p>
<p>
Over time, my lessons got better but my lesson plans looked worse and
worse.
</p>
<p>
There were times a lesson plan might look something like this:
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/lesson-plans/plan.jpg" alt="plan.jpg" align="center">
</p>
</div>
<p>
OK, not exactly but as I developed at my craft, I didn't need a laid
out script to follow line for line rather, just a set of little
reminders and maybe some printed out code. If we were going to develop
a complicated algorithm or derivation, though, I would still write out
all the steps.
</p>
<p>
This doesn't mean that as my career progressed I planned any less. It
might appear that I'm winging it but even if little to nothing is
written down, there is a plan and there's always a lot of pre work
before class begins.
</p>
<p>
Now, to bring this back to TEALS.
</p>
<p>
It's interesting how what's good in one context is not so much in
another.
</p>
<p>
What TEALS is doing is great - they've got to get a lot of
technologists in to classrooms quickly but once there, they'll be with
real, hopefully experienced teachers. What they're doing gets them
ready to go. It's a starting point, not an end.
</p>
<p>
On the other hand, when I see scripted curriculum being sold as the
special sauce, be it in CS teacher "training," Teach for America
summer prep or in the name of charter school uniformity, I run the
other way.
</p>
<p>
Let's prepare curricular materials for important programs like TEALS
and for beginning teachers just starting out but let's not confuse a
scripted lesson that can be delivered by one and all to be anything
close to the work of a master educator and craftsman.
</p>
</div>
</div>
<div id="footnotes">
<h2 class="footnotes">Footnotes: </h2>
<div id="text-footnotes">
<div class="footdef"><sup><a id="fn.1" class="footnum" href="http://cestlaz.github.io/posts/lesson-plans/#fnr.1">1</a></sup> <div class="footpara">full disclosure: I
came in to teaching with zero education credentials and took the
minimum number of ed classes for my license after I started.</div></div>
</div>
</div>Robots platforms and practicalitieshttp://cestlaz.github.io/posts/robot-survey/2016-06-15T09:08:28-04:002016-06-15T09:08:28-04:00Mike Zamansky<p>
I received an email from a friend the other day asking me about a
particular robotics platform she recently saw.
</p>
<p>
I've played with robotics on and off over the years ranging from
building them from (not using) scratch using Atmel chips and programming them in
assembly to using Arduino based platforms to using pre-built robot
platforms. They're really cool and since they interact with the real
world you can do all sorts of interesting and motivational things with students.
</p>
<p>
I've done these on my own as a hobbyist and also with students either
individually or in small groups, but never as part of a class I had
been teaching.
</p>
<p>
Why not?
</p>
<p>
The biggest reason is that the classes I've taught are already so
packed full of CS goodness that we can't even get everything done
that's theoretically on the syllabi.
</p>
<p>
The other has to do with practical concerns.
</p>
<p>
Equipment costs - Let's say we can get our platform at $100 a pop. I
just can't see a public school with 34 kids in a class getting one per
student or one for every two.
</p>
<p>
So, what's the robot to student ratio and how much actual access do
the kids get? If they're designing building, do they all get to
design and build? Same question with coding and operating.
</p>
<p>
Then there's space – if we're talking about a mobile platform as
opposed to something that sits on the desk and is near stationary, we
have a problem. The classrooms I've taught in can barely hold the
students.
</p>
<p>
There are also issues with breakage, loss, theft and long term
maintainability - will we be able to or even want to fill in with
compatible units in a few years as needed or will we have to reboot
the program from scratch.
</p>
<p>
All that to deal with before we even get to the fun of teaching and learning.
</p>
<p>
I'm really curious about the experiences of those of you who do teach
using robots and similar platforms.
</p>
<p>
If you are such a teacher, could you please fill out this form or
leave a comment for anything that the form doesn't cover?
</p>
<iframe src="https://docs.google.com/forms/d/1FlppDbeiK8uPxh_RkXoCbbdE_UDY_4qXmZWbXlZ0gGg/viewform?embedded=true" width="760" height="500" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>Navajo Math Circleshttp://cestlaz.github.io/posts/navajo-circles/2016-06-08T07:03:55-04:002016-06-08T07:03:55-04:00Mike Zamansky<p>
Yesterday, I saw the New York Premiere of <a href="http://www.zalafilms.com/navajo/">Navajo Math Circles</a>, a
documentary on a <a href="http://www.mathcircles.org/">Math Circle</a> put in place to support and enrich the
currently under-served community in the Navajo educational system.
</p>
<p>
At their core, Math Circles are math outreach and enrichment
programs. I'm most familiar with the <a href="https://www.nymathcircle.org/">New York Math Circle</a>. I'm friends
with many of their teachers and organizers and my son took part in
their summer program for a couple of years.
</p>
<p>
Over in the southwest, these Math Circles have been bringing together
students, frequently across great distances each day to explore
problem solving and creativity through mathematics.
</p>
<p>
As someone who's worked hard to bring educational opportunities to the
have nots, I love the program. Some of the highlights include the kids
working on open ended problems, focusing on process and techniques
more than specific results, working both collaboratively but also
developing self sufficiency, and more. I also love the fact that
they've started teacher math circles to help to bring some of that
math circle magic to the everyday classroom.
</p>
<p>
I enjoyed the film and recommend you check it out to see what's
possible and I want to share my two big takeaways.
</p>
<p>
First, early on in the film, one of the people running the program
talked about developing a math enrichment program through and with
Navajo traditions and culture. This is HUGE and I feel it's something
we're losing. America is so diverse from coast to coast and here in
New York City you can see radically different ways of life living
right across the street from each other. Everyone pays lip service to
"making the work interesting and relevant to the student" but few
people walk the walk. These folk do.
</p>
<p>
Second, I left the documentary with a sour taste in my mouth. Not
because of the program but because the Navajo Math Circle project and
projects like it are scraping together what little resources they can
to try to do what the school systems should be doing to begin with.
</p>
<p>
As we move to scripted lessons, national standards, curricula dictated
or at least influenced by large private concerns and standardized
tests, our schools are moving further and further away from community
and local culture.
</p>
<p>
In the documentary, one student pointed out that in math class, they
have to use the textbook. They learn the process and then have to
solve the problems. In Math Circle, there are no textbooks.
</p>
<p>
Afterwards, the students in from the Math Circle did some Q&A. I asked
them to elaborate - what's the difference between there Math Circle
experiences and their in school ones. I got:
</p>
<blockquote>
<p>
Math Circle is fun!!!!
</p>
</blockquote>
<p>
I think that says it all.
</p>
<p>
I know many great teachers who try to bring culture and community to
their classes. One of my son's best teachers, <a href="http://www.heinemann.com/authors/828.aspx">Paula Rogovin</a> did it all
the time. Many of my friends and colleagues try to do so as well but
the powers that be make it harder and harder.
</p>
<p>
Until we win back public education it's important to support programs
like Math Circles (and, if I do say so myself, programs like our own
<a href="http://cstuy.org">CSTUY</a>) and it's also critical that we work to try to bring community
and culture to our regular classes.
</p>As curricula changes, what's falling through the cracks?http://cestlaz.github.io/posts/semaphores/2016-05-01T09:08:36-04:002016-05-01T09:08:36-04:00Mike Zamansky<div id="outline-container-org90751c0" class="outline-2">
<h2 id="org90751c0">Edit:</h2>
<div class="outline-text-2" id="text-org90751c0">
<p>
Just a brief note to clarify a couple of things. As indicated in the
comments, this post isn't about what's appropriate for HS CS. It's
more about what kids have after they finish their education - be it
high school, college, code school, or other.
</p>
<p>
Some of my thoughts are the results of pondering on the exacerbations
of friends after interviewing people for entry level positions.
</p>
<p>
The two examples are just to illustrate the point.
</p>
</div>
</div>
<div id="outline-container-org5c7e447" class="outline-2">
<h2 id="org5c7e447">Original Post:</h2>
<div class="outline-text-2" id="text-org5c7e447">
<p>
I enjoy reading blogs. It's one of the ways I keep current. Not only
in terms of what's going on in CS Education, but also trends in CS -
academic or professional as well as on a range of other topics.
</p>
<p>
One of the blogs I enjoy is authored by <a href="https://twitter.com/b0rk">Julia Evans</a>. I don't know
Julia, but we do have some mutual friends. I've enjoyed her <a href="http://jvns.ca">blog</a>. She
does a nice job talking about any number of systems related
issue. I've tried to leave comments a few times but for some reason,
my comments always end up deleted or otherwise not showing up.
</p>
<p>
One recent post, one on <a href="http://jvns.ca/blog/2016/03/29/thread-pools-part-ii-i-love-blocking/">concurrency</a> got me thinking. Since the comment
I left there didn't take, I thought I'd write about it here.
</p>
<p>
It's a nice post but the thing that caught my eye was when Julia
said that she " didn't know what a semaphore was until I read this
code and I was like OH THIS IS AMAZING AND SO USEFUL AND WOW." I was a
little surprised, semaphores seem to be one of those basic concepts
that you just know but that is, of course incorrect. I first learned
about semaphores in my honors Systems class with my mentor, the late
<a href="https://en.wikipedia.org/wiki/Robert_Dewar">Robert Dewar</a>. We started from test and set and worked our way up. I
had two other undergraduate classes that at least mentioned the topic.
</p>
<p>
Then again, I knew that many undergrads would never get a good
treatment of concurrency so I tried to build a bit in to the System
Level Programming course I designed while at Stuy.
</p>
<p>
This got me thinking - according to her linked in, Julia was a CS
major at McGill - a university that I hold in high regard but either
semaphores were never covered or their treatment didn't make enough of
an impact to be worth remembering. What topics do we cover in our
classes that kids just let fall to the wayside and what topics do we
end up losing as curricula change and we don't have an eye on the big
picture.
</p>
<p>
One big one is memory management. When APCS and college 101 classes
went to Java, memory management went out the window. Not a problem, as
long as memory issues are covered in some other course. Unfortunately
the don't seem to be. You can make a case that kids don't need to
understand memory management or anything about garbage collection but
I'd argue that while one might never have to do their own memory
management a good CS person should have some understanding of what's
going on under the hood or as my friend Gerry says "never use a
technology you couldn't write yourself."
</p>
<p>
Another biggie that I lived through was the IBM PC era. Prior to the
mid to late 80's when the IBM PC ruled the world, kids learned about
CS on timesharing systems. Once the PC took hold, every kid learning
programming or studying CS was working on their own machine. They had
full access to everything and the machine just supported a single
thread.
</p>
<p>
On the one hand, it was nice since you could easily play with low
level programming and hardware but on the other hand, a hole
generation didn't learn about the complexities of multiple users and
multiple processes.
</p>
<p>
Early in my career I designed courses and only later did I realize
that you can't just design a course, you have to look at the full arc
of a students education.
</p>
<p>
I think it's interesting to think about what concepts are getting left
on the side of the road and I wonder if the big players driving CS
education spend any time thinking about this bigger picture.
</p>
</div>
</div>IDE or the Cloudhttp://cestlaz.github.io/posts/2016-04-12-ide-or-cloud.html/2016-04-12T00:00:00-04:002016-04-12T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div id="outline-container-orgheadline1" class="outline-2">
<h2 id="orgheadline1"></h2>
<div class="outline-text-2" id="text-orgheadline1">
<p>
This weekend, I had a conversation on Twitter with my friend <a href="https://twitter.com/roybahat">Roy Bahat</a>:
</p>
<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="en" dir="ltr"><a href="https://twitter.com/zamansky">@zamansky</a> Mike, unrelated, what do you think of <a href="https://t.co/BT1ublbajF">https://t.co/BT1ublbajF</a> ?</p>— Roy Bahat (@roybahat) <a href="https://twitter.com/roybahat/status/718835740738650112">April 9, 2016</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>
<blockquote class="twitter-tweet" data-lang="en"><p lang="en" dir="ltr"><a href="https://twitter.com/roybahat">@roybahat</a>Maybe I'll blog about my thoughts about online environments vs local installs</p>— Mike Zamansky (@zamansky)
<a href="https://twitter.com/zamansky/status/718837282334240768">April 9, 2016</a></blockquote><script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>
<blockquote class="twitter-tweet" data-lang="en"><p lang="en" dir="ltr"><a href="https://twitter.com/roybahat">@roybahat</a> Agree with this but there are many issues. I'll try to write more later. Now going to see my son in <a href="https://twitter.com/umgass">@umgass</a> prod of Pinafore.</p>— Mike Zamansky (@zamansky) <a href="https://twitter.com/zamansky/status/718838508689993728">April 9, 2016</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>
<p>
Another friend had just asked me about IDEs vs local installs for learning enviromnents the day before.
</p>
<p>
So, should we use cloud based IDEs when teaching CS or should we use
local installs.
</p>
<p>
There isn't a single right answer but I thought I'd share some of my thoughts here.
</p>
<p>
I'm hoping this is helpful to both those of us in the trenches as well
as maybe some platform developers out there.
</p>
<p>
Some times, you don't have a choice.
</p>
<p>
On the web based side, does your school have the bandwidth. We're not
only talking about the pipe to the outside world but also <a href="http://www.nytimes.com/2016/01/14/nyregion/bronx-science-bans-cellphones-from-wi-fi-as-students-devour-it.html?_r=0">wifi within
the school</a>. If kids can't reliably get to the web based environment,
it's not a viable option. On the other hand, cloud based software will
always be up to date and properly configured and kids can use them
from home or pretty much anywhere they have a connection.
</p>
<p>
On the other side we have local installs. This can also present
problems. Is the teacher allowed to install locally? Does he or she
know how to do it? Who's going keep all the machines up to date and configured?
</p>
<p>
Assuming we can get past the technical issues we can start looking at
the education side of thing.
</p>
<p>
On the web based side, you've got a silo. This can be both good and
bad. In an intro class, using a tool like <a href="http://codesters.com">Codesters</a> can keep the cost
of entry low, allow students to share work online and allow teachers
to make use of their curricular materials. If you can't tell, I'm a
big fan of Codesters and the Codesters team. The limitation is that
you have to use their simplified interface and toolset.
</p>
<p>
Some web based IDEs like <a href="http://koding.com">Koding</a> offer more flexibility - one tool with
many languages as well as deployment. The cost is complexity. With
Koding, you're basically running a virtual machine in the
cloud. You've got their web based IDE and a terminal shell so it's not
as complex as doign everything from scratch locally but it's not as
structured as Codesters and is more of a general purpose site rather
than one focussed soley on learning.
</p>
<p>
Then you have <a href="http://repl.it">repl.it</a>. This looks to be a great platform for
experienced programmers to play with and explore new languages but I'd
be concerned about using it with beginners. It looks like they're
rolling out some teacher tools so this might be worth revisiting soon.
</p>
<p>
In any case and with other web based products, you're living in the
providers silo.
</p>
<p>
Personally, I'm a command line wonk and confessed Emacs geek so I'm
generally wary of an online environment without an exit strategy to
real world tools. Eventually, if all development moves into the
browser as platform then this problem goes away, but for now, you're
not going to have the expressive power and flexibility that a local
install gives.
</p>
<p>
Local installs let you use more powerful and flexible tools either
alone or in combination.
</p>
<p>
Keeping kids out of silos also makes it easier for them to learn new
tools, languages, and techniques.
</p>
<p>
Since I like generic tools, I'm not a fan of big professional IDEs
like Eclipse. I'm an Emacs geek but Atom, Sublime Text, and Vim are
all good as well.
</p>
<p>
There are also an assortment of beginner IDEs like Dr. Racket and I'm
a fan with these for beginners as long as there's an exit strategy.
</p>
<p>
For completeness, I should mention that if I weren't an old school
Emacs guy, I might check out something like JetBrain's IDEs. They're
much lighter weight than something like Eclipse but still full
featured. Somewhere between a true general purpose, customizable,
programmable editor and an all encompassing IDE.
</p>
<p>
In general, I use online enviromnents with my classes early on when:
</p>
<ul class="org-ul">
<li>They're pretty much identical or equivalent to the installed version.</li>
<li>They provide some value added (<a href="http://codingbat.com">codingbat</a> for example) so they're not
being used as a development environment but for some other purpose.</li>
<li>They help with student collaboration (such as cloud9 or Koding.com
for more advanced kids).</li>
</ul>
<p>
In any case, it's imporant that our kids aren't locked into any IDE be
it web based or local.
</p>
<p>
Our kids that go on to more advanced CS studies will certainly need to
break out of sheltered world of a learning IDE and we're not doing
them a service if we shelter them too long.
</p>
<p>
Our other kids also benefit from seeing beyond these restrictive
environments. A student might learn to code in Python in one of our
classes, but if we do our jobs right, that student might be writing a
little Javascript to automate Google Docs.
</p>
<p>
I can't tell you how many people I've seen go through online coding
courses in a web based enviromnent only to be unable to do anything
outside of that enviromnent.
</p>
<p>
At the end of the day, we want our kids to be empowered to grow on
their own. All of the things I've talked about here are merely
tools. Each has it's place. It's up to the teacher to make the roadmap
and to lead the student down the path.
</p>
</div>
</div>DevOps, or You don't know what the F you're doing!http://cestlaz.github.io/posts/2016-01-31-devops.html/2016-01-31T00:00:00-05:002016-01-31T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
Having just concluded almost a quarter century at one job in one
place, I've been reflecting on a number of things.
</p>
<p>
What I accomplished, what I've failed to accomplish, highlights,
low lights and everything in between.
</p>
<p>
I've also learned a lot over these twenty five years.
</p>
<p>
One thing I learned is DevOps and System Administration.
</p>
<p>
Back around 1993 or 1994 Stuy wasn't really on the internet. Yes, we
were able to scam stuy.edu even though we were a high school and yes
we did have a class B address block but no one really had access.
</p>
<p>
Somehow, Bruce, a student of mine at the time and I ended up with the
job of getting Stuy onto the internet. Bruce was one of our superstar
kids and people thought I had extensive experience setting up and
running networks. Truth be told I messed around a bit but there's no
way I would have hired myself for the job.
</p>
<p>
Nonetheless, we were off.
</p>
<p>
We were able to take one of the RS/6000 AIX workstations that were
supposed to be used as CAD stations and repurposed it as a server. We
made email accounts for everyone and were off.
</p>
<p>
Neither Bruce nor I really knew what we were doing but we figured
things out. I learned a lot from him and I'd like to think he also got
some benefit out of working with me. Fortunately, we seemed to have a
knack for <a href="http://www.amazon.com/Linux-System-Administration-Handbook-Edition/dp/0131480057/ref=pd_sim_14_2?ie=UTF8&dpID=61%2B57ajucML&dpSrc=sims&preST=_AC_UL160_SR117%2C160_&refRID=164V89GZMZM2X9M2S8AH">finding the answers</a>.
</p>
<p>
Of course, we had our moments. Once, we got a critical patch
announcement from IBM. It said that if we needed the patch and didn't
apply it were were in big trouble but if our machine didn't need it,
applying the patch would kill our system. It was unclear whether we
needed the patch or not.
</p>
<p>
After about a half hour research, we determined that we didn't need
the patch.
</p>
<p>
But applied it anyway :-(.
</p>
<p>
D'Oh.
</p>
<p>
After a brief set of panic attacks and a bunch of fumbling around, we
did manage to restore things.
</p>
<p>
So, Bruce and I ran the system for a year or so and as I said, I
learned a lot. Now, Bruce was close to graduating so I was starting to
worry that I'd have to figure this all out myself soon. That was a
seriously frightening thought.
</p>
<p>
I figured it would be good to bring in a couple of new super smart
students. As it turns out, Jon was one of them.
</p>
<p>
At one point, there was some problem and Bruce and I were going to
head to the office to try to figure it out. Jon asked if he could come
and watch. I thought that was a great idea so I agreed.
</p>
<p>
We all went to the office and Bruce and I went to work. After about
fifteen minutes, Jon blurted out:
</p>
<blockquote>
<p>
"I just figured how you guys do it!!!"
</p>
<p>
"You guys have no idea what the F you're doing!!!!!"
</p>
</blockquote>
<p>
We all cracked up.
</p>
<p>
He was absolutely right. We had no clue. We didn't know what we were
doing but we had become pretty good at figuring things out.
</p>
<p>
Truth be told, that really is the norm. If you already knew how to
solve the problem, well, then it really wouldn't have been a problem
to begin with.
</p>
<p>
So, you learn to figure it out. It's something I learned not to be
afraid of a long time ago. I hope that it's something I've been able
to convey to my students.
</p>Debugging deploymenthttp://cestlaz.github.io/posts/2016-01-23-debugging-deployment.html/2016-01-23T00:00:00-05:002016-01-23T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
SoftDev students are hard at work on their final projects. By now,
they all have fairly complex code bases. This limits how much I can
help them with debugging.
</p>
<p>
There are some problems, though, that they have to contend with that
even with experience, are hard to spot. Notably because the very
tools you use to debug these errors are part of the problem.
</p>
<p>
Last week, this happened twice. Both cases were brought to me by
really strong students which just goes to underscore how insidious
these problems can be.
</p>
<p>
Here's a fake code snippet of a <a href="http://flask.pocoo.org/">Flask</a> application that illustrates
both problems.
</p>
<div class="org-src-container">
<pre class="src src-python"><span class="linenr"> 1: </span>from flask import Flask, render_template
<span class="linenr"> 2: </span>
<span class="linenr"> 3: </span>app = Flask(__name__)
<span class="linenr"> 4: </span>
<span class="linenr"> 5: </span>@app.route("/")
<span class="linenr"> 6: </span>def index():
<span class="linenr"> 7: </span> return "hello"
<span class="linenr"> 8: </span>
<span class="linenr"> 9: </span>@app.route('/test/<some_data>')
<span class="linenr">10: </span>def test():
<span class="linenr">11: </span> picture_url = build_url(some_data)
<span class="linenr">12: </span> result = api_test(picture_url)
<span class="linenr">13: </span> do_something(result)
<span class="linenr">14: </span>
<span class="linenr">15: </span>if __name__ == "__main__":
<span class="linenr">16: </span> app.debug = True
<span class="linenr">17: </span> app.secret_key = "some secret key"
<span class="linenr">18: </span> app.run(host="0.0.0.0", port=8000)
</pre>
</div>
<p>
First, the "easy" one. The student was trying to deploy the
application. We use <a href="http://gunicorn.org/">Green Unicorn</a> to deploy our applications,
ultimately on <a href="http://digitalocean.com/">Digital Ocean</a> servers in the cloud.
</p>
<p>
The student was using the correct command:
</p>
<div class="org-src-container">
<pre class="src src-shell">gunicorn -W 4 -b 0.0.0.0:8000 app:app
</pre>
</div>
<p>
but it wasn't working. It ran, but whenever he went to the site, it
came back with an error.
</p>
<p>
The problem?
</p>
<p>
He had to change:
</p>
<div class="org-src-container">
<pre class="src src-python">if __name__ == "__main__":
app.debug = True
app.secret_key = "some secret key"
app.run(host="0.0.0.0", port=8000)
</pre>
</div>
<p>
to
</p>
<div class="org-src-container">
<pre class="src src-python">app.secret_key = "some secret key"
if __name__ == "__main__":
app.debug = True
app.run(host="0.0.0.0", port=8000)
</pre>
</div>
<p>
Normally, when developing and testing our applications, we use the
test server that's bundled with Flask. The line that reads
"app.run…" takes care of this.
</p>
<p>
When running the application as a "main program" - "python app.py" the
if statement is true and it runs the indented lines, setting the
secret key which is required for session management.
</p>
<p>
When running under <b><b>gunicorn</b></b>, the <b><b>gunicorn</b></b> server loads the
application as a module and then runs it. In this case name isn't main
so it never sets secret key and so we have a problem.
</p>
<p>
Pretty subtle and even though we did cover this in class, it comes up
pretty rarely so it's not an easy catch.
</p>
<p>
Then there was this problem.
</p>
<p>
The setup for this one's a little more complicated. The group was
using a facial recognition api. You provide the API with the url to an
image, it fetches it and does recognition.
</p>
<p>
It's also important to note that when Flask is running, it will serve
files from a static directory, so, if I'm running my flask server on
myhost, port 800 and you stored an image named picture.jpg in the
static directory, going to:
</p>
<verbatim>
http://myhost:8000/static/picture.jpg
</verbatim>
<br><br>
<p>
would get that image.
</p>
<p>
The group did things right. They ran the Flask test server to serve
the static files and then wrote a small python program to test the
api:
</p>
<div class="org-src-container">
<pre class="src src-python">picture_url = build_url(some_data)
result = api_test(picture_url)
do_something(result)
</pre>
</div>
<p>
Everything worked fine.
</p>
<p>
But, when they put this code in as a route in their web app (as in the
top code fragment), it froze.
</p>
<p>
They couldn't figure it out.
</p>
<p>
The code worked as a "stand alone" but not in the web app.
</p>
<p>
The problem?
</p>
<p>
Once again, the built in Flask development server.
</p>
<p>
The development server runs in a single thread / process. This means
it can only do one thing at a time. When they ran their test as a
separate program, the api they used made a request to their app to
serve up the static picture file and it worked.
</p>
<p>
When they ran from the Flask application itself, their app made a call
to the web api (line 12) and then blocked while waiting for the
response. The web api tried to request the image from the Flask app
but it was blocked – <b><b>deadlock</b></b>.
</p>
<p>
Again, the solution was to run the web app using a server that could
handle multiple requests - gunicorn.
</p>
<p>
Once again, that solved the problem.
</p>
<p>
Both of these problems were fairly subtle and very hard to catch -
even with experience. I remember the hours I lost when I was learning
this stuff.
</p>
<p>
Some times kids get caught up in algorithms or poor code design but
sometimes, it's just the tools.
</p>Cellular Automata for Pathfinding in NetLogohttp://cestlaz.github.io/posts/2016-01-17-maze-ca.html/2016-01-17T00:00:00-05:002016-01-17T00:00:00-05:00Mike Zamansky<link href="//cdn.rawgit.com/noelboss/featherlight/1.3.5/release/featherlight.min.css" type="text/css" rel="stylesheet">
<script src="//cdn.rawgit.com/noelboss/featherlight/1.3.5/release/featherlight.min.js" type="text/javascript" charset="utf-8"></script>
<style>
div.center {text-align:center;}
.smaller {height:200px;width:200px}
.center {text-align:center;}
.frame {width:600px;height:800px;}
</style>
<div class="center">
<a class="center" href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-start.png">
<img src="http://cestlaz.github.io/img/maze-ca/maze-start.png">
</a>
</div>
<br>
<div id="outline-container-orgheadline1" class="outline-2">
<h2 id="orgheadline1"></h2>
<div class="outline-text-2" id="text-orgheadline1">
<p>
<a href="http://cestlaz.github.io/2016/01/15/shift-image.html#.Vpvy4x8SrmE">Last time</a> we took a look at implementing a Cellular Automaton in
NetLogo to do some simple image manipulation. We just scratched the
surface. In class, the kids write pretty nice Photoshop Light
applications.
</p>
<p>
Today we'll look at some more ambitious problem solving - using a
Cellular Automaton to find a path through a maze.
</p>
</div>
</div>
<div id="outline-container-orgheadline2" class="outline-2">
<h2 id="orgheadline2">Part 1 - finding possible paths</h2>
<div class="outline-text-2" id="text-orgheadline2">
<p>
We'll use the image above as an example and a live model with all the
code is at the end of this post.
</p>
<p>
Each square of the maze is a
NetLogo patch. White square represent possible paths, Red is our
entrance, green our exit. As we explore the maze, we'll color the
cells yellow.
</p>
<p>
Remember, in a Cellular Automaton (CA), each cell makes a decision as to
it's next state based on information about its neighbors (up, down,
left, and right only in this case).
</p>
<p>
So, if every cell is looking around at it's neighbors, most cells
don't have enough information. The only white cell that might be on
the path from entrance to exit is the one next to the entrance - it
might be on the path.
</p>
<p>
This leads us to the first step of our CA rule set:
</p>
<div class="org-src-container">
<pre class="src src-netlogo">; if I have a green neighbor, I might be on the path, turn yellow
ask patches with [pcolor = white] [
if any? neighbors with [pcolor = red] [
set pcolor yellow
]
]
</pre>
</div>
<p>
(click images to enlarge)
</p>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-1.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-1.png">
</a>
<p>
Next time through, we notice that a cell might be on the path if it's
white and it has either red or yellow neighbors.
</p>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-2.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-2.png">
</a>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-3.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-3.png">
</a>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-4.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-4.png">
</a>
<p>
Eventually, we end up with a yellow abutting green - the exit.
</p>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-found.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-found.png">
</a>
<p>
Notice that each yellow cell is also numbered. The number indicates
how many steps it took to get there from the entrance. The
implementation is trivial:
</p>
<ul class="org-ul">
<li>Start by giving each patch a variable <b><b>step</b></b> and starting it at 0.</li>
<li>When a cell is about to turn yellow, it should look at it's yellow
or red neighbors, ask for their <b><b>step</b></b> value (they'll all be the
same - think about why), and set it's <b><b>step</b></b> value to one more
than that.</li>
</ul>
<p>
We'll use these step numbers to recover the actual shortest path.
</p>
</div>
</div>
<div id="outline-container-orgheadline3" class="outline-2">
<h2 id="orgheadline3">Part 2 - recovering the shortest path.</h2>
<div class="outline-text-2" id="text-orgheadline3">
<p>
We can now use the yellow patches with the step numbers to find our
way back.
</p>
<p>
We're going to build a solution set.
</p>
<ol class="org-ol">
<li>start with an empty solution set.</li>
<li>take the only green cell not in the solution set (let's call it <b><b>G</b></b>).</li>
<li>Ask <b><b>G</b></b>'s yellow neighbor with lowest step number to turn
itself green (that cell will be <b><b>G</b></b> next time around).</li>
<li>Place <b><b>G</b></b> into the solution set (leaving the new green cell as
the only green cell not in the solution set).</li>
<li>Repeat 2 - 5 until we're back at the entrance.</li>
</ol>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-back-1.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-back-1.png">
</a>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-back-2.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-back-2.png">
</a>
<a href="http://cestlaz.github.io/posts/2016-01-17-maze-ca.html/" data-featherlight="/img/maze-ca/maze-solved.png">
<img class="smaller" src="http://cestlaz.github.io/img/maze-ca/maze-solved.png">
</a>
<p>
This is one of my favorite intro topics. It's using a CA - something
normally just presented as a toy idea, to solve a real problem. It
reinforces parallel processing and foreshadows all sorts of pathfinding
ideas to come.
</p>
<p>
Below is the complete NetLogo program. You can look at the code by
clicking on the code tab at the bottom.
</p>
<p>
To run:
</p>
<ul class="org-ul">
<li><b><b>setup</b></b> sets up all the variables and clears the world.</li>
<li><b><b>buildmaze</b></b> builds a random maze.</li>
<li><b><b>solve</b></b> is a toggle to run through an entire solution.</li>
<li><b><b>step</b></b> single steps through the CA.</li>
<li><b><b>reset</b></b> Resets all the variables and recolors the maze to
unsolved.</li>
<li>The other buttons are toggles for drawing your own maze.</li>
</ul>
<div class="center frame">
<iframe class="center frame" src="http://cestlaz.github.io/img/maze-ca/maze.html"></iframe>
</div>
</div>
</div>Cellular Automata, NetLogo and real problemshttp://cestlaz.github.io/posts/2016-01-15-shift-image.html/2016-01-15T00:00:00-05:002016-01-15T00:00:00-05:00Mike Zamansky<style>
.center {text-align:center;}
.frame {width:640px;height:800px;}
</style>
<p>
We've been using <a href="https://ccl.northwestern.edu/netlogo/">NetLogo</a> in our intro course for years. It's a
wonderful programming environment. Many of you recall the <a href="https://en.wikipedia.org/wiki/Logo_(programming_language)">Logo</a>
programming language. NetLogo is like Logo but instead of programming
a turtle, you write a program that's run by multiple, perhaps hundreds
of turtles and also by the world the turtles live on.
</p>
<p>
Some of the reasons we like it are that it's:
</p>
<ul class="org-ul">
<li>An easy accessible textual programming language</li>
<li>Makes building a graphical interface trivial</li>
<li>great for modeling</li>
<li>Comes with tons of demo models</li>
</ul>
<p>
And now, with the latest version, NetLogo programs/models can be
deployed as web sites. All you have to do is save your program as
"NetLogo Web" and put it up on a observer somewhere.
</p>
<p>
If you haven't you should download and install NetLogo, run it, then
go to the file menu and look at the built in models.
</p>
<p>
I also enjoy playing with <a href="https://en.wikipedia.org/wiki/Cellular_automaton">Cellular Automata</a> and NetLogo's a wonderful
platform to play with. The turtles live on a grid of patches and just
like the turtles, the patches will all run your program over and over.
</p>
<p>
The patches make perfect cells for a cellular automaton and you can
implement a rule set in your patches.
</p>
<p>
NetLogo even comes with a bunch of built in demo models for Cellular
Automata including <a href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">Conway's Game of Life</a>, probably the most famous CA.
</p>
<p>
On the other hand, Conway's Game of Life is somewhat cliche and while
I find it fascinating, it doesn't really solve a practical problem, at
least on on the surface.
</p>
<p>
So, I was looking for something more practical to do and something
where we could explore some deeper CS concepts.
</p>
<p>
Image manipulation.
</p>
<p>
In class, we make a Cellular Automaton where each cell or patch is a
pixel in an image. In NetLogo, you can do this with the
"import-pcolors" command. Lower down, I have a demo that just manually
colors patches - the web version of NetLogo doesn't yet support that
command.
</p>
<p>
Task 1 - what if we want to shift the image over? The kids come up
with a solution pretty quickly: "We can just have each patch ask its
neighbor for its color." Here's the code they try:
</p>
<div class="org-src-container">
<pre class="src src-netlogo">; ask each patch to set its color to the color of the
; patch at relative location -1,0
to shift-naive
ask patches [ set pcolor [pcolor] of patch-at -1 0]
end
</pre>
</div>
<p>
To see what happens, scroll down to the NetLogo model below, click on
setup and then hit the <b><b>shift-naive</b></b> button a few times.
</p>
<p>
It doesn't work.
</p>
<p>
What's going on?
</p>
<p>
It's a synchronization issue.
</p>
<p>
Suppose we have the following three cells in a row:
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/shift-image/image1.png" alt="image1.png">
</p>
</div>
<p>
If cell 3 asks cell 2 it's color before cell 2 asks cell 1's color, we
get the desired result:
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/shift-image/image2.png" alt="image2.png">
</p>
</div>
<p>
But if cell 2 asks cell 1 for it's color first then cell 3 will
actually get cell 1's color:
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/shift-image/image3.png" alt="image3.png">
</p>
</div>
<p>
So now we have the students thinking about synchronization and
parallel processing and they don't even know it.
</p>
<p>
The solution's pretty easy, break the problem up into two steps.
</p>
<p>
First, have every patch ask its neighbor for its color and then once
everyone knows their neighbor's color, then change:
</p>
<div class="org-src-container">
<pre class="src src-html">patches-own [next-color]
to shift-correct
; figure out my next color
ask patches [ set next-color [pcolor] of patch-at -1 0 ]
; then switch to it
ask patches [ set pcolor next-color]
end
</pre>
</div>
<p>
You can run that by clicking <b><b>setup</b></b> again and then <b><b>shift-correct</b></b> a
few times.
</p>
<p>
There's some of the beauty of NetLogo - we can get kids to think about
some deep concepts while playing with an easy to use, fun, interactive
environment with a real textual programming language.
</p>
<p>
Stay tuned for part 2 when I'll talk about creating a cellular
automaton that can solve a maze.
</p>
<div class="center frame">
<iframe class="center frame" src="http://cestlaz.github.io/img/shift-image/shift-image.html"></iframe>
</div>Teaching Coding - getting beyond superficial syntaxhttp://cestlaz.github.io/posts/2016-01-01-different-languages.html/2016-01-01T00:00:00-05:002016-01-01T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
The other day, Alfred Thompson put up a piece about <a href="http://blog.acthompson.net/2015/12/code-in-different-languages.html">coding in multiple
languages</a>. Alfred references a post written last May by <a href="http://robunderwood.com/2015/05/31/code-syntax-compared-part-1/%0A">Rob Underwood.</a>
</p>
<p>
Both pieces are worth a look.
</p>
<p>
Rob is trying to illustrate many of the superficial similarities in
popular languages.
</p>
<p>
In the comments on Alfred's blog, both Alfred and I alluded to coding
in an appropriate style for the language.
</p>
<p>
For me the issue is even bigger.
</p>
<p>
Learning to code is all the rage and places to learn are popping out of
the woodwork.
</p>
<p>
There are:
</p>
<ul class="org-ul">
<li>In classes, in schools, with teachers</li>
<li>Drop in programs in schools.</li>
<li>Programs run by coding schools</li>
<li>Moocs and other online resources</li>
<li>Summer and weekend programs</li>
</ul>
<p>
And probably more. All of these options are giving more and more
people a way to learn to code.
</p>
<p>
That's great, but it also raises concerns given that very few people
involved in CS education have both strong teaching and CS backgrounds.
</p>
<p>
What I'm starting to see are the results as I meet young people coming
out of all of these programs.
</p>
<p>
Unfortunately, what I'm frequently seeing, at best, is very
superficial coverage of syntax.
</p>
<p>
I've seen kids who would have no basis for understanding that the
ramifications of this Python code:
</p>
<div class="org-src-container">
<pre class="src src-python">a = 30
def f():
a=20
print a
print a
</pre>
</div>
<p>
and this Javascript code:
</p>
<div class="org-src-container">
<pre class="src src-javascript">a = 30;
function f(){
a = 20
console.log(a);
}
console.log(a);
</pre>
</div>
<p>
are very different.
</p>
<p>
It gets worse when I meet kids who "know C" because they were exposed
to constructs like:
</p>
<div class="org-src-container">
<pre class="src src-c">for (i=0;i<10;i++){
// code goes here
}
</pre>
</div>
<p>
I think the most common issue come from kids being "taught"
programming using javascript which seems deceptively simple but is
really rather deep.
</p>
<p>
It's important that as CS becomes more mainstream that we make sure
that we have teachers and programs that are teaching the real deal. It
can be fun and accessible but it does require teachers that know their
stuff and are willing to continue to learn.
</p>
<p>
Do our kids deserve any less?
</p>Advent of Code - because I'm an idiothttp://cestlaz.github.io/posts/2015-12-17-im-an-idiot.html/2015-12-17T00:00:00-05:002015-12-17T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/advent/advent.png" alt="advent.png" width="480px" align="center">
</p>
</div>
<p>
I wish our kids believed us when we tell them that we have the same
programming troubles as they do. We stare at code for hours not seeing
problems that could be a simple as passing the wrong value. We spend
an inordinate amount of time trying to see the problem and then
realize that we just forgot something silly.
</p>
<p>
At this point, it's common for us CS teachers to tell each other "I
figured out the problem I was having – it's that I was an idiot."
</p>
<p>
Last time, I talked about <a href="http://adventofcode.com/">Advent of Code</a> and how I was somewhat behind
the curve. In part because I started late and in part because I've
been using it as an excuse to learn some Clojure.
</p>
<p>
Here's how I burned over two days on <a href="http://adventofcode.com/day/6">Day 6</a>.
</p>
<p>
The problem is pretty straight forward. You have a 1,000 x 1,000 grid
representing a light board and you have to repeatedly do operations on
smaller rectangles on that grid. Turning individual lights on and off,
if you would.
</p>
<p>
If I were doing this in a language like C, I'd probably just take a
big block of memory and loop through the instructions but since I was
working in Clojure, I thought I'd try to do something in more of the
functional mode, that is, with immutable data types.
</p>
<p>
After a while, I was getting the feeling that it was going to be too
slow so I shifted to just modifying a big block of memory.
</p>
<p>
Try as I could, I couldn't get it to work. I was sure my algorithm was
fine - it wasn't a hard problem, but I couldn't get the right answer.
</p>
<p>
After a while, I started looking at existing solutions and they were
basically the same as mine.
</p>
<p>
I was stumped.
</p>
<p>
Two days after the start, I figured it out.
</p>
<p>
No matter how hard you try, if your problem specifies the data in the
form <b><b>row1,col1 row2,col2</b></b>, you're not going to get the right answer
if you decide that the input is in the form <b><b>row1,row2 col1,col2</b></b>.
</p>
<p>
<b><b>D'Oh</b></b>
</p>
<p>
Ok, after that the problem was pretty trivial.
</p>
<p>
Hopefully I'll have some time to do problem 7 and beyond this weekend.
</p>
<p>
If there are any Clojure people out there, I'm putting my solutions up
on <a href="https://github.com/zamansky/adventofcodeclojure">GitHub</a> - I'd love some feedback on how to get more idiomatic.
</p>Other People's Codehttp://cestlaz.github.io/posts/2015-11-11-other-peoples-code.html/2015-11-11T00:00:00-05:002015-11-11T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div id="outline-container-orgheadline1" class="outline-2">
<h2 id="orgheadline1"></h2>
<div class="outline-text-2" id="text-orgheadline1">
<blockquote>
<p>
The coding on their project is reminiscent in many ways of an Ed
Sheerhan song. It left me in tears and very confused as to what the
author was trying to accomplish.
</p>
<p>
– a student commenting on their most recent project.
</p>
</blockquote>
</div>
</div>
<div id="outline-container-orgheadline2" class="outline-2">
<h2 id="orgheadline2"></h2>
<div class="outline-text-2" id="text-orgheadline2">
<p>
We had some fun last week. Well, OK, I had some fun. The SoftDev
classes had just finished a little project. Basically, a blogging
platform. Something that would tie together all the tools we've been
using. Flask, user management, an SQL database (SQLite), and a nice
looking front end.
</p>
<p>
It was also the first real group project so the teams have started to
learn how to work together.
</p>
<p>
After some project demos, it was time for part two: NOSQL. We explored
MongoDB and then it was time for the project - clean up the
previous project through the use of techniques like template
inheritance and convert the database backend to MongoDB.
</p>
<p>
The catch? Each group would take another groups project and use that
as their starter code. The rules? They could modify and refactor but
they couldn't rewrite.
</p>
<p>
It threw the groups for a loop but I ultimately think they had
fun with this.
</p>
<p>
Afterwards each group gave a write up to their starter group. What
made their life easier, what made it harder. We then circled up for
discussion as a class.
</p>
<p>
It was terrific.
</p>
<p>
First, it was great that we've gotten to a point where everyone feels
comfortable giving each other constructive criticism. We've gotten to
the point where the class is a team.
</p>
<p>
Beyond that, I'm hoping that everyone got a lot out of the exercise.
</p>
<p>
As each group talked, common themes arose:
</p>
<ul class="org-ul">
<li>consistent commenting is good</li>
<li>variable names matter</li>
<li>unused code and files can be misleading</li>
<li>overall code structure, file names, and locations are important.</li>
<li>and much more</li>
</ul>
<p>
We're now going to start a discussion of coding style, standards, and
documentation.
</p>
<p>
I've got to say that I'm very happy how this little experiment worked
out.
</p>
</div>
</div>Interview questions and testshttp://cestlaz.github.io/posts/2015-11-04-tests-and-interviews.html/2015-11-04T00:00:00-05:002015-11-04T00:00:00-05:00Mike Zamansky<p>
The StuyCS Family mailing list was host to an interesting discussion
today. One of our younger members asked if the practice of giving
technical problems during an interview was going to follow him
throughout his career or if it goes away for more senior applicants.
</p>
<p>
An interesting discussion followed.
</p>
<p>
It reminded me of a time I was talking to a few senior engineers at a
large tech company. A couple of younger engineers were with us along
with a new hire. The youngsters started talking about the new hires
technical interview questions. One older engineer light heartedly
asked another "I don't recall any tricky technical questions, how
about you?" "I don't recall any either…" and on around the table.
</p>
<p>
Of course these senior engineers had track records that stretched for
miles.
</p>
<p>
I never liked those tech interview questions. If you just took
algorithms, you've got an edge and it really seems to be more of a
test of "have you seen this problem before" rather than a true test of
ability.
</p>
<p>
I much prefer those few companies that give "take home assignments" or
use other ways to determine fit.
</p>
<p>
The tech interview reminds me of the pop quiz or a poorly designed
test. If you just ask the question that the kid doesn't get, the kid's
in trouble. A kid could know how to handle 90% of the work but if the
question is that last 10%, zero credit.
</p>
<p>
As teachers, we end up using many forms of assessment and try to
develop an overall picture of a student.
</p>
<p>
Companies should try to do the same.
</p>
<p>
Why to companies still use these technical interview questions?
</p>
<p>
Quite simply because they can.
</p>
<p>
A company might miss out on a number of great candidates by using a
bad technical question but they will probably get at least a
reasonably strong hire that passes the test. For the company, mission
accomplished.
</p>
<p>
As teachers, we can't do that. I'm not given a class of 32 kids and
asked to pull out a couple of software engineers. As teachers, we're
supposed to pull everyone along.
</p>Alan Alda on Teaching Sciencehttp://cestlaz.github.io/posts/2015-10-20-alda.html/2015-10-20T00:00:00-04:002015-10-20T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
Scale, scale, scale. Scripted lessons. Online resources, Moocs. No
excuses schools. All of these are modern trends in education. None of
these are about good education. It's really demoralizing reading
article after article devaluing true master teachers and real
education.
</p>
<p>
So, last night was a real pleasure.
</p>
<p>
I attended a talk, given by Alan Alda on communicating science. The
talk was sponsored by <a href="http://academyforteachers.org/">The Academy for Teachers</a>. I grew up watching
Hawkeye on MASH and more recently Arnold Vinick on The West Wing but
Mr. Alda has really been keeping himself busy in the world of
education. Check out what he's doing at the <a href="http://www.centerforcommunicatingscience.org/">Alan Alda Center for
Communicating Science</a> at Stony Brook University.
</p>
<p>
At it's core, Mr. Alda's talk was about teaching. Making a connection
with your students and engaging them. The exact opposite of many of
the current ed reform trends.
</p>
<p>
Mr. Alda talked about <a href="http://www.centerforcommunicatingscience.org/the-flame-challenge-2/">the Flame Challenge</a> where he challenged
scientists to teach 11 year olds all about <a href="https://en.wikipedia.org/wiki/The_Chemical_History_of_a_Candle">a candle</a> without dumbing it
down. Communication.
</p>
<p>
He also talked about story telling. At one point he had a volunteer
from the audience carry a glass across the stage. He then had her do
it again, but this time with a full glass telling her "if you spill a
drop everyone in your village will die." The difference in audience
attention was striking.
</p>
<p>
Mr. Alda also talked about using improvisational games to help
students open up as well as about <a href="https://en.wikipedia.org/wiki/Curse_of_knowledge">the curse of knowledge.</a>
</p>
<p>
One of my favorite parts of the talk was when an audience member asked
for a few teaching tips. He replied that he hates tips because out of
context, without the connection to the class, they're
meaningless. Mr. Alda used as an example:
</p>
<blockquote>
<p>
Imagine that you're about to give a piano recital at Carnegie Hall
and you asked for a few tips.
</p>
<p>
If you've never played before, those tips aren't going to help you.
</p>
</blockquote>
<p>
I'm asked for CS teaching tips all the time, and Mr. Alda very much
captured my feelings on the subject. My friend and Colleague Jim
Cocoros also captured the feeling when he reminded me that the only
"tip" he gives new teachers is "be yourself." I couldn't agree more.
</p>
<p>
It was a delightful and a refreshing evening. I very much appreciate
and admire what Mr. Alda is doing beyond his acting and while I very
much hope he's able to extend his reach to more high school teachers
as he continues to work on communicating in science.
</p>Looking under the hoodhttp://cestlaz.github.io/posts/2015-10-17-under-the-hood.html/2015-10-17T00:00:00-04:002015-10-17T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
Just had an interesting conversation with <a href="http://chrisgrant.co/">Chris</a>, one of our <a href="http://cstuy.org/">CSTUY</a>
mentors. Chris is working with one of our more advanced groups of
hackers - they'll be creating a web based app that with ultimately be
deployed as mobile using <a href="http://phonegap.com/">PhoneGap</a>.
</p>
<p>
The question he had was "<a href="http://angularjs.org/">Angular.js</a> or <a href="http://backbonejs.org/">Backbone.js</a>."
</p>
<p>
Chris and I have had this conversation before. I was explaining at the
time why I preferred to use Backbone.js over Angular in my SoftDev
classes. Part of the reason is that the current version of Angular is
already deprecated while the new version isn't ready for prime time
yet. This means I'd be teaching to a dead end. More importantly, Angular
is a much higher level framework than Backbone. There's a lot of
"magic" going on. Just a few short lines of code and you're done.
</p>
<p>
Backbone is much closer to the metal. It does less work for you so it
let's me drill down with the kids all the way to the source. This way
the kids understand what's going on under the hood. As my buddy <a href="https://www.linkedin.com/in/gerryseidman">Gerry</a>
says, "never use a tool you couldn't write yourself." I personally
like low level tools like Backbone.js. If you have to get a job
done quickly, it might not be the right tool, but for teaching,
it's terrific.
</p>
<p>
I think Chris was surprised when I said that a higher level tool like
Angular could very well be appropriate for our Saturday Hackers and
that I'd certainly support whichever direction Chris wanted to go in
with his team.
</p>
<p>
Why might it be right in this case?
</p>
<p>
Mostly because the hackers only meet once a week. In our Saturday
sessions, we want our kids to learn, but we also need to create an
environment where they can continue to progress on their
projects. Some times, compromise is needed. Angular will let them get
up and running within the constraints of our program and the hackers
will still learn a lot, particularly with people like Chris mentoring them.
</p>
<p>
That's the balance we strive to achieve - a good amount of real CS but
tempered with the realities of a once a week program.
</p>
<p>
We could go the way of many other CS programs out there and
just use tools that do 90% of the work but we like to think we have a
higher standard and I think that's what makes our team of teachers and
mentors special.
</p>Grading Autogradershttp://cestlaz.github.io/posts/2015-10-16-graders.html/2015-10-16T00:00:00-04:002015-10-16T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
The other day codehs made an announcement about their new
<a href="https://medium.com/codehs-product-updates/these-are-the-autograders-you-ve-been-looking-for-bda0fa8fd8a">autograder</a>. Fellow CS Teaching veteran Alfred Thompson had his say up
on his <a href="http://blog.acthompson.net/2015/10/autogradersfor-good-or-for-evil.html">blog</a> where he talked about <a href="https://computinged.wordpress.com/">Mark Guzdial</a>'s comment on
autograders leading to less creative assignments.
</p>
<p>
I very much agree that autograders, due to their rigidness lend
themselves to less creative projects, but thought I'd write up a few
of my own thoughts on autograders.
</p>
<p>
First and foremost, <b>I HATE GRADING</b>. It's one of the worst parts of
my job and grading projects is <b>really</b> hard to do well.
</p>
<p>
You'd think an autograder would be a panacea.
</p>
<p>
It's not.
</p>
<p>
In addition to them being very nit-picky – got an extra space in your
output? <b>FAIL</b>. Wrong number of significant digits? <b>FAIL</b>. Didn't
handle all those "trick" cases? <b>FAIL</b>.
</p>
<p>
Since autograders typically check your output against a correct
solution, it's going to be limited in what it can grade right and
wrong and what's more, it's very limited in the feedback it can give.
</p>
<p>
These are some of the limitations that lead to less creative
projects but that's not my beef with the autograders.
</p>
<p>
Why do we give assignments? To assess students? Yes, but also to
inform our instruction. We need to grade the assignments ourselves
because those assignments tell us about our students and teach us how
best to work with them. What's more, we really don't just want to see
that finished product, but rather, we want to see the process as
well. Autograders can't help here.
</p>
<p>
I do use autograders – <a href="http://codingbat.com/">codingbat.com</a> and our own locally developed
<a href="http://bert.stuy.edu/pbrooks/SchemingBat/scheming.py">Scheming Bat.</a> I use them for small homeworks and class assignments
early on. For bigger stuff, I do it myself.
</p>
<p>
For advanced classes (AP and beyond) we're all about the GitHub. Not
only can I grab the projects at any time but I can also see how
projects were developed - logs, diffs, <a href="https://github.com/vynl/vynl-v0/graphs/contributors">graphs</a>. All give me insight
into how the students working. Add in class lab time when I get to
interact with the kids and I've got a good sense of my student
computer scientists.
</p>
<p>
In our intro courses, where they're not ready for GitHub, we use
Dropbox for sharing and collecting assignments. Not quite as good but
we can still see a lot.
</p>
<p>
At the end of the day, if a teacher doesn't look at a student's work
directly, a teacher isn't going to know everything there is to know
about a student. I can't imagine a top English teacher not reading a
student's essays. We're no different.
</p>
<p>
It's time consuming and generally no fun but it's a big part of <b>real</b>
education.
</p>Setting kids up to fail - CS editionhttp://cestlaz.github.io/posts/2015-08-17-setting-up-to-fail-cs.html/2015-08-17T00:00:00-04:002015-08-17T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div id="outline-container-sec-1" class="outline-2">
<h2 id="sec-1"></h2>
<div class="outline-text-2" id="text-1">
<p>
We talked about setting kids up to fail in math. What about CS?
</p>
<p>
Well, it's a little subtler.
</p>
<p>
I started thinking about this after a conversation with one of my
graduates about Harvard's famous CS50. Since that conversation, I've
spoken to a number of my kids that have gone through CS50 and most
seem to say the same things:
</p>
<ul class="org-ul">
<li>They don't really teach anything
</li>
<li>The kids rely on a group member who already knows stuff or will
learn all the stuff on their own
</li>
<li>If it weren't for my StuyCS background my group would have really
struggled.
</li>
</ul>
<p>
and things like that. I was then told that after CS50 kids go on to
Functional Programming in OCAML and they drop like flies.
</p>
<p>
Doesn't sound like a recipe for success.
</p>
<p>
We're seeing this at multiple levels and we're seeing it because very
few places seem to have a plan. A multi year path taking kids from
start to finish. It's something we've done and I'm proud of it.
</p>
<p>
I think that if we look carefully, we'll start to see what my
graduates reported happening more and more. Traditional CS sequences
can be pretty unforgiving and unless colleges put in a sensible ramp
up and recognize that not all CS and related majors should go on to
grad school we're going to have a high rate of kids initially thinking
that CS is for them and then dropping. I do suspect it will get better as colleges
recognize that there's more than one type of CS major.
</p>
<p>
It will be interesting to see what happens on the high school
level. Will we see what we've seen in math - two years on the first
level course then dump the kids into something like APCS A or will we
see something more sensible?
</p>
<p>
Where this really gets me is with all those after school and summer
programs. One give away is when a program claims "learn to <span class="underline"><span class="underline">_</span></span> in 4
weeks," "our kids learn more than in an AP class", or something similar.
</p>
<p>
My team and I have had to "rescue" kids from a number of
them.
</p>
<p>
These programs take a number of forms:
</p>
<ul class="org-ul">
<li>Using simplified environments that export to mobile
</li>
<li>Gluing together libraries with minimal code
</li>
<li>Working with an extreme amount of coaching in a short period of
time.
</li>
</ul>
<p>
Now, none of these things are necessarily bad but so many of these
programs are designed and run by non-educators.
</p>
<p>
So, the kids go through the programs, think they know the real deal,
and are hammered when they enroll in a real CS class.
</p>
<p>
I've seen it happen. There was even an article a couple of years ago
which then went on to blame the teacher in spite of the fact that the
program boasts that thier kids "learned more than in APCS."
</p>
<p>
Now, all these programs have to do is make sure the kids make
something exciting and that they're happy. There's no real
accountability and the guy at the next level will shoulder the blame.
</p>
<p>
So there you have it, setting kids up to fail.
</p>
<p>
It's something I think we'll have to be more aware of and on guard for
as CS becomes more mainstream.
</p>
</div>
</div>Shipping a producthttp://cestlaz.github.io/posts/2015-06-19-shipping-product.html/2015-06-19T00:00:00-04:002015-06-19T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div id="outline-container-sec-1" class="outline-2">
<h2 id="sec-1"></h2>
<div class="outline-text-2" id="text-1">
<p>
Back in April, I was at the second annual "Dream It, Code It, Win It!"
awards. Some of our kids had submitted work and were selected as
awardees in the high school division.
</p>
<p>
It was great to see <a href="https://twitter.com/Cahnja">Jack</a> and <a href="https://twitter.com/davcahn">David</a> Cahn there. Jack and David were
both members of winning high school teams last year and they were back
as college winners this time around.
</p>
<p>
It was great to see them.
</p>
<p>
The Cahn brothers spent some time talking to the current crop. They
mentioned one thing that really confirmed that I've been on the right
track with my SoftDev class - they said it was their most valuable
experiece at Stuy because they learned how to ship a product. To take
something, as a team, from idea to delivery with all the bumps along
the way. Now, obviously, we don't do everything - there are no
questions of funding for instance and I think we cover a lot of great
CS but giving the kids a chance to learn to take a project from idea
to delivery and all that entails was a big part of the design of the
course.
</p>
<p>
With that in mind, I just finished evaluating projects and here's a
sampling:
</p>
</div>
</div>
<div id="outline-container-sec-2" class="outline-2">
<h2 id="sec-2"></h2>
<div class="outline-text-2" id="text-2">
<p>
Stuy kids live all over the city. Nadia, Aida, and Sydney solved the
problem of where to meet your friends when you live on opposite sides
of town:
</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/i_xDQg35T20" frameborder="0" allowfullscreen></iframe>
</div>
<div id="outline-container-sec-2-1" class="outline-3">
<h3 id="sec-2-1"></h3>
<div class="outline-text-3" id="text-2-1">
<ul class="org-ul">
<li>Live demo: <a href="http://meetup.jumpingcrab.com/">http://meetup.jumpingcrab.com/</a>
</li>
<li>GitHub: <a href="https://github.com/apiccato/meetup">https://github.com/apiccato/meetup</a>
</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-sec-3" class="outline-2">
<h2 id="sec-3"></h2>
<div class="outline-text-2" id="text-3">
<p>
Miranda, Leslia, and Anya built a Chrome plugin and server to
summarize articles:
</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/pvRf7fPlV6Q" frameborder="0" allowfullscreen></iframe>
</div>
<div id="outline-container-sec-3-1" class="outline-3">
<h3 id="sec-3-1"></h3>
<div class="outline-text-3" id="text-3-1">
<ul class="org-ul">
<li>Server: <a href="http://104.236.53.73/">http://104.236.53.73/</a>
</li>
<li>Chrome plugin: <a href="https://chrome.google.com/webstore/detail/dmbibehpblbnkacpmiecigdkcomfkhkm/">https://chrome.google.com/webstore/detail/dmbibehpblbnkacpmiecigdkcomfkhkm/</a>
</li>
<li>GitHub: <a href="https://github.com/mchaiken/summarize">https://github.com/mchaiken/summarize</a>
</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-sec-4" class="outline-2">
<h2 id="sec-4"></h2>
<div class="outline-text-2" id="text-4">
<p>
and Philipp, Richard, Steve, and Ziwei created an anonymous author
attribution system:
</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/XksrKfxEprg" frameborder="0" allowfullscreen></iframe>
</div>
<div id="outline-container-sec-4-1" class="outline-3">
<h3 id="sec-4-1"></h3>
<div class="outline-text-3" id="text-4-1">
<ul class="org-ul">
<li>GitHub: <a href="https://github.com/I-A-I/authorensics">https://github.com/I-A-I/authorensics</a>
</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-sec-5" class="outline-2">
<h2 id="sec-5"></h2>
<div class="outline-text-2" id="text-5">
<p>
Not a SoftDev project, but for good measure, here's Natan and
Angelika's Ballroom Dance project - apparently they're the first two
to actually do a SONG and dance and they've both got the pipes:
</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/_xjHFdrJ4jQ" frameborder="0" allowfullscreen></iframe>
<p>
There were lots of other great projects all up on github:
<a href="https://github.com/stuycs-softdev/student-work-spring-2015">https://github.com/stuycs-softdev/student-work-spring-2015</a> albeit in a
rather disorganized form.
</p>
<p>
So proud of the work they all did this year.
</p>
</div>
</div>Jazz Hands!!!!!!http://cestlaz.github.io/posts/2015-06-11-jazz-hands.html/2015-06-11T00:00:00-04:002015-06-11T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/jazz-hands/jazzhands.gif" alt="jazzhands.gif" width="300px" align="center">
</p>
</div>
<div id="outline-container-sec-1" class="outline-2">
<h2 id="sec-1"></h2>
<div class="outline-text-2" id="text-1">
<p>
The StuyCS Semi Formal, Clyde "Thluffy" Sinclair, and other assorted
<a href="http://cestlaz.github.io/2015/03/08/antother-day-stuycs.html#.VXmHfN_08bw">silliness</a> - one of the reasons StuyCS is a family is that we try to
have fun.
</p>
<p>
Jazz Hands day was the latest.
</p>
<p>
I got the idea at JonAlf's wedding. The wait staff were all wearing
white gloves - all of a sudden it hit me - Jazz Hands!!!! and Jazz
Hands day was born.
</p>
<p>
The idea:
</p>
<p>
All of our Junior and Senior CS students, around 350 or so, along with
their teachers would wear white gloves on a specified day. The rules
were throughout the day, in any class, provided there were two or more
CS Jazz Hands students in the class, whenever:
</p>
<ul class="org-ul">
<li>a student gave a good thoughtful answer to a question
</li>
<li>or the teacher made a particularly strong point
</li>
</ul>
<p>
The kids would give a Jazz Hands salute.
</p>
<p>
Imagine, some kid gives a great answer and 1/3 of the class all of a
sudden does Jazz Hands!!!!
</p>
<div class="figure">
<p><img src="http://cestlaz.github.io/img/jazz-hands/jazzhands2.gif" alt="jazzhands2.gif" width="300px" align="center">
</p>
</div>
<p>
Unfortunately, this was an event that I wouldn't actually be able to
see as the havoc would be wreaked in other classes.
</p>
<p>
By the time we got to the end of the day, I knew we were on to
something.
</p>
<p>
Word on the street was that a bunch of teachers thought it was
hilarious. Apparently one teacher pulled the math chair into her class
so she could see.
</p>
<p>
Then we had at least a few teachers that didn't get into the spirit
and actually lodged complaints.
</p>
<p>
Let's see, we had students, via a non-verbal form of feedback,
indicate that they were totally engaged by acknowledging what they
felt was a good point.
</p>
<p>
Disruptive?
</p>
<p>
Imagine that.
</p>
<p>
I don't know what makes me want to fine tune this event more - the
positive feedback or the complaints.
</p>
<p>
``
</p>
</div>
</div>Taking stock and tracking progresshttp://cestlaz.github.io/posts/2015-02-11-taking-stock-self-assess.html/2015-02-11T00:00:00-05:002015-02-11T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
When starting the spring semester, students are frequently a little
rusty. They just had a high intensity month of study, tests, and
projects. That was followed by a week of nothing.
</p>
<p>
I like to start with something lightweight that gets them coding again
and ramps them up to speed.
</p>
<p>
In SoftDev I started with a brief overview of the HTML5 canvas and
then gave them a small homework assignment to do something fun.
</p>
<p>
I also remind the kids to self assess where they are and how they've
developed as a programmer.
</p>
<p>
I get a little tired of education "experts" espousing nonsense like you
have to have each talk each day or that you need to assess each kid
multiple times a period. That's nonsense. With 34 kids in a 40 minute
class and 150 kids a day, that doesn't fly. Besides, so many concepts
take time to develop, learn, and absorb.
</p>
<p>
Yes, you can get some instant and short term feedback but a lot more
is revealed over time.
</p>
<p>
I'm attaching a small sampling of their homework assignments. It was
basically a one day assignment to do something fun with the HTML5
canvas and indeed, it looks like they had fun.
</p>
<p>
I asked the kids to reflect on what they did now and what they could
do a semester, two, and three semesters ago.
</p>
<p>
In the beginning they would have had no idea how to approach any of
these. A year ago, they would be a major project. Now, they can knock
these out as a homework assignment.
</p>
<p>
Once you take a step back to look at how much a student can grow in a
year or so you have to marvel at the results.
</p>
<p>
At a place like Stuy, the kids frequently and unfairly judge themselves against
super prodigies.
</p>
<p>
I'm hoping by looking back at what they could do then vs now they'll
appreciate how awesome they are.
</p>
<p>
All sources at <a href="https://github.com/stuycs-softdev/submissions">https://github.com/stuycs-softdev/submissions</a>
</p>
<p>
Enjoy…
</p>
<div id="outline-container-unnumbered-1" class="outline-2">
<h2 id="unnumbered-1">Chain reaction</h2>
<div class="outline-text-2" id="text-unnumbered-1">
</div><div id="outline-container-unnumbered-2" class="outline-3">
<h3 id="unnumbered-2">click to start the reaction</h3>
<div class="outline-text-3" id="text-unnumbered-2">
</div><div id="outline-container-unnumbered-3" class="outline-4">
<h4 id="unnumbered-3">by Nadia and Sophie</h4>
<div class="outline-text-4" id="text-unnumbered-3">
<iframe height="600" width="80%" src="https://cdn.rawgit.com/stuycs-softdev/submissions/master/6/canvas/sophie-nadia/canvas.html">
</iframe>
</div>
</div>
</div>
</div>
<div id="outline-container-unnumbered-4" class="outline-2">
<h2 id="unnumbered-4">MakeOver Party</h2>
<div class="outline-text-2" id="text-unnumbered-4">
</div><div id="outline-container-unnumbered-5" class="outline-3">
<h3 id="unnumbered-5">Take a picture and apply virtual makeup</h3>
<div class="outline-text-3" id="text-unnumbered-5">
</div><div id="outline-container-unnumbered-6" class="outline-4">
<h4 id="unnumbered-6">by Veronika and Miranda</h4>
<div class="outline-text-4" id="text-unnumbered-6">
<iframe height="800" width="80%" src="https://cdn.rawgit.com/stuycs-softdev/submissions/master/7/canvas/miranda-veronika/canvas.html">
</iframe>
</div>
</div>
</div>
</div>
<div id="outline-container-unnumbered-7" class="outline-2">
<h2 id="unnumbered-7">3D Depth Perception Pong</h2>
<div class="outline-text-2" id="text-unnumbered-7">
</div><div id="outline-container-unnumbered-8" class="outline-3">
<h3 id="unnumbered-8">Follow the ball and keep it in the well</h3>
<div class="outline-text-3" id="text-unnumbered-8">
</div><div id="outline-container-unnumbered-9" class="outline-4">
<h4 id="unnumbered-9">by Natan</h4>
<div class="outline-text-4" id="text-unnumbered-9">
<iframe height="800" width="80%" src="https://cdn.rawgit.com/stuycs-softdev/submissions/master/6/canvas/NZamansky/index.html">
</iframe>
</div>
</div>
</div>
</div>
<div id="outline-container-unnumbered-10" class="outline-2">
<h2 id="unnumbered-10">Can't really describe this but I love it</h2>
<div class="outline-text-2" id="text-unnumbered-10">
</div><div id="outline-container-unnumbered-11" class="outline-3">
<h3 id="unnumbered-11">Use WASD to move DW around</h3>
</div>
<div id="outline-container-unnumbered-12" class="outline-3">
<h3 id="unnumbered-12">by Fish</h3>
<div class="outline-text-3" id="text-unnumbered-12">
<iframe height="800" width="80%" src="https://cdn.rawgit.com/stuycs-softdev/submissions/master/6/canvas/fishy/dyrlandland.html">
</iframe>
</div>
</div>
</div>Kids these days -- they don't know nuttinhttp://cestlaz.github.io/posts/2015-01-15-kids-know-nuttin.html/2015-01-15T00:00:00-05:002015-01-15T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
Yesterday, I took part in a round table discussion on Ed Tech and Tech
Ed, the latter being more, as they say, my wheelhouse. Afterwards a
few of us were chatting and a friend observed that when she first
started to talk to high school kids she was shocked that they really
didn't know the local tech players - neither names nor companies.
</p>
<p>
A couple of years ago, another friend was helping me organize an event for
high schoolers. He started to go down a list of well known tech names
and was surprised when I told him that the kids wouldn't know them.
</p>
<p>
The first time I experienced this, it was just as big a surprised to
me. I was setting up a big high school event at Foursquare (<a href="http://cestlaz.github.io/2012/03/31/checking-in-with-family.html#.VLfzl9-c1CU">post here</a>)
and was shocked to learn that practically non of the attendees had
heard of the company.
</p>
<p>
This would never have been the case in the 90s or even the early
2000s. What happened?
</p>
<p>
I have a theory.
</p>
<p>
I don't think it's just due to the fact that CS is a hot subject
now. It was hot during the 90's bubble. I'm sure the fact that a wider
range of kids are being exposed to CS is part of this phenomenon but
I don't think it's the biggest reason.
</p>
<p>
I think CS kids back then knew more – more of the players, more of the
tools, more about the systems because they had to. In some ways, and I
know I'm vastly overstating things, it's "too easy" now.
</p>
<p>
Back in the day, if you wanted to put your thoughts on line you had
to:
</p>
<ul class="org-ul">
<li>learn html
</li>
<li>maybe some PHP, Perl, or Python
</li>
<li>You probably had to learn a bit about hosting a server
</li>
<li>you had to deal with registering a domain name
</li>
<li>and more
</li>
</ul>
<p>
Now, you just go to blogger or tumblr.
</p>
<p>
Back then, if you wanted to communicate, you had to learn how to learn
the dark art of <a href="http://en.wikipedia.org/wiki/Internet_Relay_Chat">irc</a>, now you have Google chat.
</p>
<p>
Back then, you want to share photos, you had to learn how to make a
gallery. Now, Facebook.
</p>
<p>
And of course the list goes on.
</p>
<p>
Even programming required that you know something about the filesystem
and the basics of working in an operating system. Now between IDEs
both local and cloud based, you can learn all about programming and
never actually create a stand alone program that operates outside of
the IDE sandbox.
</p>
<p>
Back in the day, if a kid was into CS they had to learn more than
just the in class toolset and this in turn forced them to be in touch
with the tech community both products and players.
</p>
<p>
I'm not saying the "good old days" were in fact that good and I love
most of the progress we've made. Just noting the cultural difference.
</p>
<p>
It means we should pay more attention to educating our classes on tech
culture, the good, the bad, and the ugly.
</p>Little details we take for grantedhttp://cestlaz.github.io/posts/2014-11-21-little-details.html/2014-11-21T00:00:00-05:002014-11-21T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div id="outline-container-unnumbered-1" class="outline-2">
<h2 id="unnumbered-1"></h2>
<div class="outline-text-2" id="text-unnumbered-1">
<p>
I'm getting ready for my AP classes this morning. We're building a
<a href="http://cestlaz.github.io/2011/12/03/wheres-waldo-text-style.html#.VG8qtt-c2Ak">word search generator</a> and we're at the point where we need to read a
list of words from a file
</p>
<p>
First, I'd better make sure I can do it. We're using the java
<b><b>scanner</b></b>, mostly because it's easy.
</p>
<p>
First cut:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #00ffff; font-weight: bold;">public</span> <span style="color: #00ffff; font-weight: bold;">class</span> <span style="color: #00ff00;">wl</span> {
<span style="color: #00ffff; font-weight: bold;">public</span> <span style="color: #00ffff; font-weight: bold;">static</span> <span style="color: #00ff00;">void</span> <span style="color: #0000ff; font-weight: bold;">main</span>(<span style="color: #00ff00;">String</span>[] <span style="color: #ffff00;">args</span>) {
<span style="color: #00ff00;">Scanner</span> <span style="color: #ffff00;">sc</span> = <span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">Scanner</span>(<span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">File</span>(<span style="color: #00ff00;">"words"</span>));
<span style="color: #00ffff; font-weight: bold;">while</span> (sc.hasNext()){
<span style="color: #00ff00;">String</span> <span style="color: #ffff00;">s</span> = sc.next();
System.out.println(s);
}
}
}
</pre>
</div>
<p>
Oh yes, I forgot the
</p>
<pre class="example">
import java.io.*;
import java.util.*;
</pre>
<p>
Oh, and also the fact that I've got deal with exceptions when working
with files:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #00ffff; font-weight: bold;">try</span> {
<span style="color: #00ff00;">Scanner</span> <span style="color: #ffff00;">sc</span> = <span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">Scanner</span>(<span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">File</span>(<span style="color: #00ff00;">"words"</span>));
<span style="color: #00ffff; font-weight: bold;">while</span> (sc.hasNext()){
<span style="color: #00ff00;">String</span> <span style="color: #ffff00;">s</span> = sc.next();
System.out.println(s);
}
} <span style="color: #00ffff; font-weight: bold;">catch</span> (<span style="color: #00ff00;">Exception</span> <span style="color: #ffff00;">e</span>){
System.out.println(<span style="color: #00ff00;">"Can't open file."</span>);
System.exit(0);
}
</pre>
</div>
<p>
But we don't want to wrap our entire program in an exception:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #00ffff; font-weight: bold;">try</span> {
<span style="color: #00ff00;">Scanner</span> <span style="color: #ffff00;">sc</span> = <span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">Scanner</span>(<span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">File</span>(<span style="color: #00ff00;">"words"</span>));
} <span style="color: #00ffff; font-weight: bold;">catch</span> (<span style="color: #00ff00;">Exception</span> <span style="color: #ffff00;">e</span>){
System.out.println(<span style="color: #00ff00;">"Can't open file."</span>);
System.exit(0);
}
<span style="color: #00ffff; font-weight: bold;">while</span> (sc.hasNext()){
<span style="color: #00ff00;">String</span> <span style="color: #ffff00;">s</span> = sc.next();
System.out.println(s);
}
</pre>
</div>
<p>
Now it doesn't work because the <b><b>Scanner sc</b></b> might not exist after the
try catch block (if an exception occurred), so we need:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #00ff00;">Scanner</span> <span style="color: #ffff00;">sc</span>
<span style="color: #00ffff; font-weight: bold;">try</span> {
sc = <span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">Scanner</span>(<span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">File</span>(<span style="color: #00ff00;">"words"</span>));
} <span style="color: #00ffff; font-weight: bold;">catch</span> (<span style="color: #00ff00;">Exception</span> <span style="color: #ffff00;">e</span>){
System.out.println(<span style="color: #00ff00;">"Can't open file."</span>);
System.exit(0);
}
<span style="color: #00ffff; font-weight: bold;">while</span> (sc.hasNext()){
<span style="color: #00ff00;">String</span> <span style="color: #ffff00;">s</span> = sc.next();
System.out.println(s);
}
</pre>
</div>
<p>
And now this doesn't work because <b><b>sc</b></b> might not have a value so we
finally get to the working version:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #00ffff; font-weight: bold;">import</span> <span style="color: #ff00ff;">java</span>.<span style="color: #ff00ff;">io</span>.*;
<span style="color: #00ffff; font-weight: bold;">import</span> <span style="color: #ff00ff;">java</span>.<span style="color: #ff00ff;">util</span>.*;
<span style="color: #00ffff; font-weight: bold;">publ</span><span style="color: #00ff00;">ic c</span><span style="color: #00ffff; font-weight: bold;">lass</span> <span style="color: #00ff00;">wl</span> {
<span style="color: #00ffff; font-weight: bold;">public</span> <span style="color: #00ffff; font-weight: bold;">static</span> <span style="color: #00ff00;">void</span> <span style="color: #0000ff; font-weight: bold;">main</span>(<span style="color: #00ff00;">String</span>[] <span style="color: #ffff00;">args</span>) {
<span style="color: #00ff00;">Scanner</span> <span style="color: #ffff00;">sc</span> = <span style="color: #ff00ff;">null</span>;
<span style="color: #00ffff; font-weight: bold;">try</span> {
sc = <span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">Scanner</span>(<span style="color: #00ffff; font-weight: bold;">new</span> <span style="color: #00ff00;">File</span>(<span style="color: #00ff00;">"words"</span>));
} <span style="color: #00ffff; font-weight: bold;">catch</span> (<span style="color: #00ff00;">Exception</span> <span style="color: #ffff00;">e</span>){
System.out.println(<span style="color: #00ff00;">"Can't open file."</span>);
System.exit(0);
}
<span style="color: #00ffff; font-weight: bold;">while</span> (sc.hasNext()){
<span style="color: #00ff00;">String</span> <span style="color: #ffff00;">s</span> = sc.next();
System.out.println(<span style="color: #00ff00;">s</span>);
}
}
}
</pre>
</div>
<p>
Really simple program but that's a long list of things that can go
wrong along the way. Nothing big, but each a stumbling block for a
beginning student that doesn't have the wealth of experience that
someone like me has.
</p>
<p>
I had an interesting discussion with one of my seniors the other day
on this subject - all the base knowledge that experienced programmers
have that students don't and how we have to approach teaching so that
students are supported and not frustrated by these little but
important speed-bumps that they'll hit along the way.
</p>
<p>
I hope to write more about this soon, but for now I'll leave you to
ponder the issue.
</p>
</div>
</div>Hidden Complexityhttp://cestlaz.github.io/posts/2014-11-17-hidden-complexity.html/2014-11-17T00:00:00-05:002014-11-17T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
I've said it many times:
</p>
<blockquote>
<p>
Never use a tool you couldn't write yourself.
</p>
</blockquote>
<p>
That is - make sure you understand what's going on under the hood.
</p>
<p>
In AP we've been playing with ArrayLists. The problem for today?
Create an ArrayList with consecutive integers and then write a routine
that will randomize the ArrayList.
</p>
<p>
For example, you might start with this ArrayList:
</p>
<pre class="example">
0,1,2,3,4,5
</pre>
<p>
and end up with
</p>
<pre class="example">
3,5,1,4,2,0
</pre>
<p>
First cut, the students grabbed a random element from the ArrayList,
removed it, and added it to the end of a new list. Then repeat until
the original list is empty and the new one is randomized. Then return
the list.
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #a020f0;">public</span> <span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #0000ff;">shuffle1</span>(<span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #a0522d;">l</span>){
<span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #a0522d;">result</span> = <span style="color: #a020f0;">new</span> <span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>>();
<span style="color: #a020f0;">while</span> (l.size()>0){
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">i</span> = rnd.nextInt(l.size());
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">v</span> = l.remove(i);
result.add(v);
}
<span style="color: #a020f0;">return</span> result;
}
</pre>
</div>
<p>
Looks good.
</p>
<p>
Version two was much the same but after it removed a random value, it
added it to the end of the same ArrayList:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #a020f0;">public</span> <span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #0000ff;">shuffle2</span>(<span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #a0522d;">l</span>){
<span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #a0522d;">result</span> = <span style="color: #a020f0;">new</span> <span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>>();
<span style="color: #a020f0;">for</span> (<span style="color: #228b22;">int</span> <span style="color: #a0522d;">s</span>=l.size();s>0;s--) {
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">i</span> = rnd.nextInt(s);
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">v</span> = l.remove(i);
l.add(v);
}
<span style="color: #a020f0;">return</span> l;
}
</pre>
</div>
<p>
Then it was time to time. Both seemed pretty quick but as our data set
grew things seemed strange:
</p>
<div class="row">
<div class="c4">
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<colgroup>
<col class="left">
<col class="left">
</colgroup>
<thead>
<tr>
<th scope="col" class="left">Size</th>
<th scope="col" class="left">Time</th>
</tr>
</thead>
<tbody>
<tr>
<td class="left">100,000</td>
<td class="left">2 seconds</td>
</tr>
<tr>
<td class="left">200,000</td>
<td class="left">7 seconds</td>
</tr>
<tr>
<td class="left">400,000</td>
<td class="left">26 seonds</td>
</tr>
</tbody>
</table>
</div></div>
<p>
We're just looping through an ArrayList, what's going on? When we
double the size of the list, it should just take double the time.
</p>
<p>
Since the class already wrote their own ArrayList implementation, they
were quick to realize that every time we removed an item from the
original Array, we were doing a linear or O(n) operation. That means
our algorithms, which look linear, are in fact O(N<sup>2</sup>).
</p>
<p>
Can we do better? You bet. They just changed the remove and add to
using get and set. Instead off removing an item and re-inserting it,
just swap the randomly selected item with the last element:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #a020f0;">public</span> <span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #0000ff;">shuffle3</span>(<span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #a0522d;">l</span>){
<span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>> <span style="color: #a0522d;">result</span> = <span style="color: #a020f0;">new</span> <span style="color: #228b22;">ArrayList</span><<span style="color: #228b22;">Integer</span>>();
<span style="color: #a020f0;">for</span> (<span style="color: #228b22;">int</span> <span style="color: #a0522d;">s</span>=l.size();s>0;s--) {
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">i</span> = rnd.nextInt(s);
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">tmp</span> = l.get(i);
l.set(i, l.get(s-1));
l.set(s-1,tmp);
}
<span style="color: #a020f0;">return</span> l;
}
</pre>
</div>
<p>
No removes so no hidden linear component.
</p>
<p>
The run time?
</p>
<div class="row">
<div class="c4">
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<colgroup>
<col class="left">
<col class="left">
</colgroup>
<thead>
<tr>
<th scope="col" class="left">Size</th>
<th scope="col" class="left">Time</th>
</tr>
</thead>
<tbody>
<tr>
<td class="left">100,000</td>
<td class="left">.15 seconds</td>
</tr>
<tr>
<td class="left">200,000</td>
<td class="left">.16 seconds</td>
</tr>
<tr>
<td class="left">400,000</td>
<td class="left">.17 seonds</td>
</tr>
</tbody>
</table>
</div></div>
<p>
In fact, it took data sets in the size of millions before we even
broke more than a couple of seconds.
</p>
<p>
The algorithm looks the same but understanding what goes on under the
hood can make a big difference.
</p>Forty minutes to the punch line or "we'll never look at functions the same way again""http://cestlaz.github.io/posts/2014-11-12-decorators.html/2014-11-12T00:00:00-05:002014-11-12T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div id="outline-container-unnumbered-1" class="outline-2">
<h2 id="unnumbered-1"></h2>
<div class="outline-text-2" id="text-unnumbered-1">
<p>
How many times do we teach something and leave the kids thinking:
</p>
<p>
"what's the point of this?" "When will I use this?" or even just the
plain old fashioned "that's weird."
</p>
<p>
It's pretty cool when a lesson starts out that way but you get to the
payoff by the end of the class.
</p>
<p>
Today we started exploring some advanced python.
</p>
<p>
We started by showing that you can assign functions to variables or
pass them as parameters:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a020f0;">def</span> <span style="color: #0000ff;">inc</span>(x):
<span style="color: #a020f0;">return</span> x+1
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">dec</span>(x):
<span style="color: #a020f0;">return</span> x-1
<span style="color: #a0522d;">f</span> = inc
<span style="color: #a020f0;">print</span> f(5)
<span style="color: #a0522d;">flist</span> = [inc,dec]
<span style="color: #a020f0;">print</span> flist[1](5)
</pre>
</div>
<p>
We then looked at closures in python:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a020f0;">def</span> <span style="color: #0000ff;">makeAdder</span>(n):
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">inner</span>(x):
<span style="color: #a020f0;">return</span> x+n
<span style="color: #a020f0;">return</span> inner
<span style="color: #a0522d;">add3</span> = makeAdder(3)
<span style="color: #a0522d;">add5</span> = makeAdder(5)
<span style="color: #a020f0;">print</span> add3(10)
<span style="color: #a020f0;">print</span> add5(10)
</pre>
</div>
<p>
The idea that we can make a function that builds and returns a
function. When we call <b><b>makeAdder(3)</b></b>, the 3 is passed as parameter
n so the inner function reduces to <b><b>return x+3</b></b> and then we return
that inner function. When we later run it: add3(10) it adds
10+3. makeAdder(5) works similarly but passing a 5 in for n instead
of a 3.
</p>
<p>
Even a somewhat clunky way of doing class type abstractions:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a020f0;">def</span> <span style="color: #0000ff;">make_counter</span>():
<span style="color: #b22222;"># </span><span style="color: #b22222;">private "instance" data</span>
<span style="color: #b22222;"># </span><span style="color: #b22222;">has to be a list due to weird python scoping rules</span>
<span style="color: #a0522d;">count</span> = [0]
<span style="color: #b22222;"># </span><span style="color: #b22222;">public methods</span>
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">inc</span>():
<span style="color: #a0522d;">count</span>[0]=count[0]+1
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">dec</span>():
<span style="color: #a0522d;">count</span>[0]=count[0]-1
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">reset</span>():
<span style="color: #a0522d;">count</span>[0]=0
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">get</span>():
<span style="color: #a020f0;">return</span> count[0]
<span style="color: #b22222;"># </span><span style="color: #b22222;">send back a dictionary so we have access to all the methods</span>
<span style="color: #a020f0;">return</span> {<span style="color: #8b2252;">'inc'</span>: inc, <span style="color: #8b2252;">'dec'</span>: dec, <span style="color: #8b2252;">'reset'</span>: reset, <span style="color: #8b2252;">'get'</span>: get}
<span style="color: #a0522d;">c1</span> = make_counter()
<span style="color: #a0522d;">c2</span> = make_counter()
<span style="color: #b22222;"># </span><span style="color: #b22222;">we've got to use the clunky list notation </span>
c1[<span style="color: #8b2252;">'inc'</span>]()
c1[<span style="color: #8b2252;">'inc'</span>]()
c1[<span style="color: #8b2252;">'inc'</span>]()
<span style="color: #a020f0;">print</span> c1[<span style="color: #8b2252;">'get'</span>]()
c2[<span style="color: #8b2252;">'inc'</span>]()
<span style="color: #a020f0;">print</span> c2[<span style="color: #8b2252;">'get'</span>]()
c1[<span style="color: #8b2252;">'reset'</span>]()
<span style="color: #a020f0;">print</span> c1[<span style="color: #8b2252;">'get'</span>]()
</pre>
</div>
<p>
Up to now the students are able to see how this works but the why is
unclear.
</p>
<p>
So now we'll look at where this is useful.
</p>
<p>
Let's suppose we have routines like the following. It returns a
string:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a020f0;">import</span> random
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">get_name</span>():
<span style="color: #a0522d;">names</span> = [<span style="color: #8b2252;">'tom'</span>,<span style="color: #8b2252;">'sue'</span>,<span style="color: #8b2252;">'harry'</span>,<span style="color: #8b2252;">'lisa'</span>,<span style="color: #8b2252;">'sarah'</span>,<span style="color: #8b2252;">'horatio'</span>]
<span style="color: #a020f0;">return</span> random.choice(names)
</pre>
</div>
<p>
get<sub>name</sub> and routines like it might be scattered throughout our
code. Let's suppose, for some strange reason, we want to double the
name every time we use it. A "traditional" way of doing this might be:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a020f0;">def</span> <span style="color: #0000ff;">dble</span>(f):
<span style="color: #a0522d;">name</span> = f()
<span style="color: #a020f0;">return</span> name+name
<span style="color: #a020f0;">print</span> dble(get_name) <span style="color: #b22222;"># </span><span style="color: #b22222;">returns something like tomtom</span>
</pre>
</div>
<p>
Here, we pass a function which returns a string and then dble returns
that string repeated twice. The problem here is that if we've got
get<sub>name</sub> all over our code base, we have to find it and change each
instance to <b><b>dble(get<sub>name</sub>)</b></b>
</p>
<p>
What if we write it as a function that returns a function:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a020f0;">def</span> <span style="color: #0000ff;">doubler</span>(f):
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">inner</span>():
<span style="color: #a0522d;">name</span>=f()
<span style="color: #a020f0;">return</span> name+name
<span style="color: #a020f0;">return</span> inner
</pre>
</div>
<p>
Now, in this case, we can do something like:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #b22222;"># </span><span style="color: #b22222;">make a new function that wraps get_name in "inner"</span>
<span style="color: #b22222;"># </span><span style="color: #b22222;">when we call inner, it returns the string twice</span>
<span style="color: #a0522d;">f</span> = doubler(get_name)
<span style="color: #b22222;"># </span><span style="color: #b22222;">and then later</span>
<span style="color: #a020f0;">print</span> f() <span style="color: #b22222;"># </span><span style="color: #b22222;">will print something like tomtom</span>
</pre>
</div>
<p>
The cool part is that we can also do this:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a0522d;">get_name</span> = double(get_name)
</pre>
</div>
<p>
And then whenever we call our new <b><b>get<sub>name</sub></b></b> we end up calling the
wrapped function.
</p>
<p>
This was the first A-ha. We don't have to change get<sub>name</sub> all over our
code base - we only have to change it once.
</p>
<p>
Once we write a function like doubler, instead of re-assigning
get<sub>name</sub> as we did above, we can do the following:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #228b22;">@doubler</span>
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">get_name</span>():
<span style="color: #b22222;"># </span><span style="color: #b22222;">rest of code as defined above</span>
<span style="color: #228b22;">@doubler</span>():
<span style="color: #a020f0;">def</span> <span style="color: #0000ff;">demo</span>():
<span style="color: #a020f0;">return</span> <span style="color: #8b2252;">"hello"</span>
</pre>
</div>
<p>
The second example will have demo return "hellohello" whenever we
invoke it.
</p>
<p>
A Python decorator is merely shorthand for calling a wrapper type
function like doubler.
</p>
<p>
This was the second A-ha moment – we can write functions that
transform functions.
</p>
<p>
We'll cover more decorator and closure plumbing tomorrow and then
start doing some fun stuff with these concepts.
</p>
</div>
</div>Using easy assignments to introduce deep conceptshttp://cestlaz.github.io/posts/2014-10-05-easy-assignments.html/2014-10-05T00:00:00-04:002014-10-05T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
In this early part of the semester, the students don't know all that
much. We haven't covered that many language constructs let along
algorithms, development techniques and all that other good stuff.
</p>
<p>
In terms of the "Java" part of APCS we've talked about basic types,
Strings, basic classes, loops and conditionals. We're limited in the
tools we have but we can still get the classes thinking in the right
way.
</p>
<p>
Last week, when we introduced loops we spent some time drawing shapes.
</p>
<p>
Starting with things like
</p>
Rectangle:
<pre>
*****
*****
*****
</pre>
<p>
and
</p>
Triangle1
<pre>
*
**
***
****
*****
</pre>
<p>
Simple nested loop stuff.
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">String</span> <span style="color: #a0522d;">s</span> = <span style="color: #8b2252;">""</span>;
<span style="color: #a020f0;">for</span> (<span style="color: #228b22;">int</span> <span style="color: #a0522d;">r</span> = 0; r < <span style="color: #228b22;">height</span>; r++) {
<span style="color: #a020f0;">for</span> (<span style="color: #228b22;">int</span> <span style="color: #a0522d;">c</span>=0; c<=r; c++ ){
s=s+<span style="color: #8b2252;">"*"</span>;<span style="color: #ff0000; font-weight: bold;">"</span>
<span style="color: #8b2252;"> }</span>
<span style="color: #8b2252;"> s=s+"</span>\n<span style="color: #ff0000; font-weight: bold;">"</span><span style="color: #8b2252;">;</span>
<span style="color: #8b2252;">}</span>
<span style="color: #8b2252;">return s;</span>
</pre>
</div>
<p>
Things get interesting when we looked at the next one:
</p>
Triangle2:
<pre>
*
**
***
****
*****
</pre>
<p>
It seems like a simple little problem with a simple solution:
</p>
<p>
What I love about it is that you can look at it in a couple of
interesting ways.
</p>
<p>
First, you can look at those spaces as a triangle in and of
themselves (replaced with # below):
</p>
<pre>
####*
###**
##***
#****
*****
</pre>
<p>
Well, that's almost the same as the Triangle1 from above. Also, if you
take away that triangle of spaces, you're pretty much left with
Triangle1.
</p>
<p>
The structure of the code can look something like:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">String</span> <span style="color: #a0522d;">s</span>=<span style="color: #8b2252;">""</span>;
<span style="color: #a020f0;">for</span> (<span style="color: #228b22;">int</span> <span style="color: #a0522d;">r</span> = 0; r < <span style="color: #228b22;">height</span>; r++){
<span style="color: #b22222;">// </span><span style="color: #b22222;">loop over the number of spaces we need for this line</span>
<span style="color: #b22222;">// </span><span style="color: #b22222;">loop over the number of stars we need for this line</span>
s=s+<span style="color: #8b2252;">"\n"</span>;
}
<span style="color: #a020f0;">return</span> s;
</pre>
</div>
<p>
We can also look at the problem just as a series of lines. How many
spaces and how many stars:
</p>
<p>
Let's say height = 5
</p>
<div class="org-src-container">
<pre class="src src-org"><span style="color: #0000ff;">| row | spaces | stars |</span>
<span style="color: #0000ff;">|</span></pre></div>Wait, I know that!!!!http://cestlaz.github.io/posts/2014-09-23-I-know-that.html/2014-09-23T00:00:00-04:002014-09-23T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
If I'm doing my job right, by the time my kids graduate they can learn
on their own.
</p>
<p>
It's like when two years ago, before starting her summer internship,
Batya listed all the tools and technologies she had to work with. When
I pointed out that she hadn't ever used any of them before and asked
how she was going to deal with it, she replied "I'll figure it out."
And she did.
</p>
<p>
At the end of the summer, Dina told a similar story about her
internship and how she knew she'd figure everything out because of the
solid background she got by going through StuyCS.
</p>
<p>
I loved both these stories.
</p>
<p>
But getting the kids there takes time.
</p>
<p>
Yesterday, in my AP classes, I assigned three <i>codingbat</i> problems. I
decided to go objects first this time round so we haven't done any
language constructs. The problems were simple String manipulations but
I added one that needed conditionals.
</p>
<p>
Today we went over them. Most of the class solved the assignment and
most had either no trouble or had to do just a little work.
</p>
<p>
I asked what about that last problem might have caused some
difficulty.
</p>
<p>
They couldn't figure it out, it seemed pretty straighforward. After a
number of guesses, one student said:
</p>
<p>
"Wait, we don't know ifs"
</p>
<p>
That was it. They didn't realize that they had taught themselves
something new.
</p>
<p>
This, of course, doesn't just happen.
</p>
<p>
They've seen conditionals in all sorts of guises.
</p>
<p>
Scheme:
</p>
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #a020f0;">if</span> boolean_expression
True_part
False_part)
</pre>
</div>
<p>
NetLogo:
</p>
<pre class="example">
if boolean [True part]
and
ifelse boolean [True part][ False part]
</pre>
<p>
and Python:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #a020f0;">if</span> <span style="color: #483d8b;">bool</span>:
s1
<span style="color: #a020f0;">elif</span> bool2:
s2
<span style="color: #a020f0;">else</span>:
s3
</pre>
</div>
<p>
and so on.
</p>
<p>
So they new the concept, from there it was just details.
</p>
<p>
Some said they just wrote it and it worked. Some said they looked up
sample code. Most didn't think they were doing anything new.
</p>
<p>
It was pretty awesome.
</p>
<p>
It's still a long road before they graduate, but we're getting there.
</p>Building a SHIP - Outreachhttp://cestlaz.github.io/posts/2014-07-20-ship-outreach.html/2014-07-20T00:00:00-04:002014-07-20T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div id="outline-container-sec-1" class="outline-2">
<h2 id="sec-1"></h2>
<div class="outline-text-2" id="text-1">
<p>
We've got a few more topics to cover in the <b><b>Building a SHIP</b></b>
series. We still have to cover:
</p>
<ul class="org-ul">
<li>The Crew
</li>
<li>Curricular Choices
</li>
<li>The long term plan
</li>
<li>Site and funding
</li>
</ul>
</div>
</div>
<div id="outline-container-sec-2" class="outline-2">
<h2 id="sec-2"></h2>
<div class="outline-text-2" id="text-2">
<p>
But for today, we'll talk outreach.
</p>
</div>
</div>
<div id="outline-container-sec-3" class="outline-2">
<h2 id="sec-3"></h2>
<div class="outline-text-2" id="text-3">
<p>
Outreach proved to be particular challenge for SHIP. Our entire crew
is made up of teachers. That meant that we couldn't communicate with
schools during business hours. That made things particularly tough. I
could send emails after hours or set up emails to be sent at specific
times during the day, but we couldn't call while at our day jobs. As a
result, this led to a vary long communication loop and we could never
be sure that information about SHIP was getting to the right people.
</p>
<p>
We did have a small number of non-teacher volunteers and they were
invaluable but they had limited knowledge from the teaching side.
</p>
<p>
So, we had the volunteers try to call schools during the day and we
followed up by emailing a flyer and link to a web site. We tried to
emphasize that we needed help from the schools in finding the right
students – that is students who might not have even considered
something like SHIP but where we could potentially turn them on to
something new.
</p>
<p>
In spite of this, we did get over 200 applicants for our 48 slots. I
have no idea how this compares to similar programs.
</p>
</div>
</div>
<div id="outline-container-sec-4" class="outline-2">
<h2 id="sec-4"></h2>
<div class="outline-text-2" id="text-4">
<p>
There were many terrific applications, but there were some head
scratching situations. There were some incomplete applications which I
attribute to students who weren't really interested in the program,
but I was surprised by two things on the student side.
</p>
<p>
First, sme times we needed a little more information from a student so we
sent an email to the addresses (primary and backup) that they listed
in the application. Some times students got right back to us. Other
times it took days or even weeks. In one case, we weren't able to
accept the student because he didn't get back to us until after the
selection process was over. I know that not everyone reads or responds
to emails promptly but I was surprised since these were cases of
students who wanted to partake in our program.
</p>
<p>
Another thing that surprised me is that we almost lost a couple of
students because they thought the program would cost too much. We
tried to make it as clear as possible that we offered financial
assistance and in many cases could cover all fees but apparently we
weren't as clear as I had hoped.
</p>
</div>
</div>
<div id="outline-container-sec-5" class="outline-2">
<h2 id="sec-5"></h2>
<div class="outline-text-2" id="text-5">
<p>
The one <b><b>really big</b></b> shock to me involved
recommendations. We required our applicants provide one email
address for someone that agreed to write a recommendation letter and
allowed for a second, optional one. We then contacted these
recomenders. If we didn't hear back, we sent reminder emails and asked
the applicants to prod the recommenders as well.
</p>
<p>
We had a return rate of about 10%. This cut across type of school
(public, private, parochial, and charter) and grade (rising 9 through
12). As a teacher myself, I know of some colleagues who don't actually
write recs they agree to write but I was shocked that we only heard
back from 10%. The end result was that we could use a recommendation
to help an applicant but we didn't feel that it was fair to penalize a
student just because a teacher didn't send in a rec.
</p>
</div>
</div>
<div id="outline-container-sec-6" class="outline-2">
<h2 id="sec-6"></h2>
<div class="outline-text-2" id="text-6">
<p>
As a final though on outreach, it should get easier for us over
time. SHIP is going great and next year, we'll be a known quantity to
schools. We should also have our cadre of shipmates helping spread the
word and of course, we want them back for another summer of more
advanced work.
</p>
</div>
</div>Twitch Codinghttp://cestlaz.github.io/posts/2014-04-10-twitch-coding.html/2014-04-10T00:00:00-04:002014-04-10T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
We have the kids write programs in all sorts of ways
</p>
<ul class="org-ul">
<li>on paper
</li>
<li>solo
</li>
<li>informally in pairs
</li>
<li>"pair programming"
</li>
<li>We have them trade code, pick up each others projects, and more.
</li>
</ul>
<p>
We do lots of different things to engage the kids in a lot of
different ways and I love it when someone comes up with a new
technique.
</p>
<p>
My friend, colleague, and incidentally, former student, Sam had such
an idea the other day. Sam started his teaching career at Francis
Lewis High School and it took us a while to convince him to join the
team, but he's been with us for about three years now and he's terrific.
</p>
<p>
Sam's also our resident gamer so I guess I shouldn't have been
surprised when Sam said he was going to do <a href="http://www.reddit.com/r/twitchplayspokemon/comments/1y94r8/the_history_of_twitch_plays_pokemon/">Twitch Pokemon</a> coding with
his classes. It sounded great.
</p>
<p>
In Twitch Pokemen, users type moves into a chat window and a bot reads
the commands to control a Pokemon. Sam's idea was to apply it to a CS class.
</p>
<p>
I loved the idea so I tried it in my classes.
</p>
<p>
First cut, I did it with stacks. We had a basic design in mind and then we started the "Twitch Coding."
</p>
<p>
We went up and down the rows. When it was a students turn, they could
either add a word, line, or concept, delete one, or change one.
</p>
<p>
So, for example, if the state of the code was:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #F0DFAF; font-weight: bold;">public</span> <span style="color: #7CB8BB;">Node</span> <span style="color: #DFAF8F;">top</span>;
<span style="color: #F0DFAF; font-weight: bold;">public</span> <span style="color: #7CB8BB;">void</span> <span style="color: #93E0E3;">push</span>(<span style="color: #7CB8BB;">String</span> <span style="color: #DFAF8F;">s</span>) {
<span style="color: #7CB8BB;">Node</span> <span style="color: #DFAF8F;">n</span> = <span style="color: #F0DFAF; font-weight: bold;">new</span> <span style="color: #7CB8BB;">Node</span>(s);
}
</pre>
</div>
<p>
a student could:
</p>
<ul class="org-ul">
<li>add n.setNext(top) to the push routine
</li>
<li>change public to private in the declaration of top
</li>
</ul>
<p>
Or the somewhat lame
</p>
<ul class="org-ul">
<li>add a // above the push declaration line
</li>
</ul>
<p>
or something else.
</p>
<p>
If a student gets stuck, it's up to the class to "go Price is Right"
on them and give suggestions.
</p>
<p>
It worked great in one class, forced in another, and somewhere in the
middle in the third. Overall, I was happy with the results.
</p>
<p>
We tried it again today as we implemented a queue.
</p>
<p>
This time, we prepped a little better and the results were better.
</p>
<p>
The idea needs some fine tuning, but I think it's a fun and different
way to engage the class and I think we'll be playing with twitch
coding some more in the coming months.
</p>Sorting - Subtle Errorshttp://cestlaz.github.io/posts/2014-03-17-subtle-errors-sorting.html/2014-03-17T00:00:00-04:002014-03-17T00:00:00-04:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<p>
Time to wrap up sorting for a while. We just finished quicksort
having gone through a series of lessons
</p>
<ul class="org-ul">
<li>We started with <a href="http://cestlaz.github.io/2014/03/12/select-to-sort.html#.UyJRTh_G8RM">Quickselect</a>.
</li>
<li>Then we did a quicksort, copying to new arrays during the partition
</li>
<li>Then finally to an in place quicksort.
</li>
</ul>
<p>
For the final quicksort we used a partition algorithm pretty much the
same as the one described <a href="http://en.wikipedia.org/wiki/Quicksort">here.</a>
</p>
<p>
We started testing using by building a randomly filled array like this:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #7CB8BB;">Random</span> <span style="color: #DFAF8F;">rnd</span> = <span style="color: #F0DFAF; font-weight: bold;">new</span> <span style="color: #7CB8BB;">Random</span>();
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">a</span>[] = <span style="color: #F0DFAF; font-weight: bold;">new</span> <span style="color: #7CB8BB;">int</span>[n];
<span style="color: #F0DFAF; font-weight: bold;">for</span> (<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">i</span>=0;i<<span style="color: #7CB8BB;">n</span>;i++) {
a[i] = rnd.nextInt(100);
}
qsort(a);
</pre>
</div>
<p>
And everything seemed terrific.
</p>
<p>
Just like when we did the mergesort, we started to increase n. First
20, then 100, then 1000 and so on.
</p>
<p>
All of a sudden, we started getting a stack overflow. We only made it
to about 450,000. Mergesort got to arrays of about 40,000,000 items
before we started to have memory problems.
</p>
<p>
Our algorithm was sound. It worked on everything up to about
450,000. Since Mergesort worked well into the tens of millions, quicksort
should have as well.
</p>
<p>
What was wrong?
</p>
<p>
We changed the code a bit:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #7CB8BB;">Random</span> <span style="color: #DFAF8F;">rnd</span> = <span style="color: #F0DFAF; font-weight: bold;">new</span> <span style="color: #7CB8BB;">Random</span>();
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">a</span>[] = <span style="color: #F0DFAF; font-weight: bold;">new</span> <span style="color: #7CB8BB;">int</span>[n];
<span style="color: #F0DFAF; font-weight: bold;">for</span> (<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">i</span>=0;i<<span style="color: #7CB8BB;">n</span>;i++) {
a[i] = rnd.nextInt(10000);
}
qsort(a);
</pre>
</div>
<p>
Instead of an array of 450,000 values between 0 and 100, our elements
now went fro 0 to 10,000.
</p>
<p>
All of a sudden things were good.
</p>
<p>
Why? It wasn't long before the student saw that 500,000 elements with
values between 0 and 100 meant lots of duplicates. Our partition
didn't account for that. If we had duplicate pivots, only one is moved
into place, the rest are left unsorted taking us closer to worst case
performance and blowing our stack.
</p>
<p>
Fortunately there was an easy fix:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #F0DFAF; font-weight: bold;">public</span> <span style="color: #7CB8BB;">int</span> <span style="color: #93E0E3;">partition</span>(<span style="color: #7CB8BB;">int</span>[] <span style="color: #DFAF8F;">a</span>, <span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">l</span>, <span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">r</span>) {
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">tmp</span>;
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">pivotIndex</span> = l+rnd.nextInt(r-l);
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">pivot</span> = a[pivotIndex];
tmp = a[r];
a[r] = a[pivotIndex];
a[pivotIndex]=tmp;
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">wall</span>=l;
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">pcount</span>=1;
<span style="color: #F0DFAF; font-weight: bold;">for</span> (<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">i</span>=l;i<<span style="color: #7CB8BB;">r</span>;i++) {
<span style="color: #F0DFAF; font-weight: bold;">if</span> (a[i]<pivot) {
tmp = a[i];
a[i]=a[wall];
a[wall]=tmp;
wall++;
}
<span style="color: #F0DFAF; font-weight: bold;">if</span> (a[i]==pivot)
pcount++;
}
<span style="color: #5F7F5F;">// </span><span style="color: #7F9F7F;">now copy over all the pivots</span>
<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">rwall</span>=wall;
tmp = a[rwall];
a[wall]=a[r];
a[r]=tmp;
rwall++;
<span style="color: #F0DFAF; font-weight: bold;">for</span> (<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">i</span>=rwall+1;i<=r;i++) {
<span style="color: #F0DFAF; font-weight: bold;">if</span> (a[i]==pivot) {
tmp = a[rwall];
a[rwall]=a[i];
a[i]=tmp;
rwall++;
}
}
<span style="color: #F0DFAF; font-weight: bold;">return</span> (wall+rwall)/2;
}
</pre>
</div>
<p>
When we partition the array, move all the elements equal to the
partition to the middle of the array.
</p>
<p>
That did the trick.
</p>
<p>
All of a sudden we were blazing through data sets upwards of
100,000,000 elements.
</p>
<p>
We're done for sorting for a while, at least until the heapsort but
it's been a fun couple of weeks
</p>From selection to sortinghttp://cestlaz.github.io/posts/2014-03-12-select-to-sort.html/2014-03-12T00:00:00-04:002014-03-12T00:00:00-04:00Mike Zamansky<script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js"></script>
<script type="text/javascript" src="http://cestlaz.github.io/posts/2014-03-12-select-to-sort.html/assets/static/mj.js"></script>
<style>
div.center {text-align:center;}
</style>
<p>
When I first saw the <a href="http://en.wikipedia.org/wiki/Quicksort">quicksort</a> it was in an algorithms class back in
the day. We first learned the quicksort, then choosing a good pivot
element and then as an afterthought we did <a href="http://en.wikipedia.org/wiki/Quickselect">quickselect</a>.
</p>
<p>
Fast forward to teaching. I was never really happy teaching
quicksort. Mergesort is easy to motivate and it's pretty easy to
write. Quicksort always felt a little forced.
</p>
<p>
I thought I'd try switching things up this time and doing quickselect
first.
</p>
<p>
The motivating problem: find the K<sup>th</sup> smallest item in a list - in our
case the list is an array of ints.
</p>
<p>
I want to start with the least efficient algorithm so I stack the
deck. I remind them that we've been finding the smallest item in a
list for two years now.
</p>
<p>
They don't disappoint and suggest something like this:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #DFAF8F;">L</span> = [10,3,28,82,14,42,66,74,81]
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #93E0E3;">findKth</span>(L,k):
<span style="color: #DFAF8F;">omits</span>=[]
<span style="color: #F0DFAF; font-weight: bold;">for</span> i <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #DCDCCC; font-weight: bold;">range</span>(k):
<span style="color: #DFAF8F;">ans</span>=<span style="color: #DCDCCC; font-weight: bold;">max</span>(L)
<span style="color: #F0DFAF; font-weight: bold;">for</span> item <span style="color: #F0DFAF; font-weight: bold;">in</span> L:
<span style="color: #F0DFAF; font-weight: bold;">if</span> item < ans <span style="color: #F0DFAF; font-weight: bold;">and</span> item <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #F0DFAF; font-weight: bold;">in</span> omits:
<span style="color: #DFAF8F;">ans</span>=item
omits.append(ans)
<span style="color: #F0DFAF; font-weight: bold;">return</span> ans
<span style="color: #F0DFAF; font-weight: bold;">print</span> findKth(L,3)
</pre>
</div>
<p>
Clearly an \(O(n^2)\) algorithm.
</p>
<p>
Can we do better?
</p>
<p>
Certainly.
</p>
<p>
The students then suggest sorting the data set first. If we use
mergesort, we can sort in \(O(nLg (n))\) time. This lead to a great
conversation about sorting being so fast it's practically free and
that you don't have to hard code everything from scratch. Not only is
sorting the data set then plucking the k<sup>th</sup> item out much faster, if
you already have a sort written or if you use your language's
library's sort, it's much easier as well:
</p>
<div class="org-src-container">
<pre class="src src-python"><span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #93E0E3;">findKth</span>(L,k):
<span style="color: #DFAF8F;">tmp</span> = <span style="color: #DCDCCC; font-weight: bold;">sorted</span>(L)
<span style="color: #F0DFAF; font-weight: bold;">return</span> tmp[k]
</pre>
</div>
<p>
But we can do even better. So now we talk about <b>quickselect</b>
</p>
<p>
We pick a random pivot, partition the list a la quicksort (reorder the
list such that all items less than the pivot are to its left, and all
items greater than the pivot are to its right).
</p>
<p>
We now know that after partitioning. the pivot is in it's exact
location. If its index is <b>k</b> then we're done. If not, we can
recursively <b>quickselect</b> on either the left or right side.
</p>
<p>
Pretty cool, but is it faster?
</p>
<p>
It's easy to see that if we keep choosing a bad pivot (the smallest or
largest in the list), each iteration takes \(n\) time to partition and
each iteration takes one item out of contention. This takes us back to
\(O(n^2)\).
</p>
<p>
However…
</p>
<p>
If we choose a good partition – at the middle of the list, each
partition takes less and less time. We get a run time of:
</p>
<p>
\(n+\frac{n}{2} +\frac{n}{4}+\frac{n}{8}+\dots\) and since \(\frac{n}{2}
+\frac{n}{4}+\frac{n}{8}\dots=n\) this becomes an \(O(2n)\), or \(O(n)\) algorithm.
</p>
<p>
That's really cool.
</p>
<p>
Homework was the actual implementation.
</p>
<p>
I think this might be a better way to approach quicksort. It seems
less forced, plus the class gets to go through the exercise of taking
an algorithm form \(O(n^2)\) to \(O(nlg(n))\) to \(O(n)\).
</p>
<p>
Next, moving to the quicksort and also showing that we can indeed
avoid those really bad pivots.
</p>
<h4>Addendum</h4>
We moved to quicksort today and overall I'm happy with this
approach. The only thing I think needs tweaking is going from the idea
of partitioning to Java code. Java makes it somewhat of a bear.
<br>Be the ballhttp://cestlaz.github.io/posts/2014-03-09-be-the-ball.html/2014-03-09T00:00:00-05:002014-03-09T00:00:00-05:00Mike Zamansky<style>
div.center {text-align:center;}
</style>
<div class="center"> <iframe width="560" height="315" src="//www.youtube.com/embed/sWH811TcckU" frameborder="0" allowfullscreen></iframe> </div>
<p>
Crystal Furman wrote a nice post titled <a href="http://teachingcomputerscience.weebly.com/1/post/2014/03/coding-comprehension.html">Coding Comprehension</a> about a
week ago. There was a little buzz about it in the APCS Facebook group
and shortly after, Alfred Thompson added his <a href="http://blog.acthompson.net/2014/03/when-knowing-syntax-is-not-enough.html">two cents.</a>
</p>
<p>
I thought I'd add mine, at least a couple of thoughts.
</p>
<p>
There are a lot of issues - long term retention, transfer of knowledge
from the basics to more advanced tools, pattern recognition, and more.
</p>
<p>
It reminded me of Benjamin Zander's talk "Playing on one Buttock":
</p>
<div class="center"> <iframe width="560" height="315" src="//www.youtube.com/embed/r9LCwI5iErE" frameborder="0" allowfullscreen></iframe> </div>
<p>
Check out the first five minutes.
</p>
<p>
Code reading is important, pair programming, where students are
constantly explaining to each other helps, and there are other
techniques.
</p>
<p>
We can also model thinking like a computer from day one.
</p>
<p>
Many of us start day one with exercises where students are the
computer. Perhaps using a simplified made up language or maybe by just
throwing some task at the kids and having them write instruction lists
for each other. That's a great start, but we can continue drawing the
relationship between the way we think and the way a computer works.
</p>
<p>
Take a simple intro problem – finding the largest value in a list of
numbers.
</p>
<p>
The ultimate solution in Java might be:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #F0DFAF; font-weight: bold;">public</span> <span style="color: #7CB8BB;">int</span> <span style="color: #93E0E3;">findMax</span>(<span style="color: #7CB8BB;">int</span>[] <span style="color: #DFAF8F;">L</span>){
maxIndex = 0;
<span style="color: #F0DFAF; font-weight: bold;">for</span> (<span style="color: #7CB8BB;">int</span> <span style="color: #DFAF8F;">i</span>=0;i<L.<span style="color: #7CB8BB;">length</span>;i++){
<span style="color: #F0DFAF; font-weight: bold;">if</span> (a[i]<a[maxIndex]){
maxIndex = i;
}
}
<span style="color: #F0DFAF; font-weight: bold;">return</span> maxIndex;
}
</pre>
</div>
<p>
Somewhere along the development process, I ask my students how they
would find the largest value in list. If the list was short, they
might just scan it. If the list was very long, they do the same thing
as our Java snippet does - remember the largest so far as we scan down
the list one by one. At first, we just think we're scanning the list,
but if we slow things down, we see that we're following pretty much
the same algorithm as what we'd write in code.
</p>
<p>
I use this technique throughout all my classes - slow ourselves down
and really analyze the steps towards solving the problem. No single
technique is going to teach our kids how to think about and comprehend
code, but it's another tool in our bag of tricks.
</p>
<h4>Side note</h4>
<p>
This is my first post written using <a href="http://www.emacswiki.org/emacs/">Emacs</a> <a href="http://orgmode.org/">Org mode</a>. I've been using it
for years but only now discovering how amazing a tool it is.
</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>Change the datahttp://cestlaz.github.io/posts/2014-02-26-change-the-data.md/2014-02-26T00:00:00-05:002014-02-26T00:00:00-05:00Mike Zamansky<div><blockquote>
<p>Patient: "Doctor, it hurts when I do this."</p>
<p>Doctor: "So, don't do that."</p>
</blockquote>
<p>We've been spending time on
<a href="http://en.wikipedia.org/wiki/State_space_search">State Space Search</a>. It's
a great topic. We deal with or at least introduce:</p>
<ul>
<li>Recursion</li>
<li>Blind search</li>
<li>Heuristic search</li>
<li>foreshadowing things like A* and Dijkstra's algorithm.</li>
</ul>
<p>and more. Today, however. I want to talk about something else.</p>
<p>We started by developing a maze solver. It reads a text file
representing the maze and then proceeds to find an exit. One version
of the source code can be found
<a href="https://github.com/stuycs-apcs-z/classcode/tree/master/3/maze">here</a>.</p>
<p>It's really cool to see how such a short program, about 10 lines of
work code, can solve such an open sounding problem. From there we talk
about state spaces, graphs, etc. We then moved on to the
<a href="https://github.com/stuycs-apcs-z/classcode/tree/master/3/maze">Knight's tour</a>. By
viewing it as a state space problem we can look at it just like the
maze.</p>
<p>We represented a state as a board with the knight's current position and where it's been. An easy way to do this is to use an array of ints. So we have an empty 5x5 board:</p>
<pre class="code literal-block"><span></span>0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
</pre>
<p>Or a board after a few moves:</p>
<pre class="code literal-block"><span></span>1 0 0 0 0
4 0 2 0 0
0 0 5 0 0
0 3 0 0 6
0 0 0 0 0
</pre>
<p>The kids saw three base cases:</p>
<ol>
<li>When our count got up to n^2 (and in fact, we're done)</li>
<li>When we land on a non-zero space (when we just return or backtrack)</li>
<li>When we try to move off the board, for an index out of bounds error.</li>
</ol>
<p>I wanted to look at that third one. We talked for a bit about using an
if or a try/catch but I pointed out that I didn't like either. Looking
at our maze code, we never checked bounds there. Why not. Well it
turns out that our maze had wall all around. It was stored in a 2D
array but the entire outer edge was wall. Why not do the same for the chess board:</p>
<pre class="code literal-block"><span></span>-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
</pre>
<p>Now, as long as we start on the board, if the Knight jumps off the
edge, it will end on a -1 square and backtrack. By modifying our data
structure and data to contain a border, we've eliminated the special
case of index out of bounds.</p>
<p>I always like doing that.</p>
<h5>Some Links</h5>
<p><a href="https://github.com/stuycs-apcs-z/classcode/tree/master/3/knights">Source code for Knight's tour</a></p></div>Fibonacci by the tailhttp://cestlaz.github.io/posts/2014-02-13-fibonacci.md/2014-02-13T00:00:00-05:002014-02-13T00:00:00-05:00Mike Zamansky<div><p>We're ramping up for recursion in my junior classes - state space
search, nlg(n) sorts, etc. As a refresher, we took a quick look at the
Fibonacci numbers.</p>
<p>Now, some people seem to think that it's a tired problem. It's mathy,
it's played out, it's boring etc.. They just might be missing the
point.</p>
<p>The beauty isn't in the problem itself, but rather, that it's a
platform on which you can look at many problem solving techniques.</p>
<p>We can look at the basic, straightforward , imperative solution:</p>
<blockquote>
<p _="%" endhighlight>{% highlight java %}
public int fib1(int n) {
int a=1,b=1;
for (int i=0;i<n;i++){
int c=a+b;
a=b;
b=c;
}
return a;
}</p>
</blockquote>
<p>It's straightforward and fast - no recursion needed.</p>
<p>Next, we can look at the basic recursive version:</p>
<blockquote>
<p _endhighlight_="%endhighlight%">{% highlight java %}
public int fib2(int n) {
if (n<=1)
return 1;
else
return fib2(n-1)+fib2(n-2);
}</p>
</blockquote>
<p>The advantages (of recursive solutions in general):</p>
<ul>
<li>It's a direct translation from the recursive mathematical formula.</li>
<li>It's elegant, clean, and concise.</li>
<li>It can make hard problems much easier (see: <a href="http://cestlaz.github.io/2010/01/10/towers-of-hanoi.html#.Uv1m4N_EvZ8">Towers, Hanoi</a>).</li>
<li>We can use same thought process that led to this solution to solve
problems like finding our way out of a maze.</li>
</ul>
<p>The downside:</p>
<ul>
<li>It can be VERY slow.</li>
</ul>
<p>So, how do we address this?</p>
<p>One way is via <strong>memoization</strong> - when we find a value, store it in a
table, then we can use the look up table instead of recalculating over
and over:</p>
<blockquote>
<p><code>java
public int[] fibnums = new int[100000];
public int fib3(int n) {
if (n<=1)
return 1;
else if (fibnums[n] != 0)
return fibnums[n];
else {
fibnums[n] fib3(n-1)+fib3(n-2);
return fibnums[n];
}
}</code></p>
</blockquote>
<p>This is a terrific thing to show a class since it's easy for students
to wrap their heads around, it really speeds things up, and it's a
precursor to lots of neat algorithms.</p>
<p>Finally, we can look at re-writing Fibonacci using tail
recursion. This one can be a little hard for students to grasp. I like
building it up from the iterative solution. In that solution, we use
<strong>a</strong>, and <strong>b</strong> to "walk down" the list of Fibonacci numbers. At any point in time, <strong>a</strong> and <strong>b</strong> represent where we are in the sequence. We also use <strong>c</strong> but that's really just a temporary place to add a and b together.</p>
<p>The problem with doing this in a recursive solution is that we can't
have <strong>a</strong> and <strong>b</strong> as local variables as each recursive call will
have new <strong>a</strong> and <strong>b</strong>s and no information will be transferred.</p>
<p>Since we're working in Java, it doesn't take long for some students to come up with the idea of using instance variables to store a and b and just use the recursion for the "loop.":</p>
<blockquote>
<p _="%" endhighlight>{% highlight java %}
public int a=1, b=1
public int fib4(int n) {
if (n==1)
return a;
else {
int c=a+b;
a=b;
b=c;
return fib4(n-1)
}
}</p>
</blockquote>
<p>Great, but using instance variables in this way is very inelegant and messy. Better, use extra parameters to store the values from call to call:</p>
<blockquote>
<p _="%" endhighlight>{% highlight java %}
public int fib5(int n,int a, int b) {
if (n==1)
return a;
else
return fib4(n-1,b,a+b)
}</p>
</blockquote>
<p>Looking at Fib5(5) we get for n, a, and b:</p>
<ul>
<li>5,1,1</li>
<li>4 1,2</li>
<li>3,2,3</li>
<li>2,3,5</li>
<li>1,5,8</li>
</ul>
<p>At which point we just return the 8</p>
<p>Clean, elegant, fast, and easy to understand.</p>
<p>Each of these four techniques are important and will be used time and time again and here we have one simple problem that allows us to explore them all.</p>
<h5>Some Links</h5>
<p><a href="http://maikolsolis.wordpress.com/2014/01/18/project-euler-problem-2-even-fibonacci-numbers/">Project Euler: Problem #2 - Even Fibonacci numbers</a></p>
<p><a href="http://java.dzone.com/articles/memoized-fibonacci-numbers">Memoized Fibonacci Numbers with Java 8</a></p>
<p><a href="http://mikesmathpage.wordpress.com/2014/02/07/the-quadratic-formula-and-fibonacci-numbers/">The quadratic formula and Fibonacci numbers</a></p>
<p><a href="http://blog.smartbear.com/programming/why-developers-%0Astill-need-the-basics/">Monte Carlo Simulations, Fibonacci Numbers, and Other Number Tests: Why Developers Still Need The Basics</a></p>
<p><a href="http://www.ted.com/talks/arthur_benjamin_the_magic_of_fibonacci_numbers.html">TED: Arthur Benjamin: The magic of Fibonacci numbers - Arthur Benjamin (2013)</a></p>
<p><a href="http://lee-phillips.org/lispmath/">Fibonacci Numbers in the Real World</a></p></div>Rot13 - Gateway <s>Drugs</s> Techniqueshttp://cestlaz.github.io/posts/2014-01-07-rot13-gateway.md/2014-01-07T00:00:00-05:002014-01-07T00:00:00-05:00Mike Zamansky<div><p>I've written before about <a href="http://cestlaz.github.io/2013/08/07/That_One_Inspirational_Curriculum.html#.UsyYlN_EvZ8">That One Inspirational Curriculum</a> -
the idea that it's not the topic in the syllabus but rather what the
teacher does with it.</p>
<p>Some times a simple problem can lead to some really neat concepts.</p>
<p>Take what we did in my AP classes over the past couple of days. </p>
<p>I wanted a nice little warm up after the break so we wrote a simple
<a href="http://www.rot-n.com/">rotation cipher</a>. We started with a little
encode routine - take a string and rotate the letters by some
offset. For example if we use an offset of 3, 'hello' becomes
'khoor' - each letter being shifted over thee places.</p>
<p>Pretty easy for the class but even a simple problem like this lets us
talk about a few things, including:</p>
<ul>
<li>we can exploit the ASCII ordering but have to remember to deal with
the offsets. That is in ASCII, an 'a' is 97, we can't just calculate c =
(c+offset)%26. We have to first shift the letter down to 0, add and
mod, and then shift back c = ((c-'a') +offset)%26 + 'a'</li>
<li>We can talk about neat Internet history such as how
(rot13)[http://en.wikipedia.org/wiki/ROT13] was used to hide
spoilers and offensive material on the internet.</li>
</ul>
<p>I then ran a program that broke the encryption. I also showed the
students how it didn't work on single words but did on full sentences.</p>
<p>By hand, decodingn even a simple cipher is a pain.</p>
<p>With computer assist, it's easy - just print out all 26 possible rotations and pull out the right one.</p>
<p>Our question was how do we have the computer do it all on its own?</p>
<p>I asked them to think about how they might write a program to
accomplish this -- and that's when the magic starts.</p>
<p>They came up with a few interesting ideas:</p>
<ol>
<li>For each of the 26 rotations, choose the one with the most vowels.</li>
<li>For each word in each rotation, give a point for each word with a vowel and choose the rotation with the highest score.</li>
<li>Look for common short words in each rotation and then check other words against a dictionary.</li>
<li>Do the letters appear with the same frequencies as in the English language</li>
</ol>
<p>We noticed that all of these suggestions are based on our knowledge of
English. What if the message was in a different language or even a
different alphabet?</p>
<p>We decided to use choice 4 - the letter frequencies.</p>
<p><strong>Magic part 1 - using known data to figure out a pattern for unknown data</strong></p>
<p>Even if we don't know the frequencies, if we can get a sample document in our language, we can figure them out. We downloaded a text from Project Gutenberg and used it to build
an array of 26 elements called <em>CorpusFreqs</em>. CorpusFreqs[0] would hold the
frequency of the letter 'a' in our sample document (that is, how many
times 'a' appears over the total number of letters in our document),
CorpusFreqs[1] the frequency of 'b' etc.</p>
<p>Now we have a model that we can use to compare our rotations to.</p>
<p><strong>Magic part 2 - wow, that 9th grade math is actually useful</strong></p>
<p>At this point, it usually isn't clear how to compare our rotations to
the model frequencies we calculated. Time to simplify,</p>
<p>We can look at another problem: Selecting a house.</p>
<blockquote>
<p><strong>Me:</strong> if we can only have one criteria, what would it be?</p>
<p><strong>Class:</strong> Neighborhood</p>
<p><strong>Me:</strong> Ok, let's rate each neighborhood between 0 and 100 </p>
<p><strong>Me:</strong> We can draw two houses on a line, which is better?</p>
<p><strong>Class:</strong> The one with the larger value!</p>
<p><strong>Me:</strong> What if we add a third house? Which is it more similar to?</p>
<p><strong>Class:</strong> The one it's closer to.</p>
</blockquote>
<p>Next:</p>
<blockquote>
<p><strong>Me:</strong> Well, what if we add another feature? Cost - let's map low cost to 100 and high cost to 0 and all the other costs in between.</p>
<p><strong>Me:</strong> If we want to visualize a house, how can we do it?</p>
<p><strong>Class:</strong> We can use a graph - like x,y points use location,cost points.</p>
</blockquote>
<p>So we do it.</p>
<blockquote>
<p><strong>Me:</strong> This is the least desirable house (0,0) and this is the best one (1,1).
I plot two houses and ask</p>
<p><strong>Me:</strong> Which is more desirable?</p>
<p><strong>Class:</strong> That one (they indicate the one closer to 1,1).</p>
<p><strong>Me:</strong> How can you tell</p>
<p><strong>Class:</strong> It's closer</p>
<p><strong>Me:</strong> How do we figure it out?</p>
<p><strong>Class:</strong> The Distance Formula!!!!!</p>
</blockquote>
<p>So now we add a third feature - size. It's pretty easy to show that
the distance formula extends to three-space and in fact to even higher
dimensions.</p>
<p><strong>Magic part 3 - from 3 dimensions to 26</strong></p>
<p>So now, we bring it back to our cipher. For the house example, we used
points in 1,2, and 3 dimensions (and we actually talked about it in
4D) so we used 1 through 4-space vectors to represent the points and
used Euclidean distance formula to see what houses were similar to
each other, or what points where near to each other</p>
<p>From there, it's easy to see that the frequency array we built from ou sample text is a
26-space vector and that we can build a similar vector for each
rotation.</p>
<p>From there we can use the distance formula to see how close each
rotation is to the sample document vector. The rotation with the
closest vector is pobably our solution.</p>
<p>So from a simple warm up problem we're at the gateway to some serious techniques that will come back time and time again as the students move through their CS education and careers.</p>
<p>Fun!</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>Build it firsthttp://cestlaz.github.io/posts/2013-11-19-build_it.md/2013-11-19T00:00:00-05:002013-11-19T00:00:00-05:00Mike Zamansky<div><p>The subtitle of this post is:</p>
<blockquote>
<p>and why my students are going to hate me tomorrow.</p>
</blockquote>
<p>When my good friend Gerry Seidman talks to my classes, he frequently
says "never use a data structure or algorithm you couldn't build yourself."</p>
<p>This doesn't mean that you have to write everything from scratch, just
that you should have some knowledge as to what's going on under the
hood. I find that all too often young programmers just rely on APIs
and libraries and really don't know how their computers and programs are working.</p>
<p>And it's never too early to start.</p>
<p>We've been spending time talking about arrays recently. Now, most of
my students have some exposure to Python and so we started talking
about the flexibility and power of the Python list vs the limited
facilities of the Java array.</p>
<p>How to solve the problem and make Java easier to work with? Let's
write our own list class. We started simple:</p>
<pre class="code literal-block"><span></span>public class myList {
private int[] data;
private int numItems;
public myList() {
data = new int[5];
numItems = 0;
}
// append to the end of the list
public add(int d) {
if (numItems >= data.length) {
tmp = new int[data.length+data.length/2];
for (int i=0;i<numItems;i++)
tmp[i]=data[i];
data = tmp;
}
data[numItems]=d;
numItems = numItems + 1;
}
}
</pre>
<p>from there we added functionality such as:</p>
<ul>
<li>Inserting in arbitrary locations</li>
<li>Removing items from the list</li>
<li>Searching for an item</li>
<li>Setting the item at a location to a value</li>
</ul>
<p>And of course we were also able to talk about things like refactoring
out growing the array into a private method.</p>
<p>And tonight the classes are changing the internal array from int[] to String[].</p>
<p>Of course, what we're building is an ArrayList. Tomorrow we'll reveal
that little fact and of course the classes will all hate me, but then,
they'll really understand what's going on under the hood.</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>Databases - the next dayhttp://cestlaz.github.io/posts/2013-10-09-database-followup.md/2013-10-09T00:00:00-04:002013-10-09T00:00:00-04:00Mike Zamansky<div><p>Two days ago I asked the students, in small groups, to come up with a design to store a school (or school district) database.</p>
<p>Yesterday we discussed the designs.</p>
<p>All the students took our brand of AP Computer Science last year - a
superset of the old AB curriculum and in that class they implemented a
number of data structures such as binary search trees and hash tables,
but they really didn't have an opportunity to design something more
comprehensive.</p>
<p>At the start, suggestions were based around simple monolithic
designs. A class to represent a student, an array or hash table of
these classes and in each object, an array of grades or something like
that. </p>
<p>Soon the discussion turned to optimizing search based on different
"keys." Searching by student id or searching by name. This led to the
idea of indices. For example, if our main data set is sorted by name, we can make auxiliary lists sorted by id or grades and use those to point into our main data set.</p>
<div align="center">
<a href="http://cestlaz.github.io/img/2013-10-09-database-part2/indices.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/2013-10-09-database-part2/indices.png" class="" alt="">
</a>
</div>
<p>This was followed by less monolithic ideas -- essentially ideas behind
linking different tables using key fields. For example, a student
table with student id and a transcript table where each line has a
student id, a class, grade, teacher, and date.</p>
<div align="center">
<a href="http://cestlaz.github.io/img/2013-10-09-database-part2/links.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/2013-10-09-database-part2/links.png" class="" alt="">
</a>
</div>
<p>Pretty sophisticated ideas.</p>
<p>From there we talked about assorted data structures that we could use with these ideas. </p>
<p>I think it was a productive day.</p></div>Databases - putting it all togetherhttp://cestlaz.github.io/posts/2013-10-07-databases.md/2013-10-07T00:00:00-04:002013-10-07T00:00:00-04:00Mike Zamansky<div><p>So, we're into the second year of my Software Development class. It's a
little different since last time, I taught many of the kids in
AP. This time, they're mostly new to me.</p>
<p>In AP, everything is low level. The students build linked lists,
binary search trees, heaps, hash tables, graphs and the like. It's all
about building the data structure. The Node, if you would.</p>
<p>We're about to start talking about databases. We'll probably spend a
couple of days on relational databases and SQL and then some time with
MongoDB. </p>
<p>There can be a big gap between a single lower level data structure and
something as complex as a database.</p>
<p>I wanted to learn more about the kids and also
see how they would go from last years material to solving a larger
problem.</p>
<p>So today we talked about designing a database. Actually, we haven't
even gotten there yet. We actually talked about what data we'd want to
store if we were building a database for a school. Sounds like a
typical class assignment.</p>
<p>Turns out, there's lots of data:</p>
<ul>
<li>Personal info like name, id number, address</li>
<li>Transcript based data including:</li>
<li>grade</li>
<li>class code</li>
<li>class section</li>
<li>time stamp</li>
<li>teacher</li>
<li>Teacher information</li>
<li>Attendance Information</li>
</ul>
<p>And more.</p>
<p>The kids were then broken into groups.</p>
<p>The assignment:</p>
<blockquote>
<p>Assume you're working in Java. You can use all the tools covered last years. Both built in like HashMaps and TreeMaps and those that you built like search trees or heaps.
</p><p></p>
You can assume that whatever you design will automatically be stored in a file system without any changes.
<p></p>
Design your student database.
</blockquote>
<p>It was great hearing the discussions. Some groups based things on Java
Classes, some on hash tables, some trees. Some groups started with
efficiency concerns and wondered what types of queries they would
need. I was really pleased with the level of activity and the types of
concerns the students had.</p>
<p>I'm really looking forward to tomorrow when we discuss the designs and move on from there.</p></div>Real Data - Part IIhttp://cestlaz.github.io/posts/2013-05-20-Real_Data_Part_II.md/2013-05-20T00:00:00-04:002013-05-20T00:00:00-04:00Mike Zamansky<div><p>About a month ago, I talked about using <a href="http://cestlaz.github.io/2013/04/14/Real_Data.html#.UZjTjqDctKk">real
data</a>
with our intro classes. After looking at the correlation between
school's SAT scores and free and reduced lunch rates, it was time to
turn the students loose.</p>
<p>The assignment: Find some interesting data out and do something with
it. Make a web page that shows what you did and what you
discoverde. We had already looked at the NYC Data Mine as well as a
few other sources but students were encouraged to find new data sourcess.</p>
<p>The results were terrific. On top of the requirements, some students
figured out how to incorporate Google Maps, graphs, and other niceties
well beyond what we've covered in class.</p>
<div align="center">
<a href="http://cestlaz.github.io/img/data_project.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/data_project.png" class="" alt="">
</a>
</div>
<p>Explorations included:</p>
<ul>
<li><a href="http://149.89.150.100/~veronika.azzara/compsci_project/maps.py">311 Calls in NYC</a></li>
<li><a href="http://149.89.150.100/~vanessa.miraj/untitled%20text%203.html">Movie earnings</a></li>
<li><a href="http://149.89.150.100/~lily.chen/fooddata.html">Food pricing over time</a></li>
<li><a href="http://149.89.150.100/~ivette.chen/healthiest-state-rankings.py">Red Meat and Health</a></li>
<li><a href="http://149.89.150.100/~hilary.tung/data/pie%20vs%20cake.py">Cake comparisons</a></li>
</ul>
<p>and even </p>
<ul>
<li><a href="http://149.89.150.100/~kyle.oleksiuk/Kyle&AnishProject2.html">Pokemon</a></li>
</ul>
<p>That's just a sampling.</p>
<p>Well done guys.</p></div>Madlib Madnesshttp://cestlaz.github.io/posts/2013-04-30-Madlib_Madness.md/2013-04-30T00:00:00-04:002013-04-30T00:00:00-04:00Mike Zamansky<div><p>Earlier in the term, our intro classes spent a little time learning
some basic HTML. We don't spend a lot of time on it, just enough so
that the students can present their work in a static web site. The end
goal, though, was to programatically generate the web sites - there's
nothing quite as empowering to a student as when they can present their
work to the world.</p>
<p>Finally, it's all coming together.</p>
<p>Now that the classes are comfortable with Python, we can have some
fun. We all remember Mad Libs - that wacky word game where you select
unknowingly select words to substitute into a basic story and
hilarity ensues.</p>
<p>We did our own versions using Python files, lists and
dictionaries. </p>
<p>Here are some of the results:
1. <a href="http://homer.stuy.edu/~richard.zhan/19-Madlibs.py">
http://homer.stuy.edu/~richard.zhan/19-Madlibs.py
</a>
2. <a href="http://homer.stuy.edu/~veronika.azzara/madlibifystory.py">
http://homer.stuy.edu/~veronika.azzara/madlibifystory.py
</a>
3. <a href="http://homer.stuy.edu/~belinda.liang/18-MadLibsMiniProject.py">
http://homer.stuy.edu/~belinda.liang/18-MadLibsMiniProject.py
</a>
4. <a href="http://homer.stuy.edu/~kyle.oleksiuk/MadlibifyProject5.py">
http://homer.stuy.edu/~kyle.oleksiuk/MadlibifyProject5.py
</a>
5. <a href="http://homer.stuy.edu/~phillip.huynh/story.py">
http://homer.stuy.edu/~phillip.huynh/story.py
</a></p>
<p>The students wrote a basic story with substitution points. Their
programs then randomly replaced these points with words from an
assortment of categorized lists. </p>
<p>Enjoy!!!!!</p></div>Real Datahttp://cestlaz.github.io/posts/2013-04-14-Real_Data.md/2013-04-14T00:00:00-04:002013-04-14T00:00:00-04:00Mike Zamansky<div><p>When looking for assignments for our classes, in addition to trying to
craft assignments that develop and reinforce key ideas, we also strive
to come up with ideas that "speak" to the students and keep their
interest. We write small games, use problems within the student's
experiences, and in general try to find problems that are appealing.</p>
<p>This is much easier to do when the kids can read data from a file. The
tool we're using with our sophomores right now is Python and Python
makes reading files very easy. Combining file input with basic string
functions and all of a sudden, we can read and parse comma separated
values.</p>
<p _="%" endhighlight>{% highlight python linenos %}
l=[]
for line in open(filename).readlines():
l.append(line.strip().split(",")</p>
<p>True, this doesn't handle quotes and embedded commas, but that just
leads to a discussion on cleaning up data and when we do list
comprehensions, things get even slicker.</p>
<p>We could just make up some sample data, for example, student test scores:</p>
<p>Tom,95,87,97,93</p>
<p>Sarah,98,98,84,92</p>
<p>Harry,90,90,90,90</p>
<p>Sue,94,95,96,97</p>
<p>But it's so much more fun with the wealth of CSV data waiting to be
grabbed. If your kids like sports, you can check
out <a href="http://www.baseball-reference.com/">baseball-reference.com</a>
or it's counterparts for basketball or football. </p>
<p>We decided to look at government data instead.</p>
<p>Federal data can be found at <a href="http://www.data.gov/">data.gov</a> but we focused on <a href="https://data.cityofnewyork.us/">New York City</a>. We
settled
on <a href="https://data.cityofnewyork.us/Education/SAT-Results/f9bf-2cp4">SAT</a>
data. SAT math, reading, and writing scores for all NYC public
schools. Something Stuy kids are very interested in. We were able to
look for comparable schools, which schools had large spreads between
math and verbal, which schools had score increases over time, etc.</p>
<p>Much more interesting to look at real SAT data than made up student
grade info. </p>
<p>Tomorrow we'll look at combining data sets -- looking at
the relationship between SAT scores and school ratings and
demographics. It should be interesting. Later, we'll grab books
from <a href="http://www.gutenberg.org/">Project Gutenberg</a> and see
how we can analyze large texts.</p>
<p>The moral of the story - there's lots of great data easily accessible
-- let's use it to motivate and engage our students.</p>
<p><b>UPDATE:</b></p>
<p>It's taken me a while to post this, and in the meantime we analyzed
the SAT data from one NYC data set and matched it with a data set of
demographic data:</p>
<div align="center">
<a href="http://cestlaz.github.io/img/SAT_SCORES.png" rel="lightbox">
<img width="50%" src="http://cestlaz.github.io/img/SAT_SCORES.png" class="" alt="">
</a>
</div>
<p>The graph shows a strong correlation between schools with a high number of
students eligable for free lunch (the Y-axis) and low SAT scores (the
X-axis). This led to a very interesting conversation on the effects of
poverty.</p>
<p>We also noticed a couple of outliers. There's one school at about
(1400,82). High poverty (free lunch) and national average SAT. Also two
schools with low free lunch numbers and middling SAT scores
(1400,17ish).</p>
<p>The (1400,82) point turns out to be a school that caters to English
Language Learners and we presume has a large number of recent
immigrants (partially noted by the name and also by the fact that
their SAT math scores far surpassed the English ones).</p>
<p>Great discussions ensued all due to applying CS to real world data.</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>Layers of a lessonhttp://cestlaz.github.io/posts/2012-12-17-layers-of-a-lesson.html/2012-12-17T00:00:00-05:002012-12-17T00:00:00-05:00Mike Zamansky<div align="center">
<img width="50%" src="http://cestlaz.github.io/img/turtle-anim.gif" class="" alt="">
</div>
<p>
</p><p>
My last post I was talking about the fact that as teachers, our
knowledge and experience is frequently trivialized. The tenor of the
times is that anyone can design a course, anyone can teach, and in
fact, we don't even need teachers, just videos or computer based
systems. If you've ever tutored a friend, you're more than qualified.
</p><p>
That might be a strong statement but everywhere you look you see
"education" programs designed and implemented by non teachers. It
seems that it's believed that teaching only involves the most
superficial of transfers of information.
</p><p>
Today, I thought I'd look at a lesson I taught the other week. How
I've seen similar material presented and how my colleagues and I might treat
the subject.
</p><p>
We use <a href="http://ccl.northwestern.edu/netlogo/">NetLogo</a> in
our Sophomore level intro course. It's a highly parallel version of
logo. It's very visual, it's great for modeling and you can introduce
deep, meaningful concepts such as parallel processing in a gentle
manner.
</p><p>
Early on the kids have to learn how to manipulate the turtles. In
NetLogo you write a single program and it's run by all the turtles "at
once." The image above is one of their early "experiments." Have the
turtles wiggle out of the center, but when they get to an invisible
border, start spinning. They do a number of variations on this theme.
</p><p>
A solution might look like this:
</p><pre>
; asked in a turtle context
to gospin
ifelse abs xcor < 8 or abs ycor < 8
[ wiggle ] ; wiggle implementation not shown
[ left 5 ]
end
</pre>
<p>
Let's call level one just talking about the solution by looking at the
program as a sequence of instructions. Specifically relating the
instructions to the problem, showing how it solves it, and that's it.
</p><p>
This is the simplest level. A book, video, or online courseware can
approach teaching at this level. A non computer scientist teacher or a
non teacher computer scientist could do so as well. Students might
learn a bit but I wouldn't hope for much inspiration or
creativity to come out of it.
</p><p>
Let's move to level two.
</p><p>
Here we might talk about "what the turtles are doing." They're always
doing something, either wiggling or spinning. This is a step in the
right direction. When done right, the students start thinking about
the problem in a more general sense but they're still looking at the
problem as something that exists only in the world of NetLogo. They
are more likely develop patterns than in level one, but it's still
limited.
</p><p>
Level three is where things get interesting. On the surface, the
problem is just a nice introduction to programming turtles in
NetLogo. At a deeper level, it's an opportunity to introduce the kids
to State Machines. A new way of thinking about problems and problem
solving.
</p><p>
Students understand the idea of a "state." For example, in class,
they're in a "seated state," maybe in a "note taking state," etc. It's
easy to see that they don't know what their day will bring but they
constantly make decisions based on their "state." Likewise, they can
think about the turtle as in a state. It's either in a wiggling state
or a spinning state and based on their situation they can either
continue in their current state or transition to the other one:
</p><div align="center">
<img width="50%" src="http://cestlaz.github.io/img/spin-state.png" class="" alt="">
</div>
This opens up a new way of thinking and it's easy to see how this
extends to other problems, for example, a ghost from pacman:
<div align="center">
<img width="50%" src="http://cestlaz.github.io/img/pacman-ghost-state.png" class="" alt="">
</div>
A good teacher thinks about working across these levels. He adjusts
based on the class and looks for opportunities to develop these deeper
concepts.Real Projectshttp://cestlaz.github.io/posts/2012-12-09-real-projects.html/2012-12-09T00:00:00-05:002012-12-09T00:00:00-05:00Mike ZamanskyThis post was supposed to be about varsity academic teams but I wanted
to share something else first.
<p>
For years I was unhappy with our "research" course but due to the
misguided views of our past administration, I pretty much had to keep
it running. Over the same time, I was frustrated by the fact that
there was so much missing in our students computer science related
education. Specifically, kids don't really get to experience creating
large "real" systems from beginning to end. I was also frustrated by
the fact that the previous administration prevented me from creating a
course to address this problem.
</p><p>
Due to a particular set of circumstances, I was able to
convert our research course into what is now my "Software Development"
course.
</p><p>
So far, I'm very happy with the results.
</p><p>
The classes just finished their latest projects. Over the course of
about three week, mostly on their own time, working around homework
and other obligations, student groups designed, developed, tested and
deployed a range of applications.
</p><p>
All the programs
use <a href="http://cestlaz.github.io/posts/2012-12-09-real-projects.html/flask.pocoo.org">Flask</a> as a web framework. Many
use <a href="http://cestlaz.github.io/posts/2012-12-09-real-projects.html/mongodb.org">MongoDB</a> to store data and they used a
range of web resources and apis. The students were a little limited by
the time frame of the project and the fact that I just started
teaching them how to use javascript mid project, but they really did a
terrific job.
</p><p>
A few in particular were a lot of fun:
</p><p>
</p><div align="center">
<a href="http://ml7.stuycs.org:7207">
<img width="400px" src="http://cestlaz.github.io/img/survival-guide.png">
</a>
</div>
<p>
The <a href="http://ml7.stuycs.org:7207">Survival Guide</a> used
Google Maps to help prepare you for all sorts of disasters ranging
from Hurricanes, to Alien Invasions, to the Zombie Apocalypse.
</p><p>
A <a href="http://ml7.stuycs.org:6202">Movie recommender</a> That used
MoveDB, YouTube, and the NY Times API to find and show info about
movies and actors.
</p><p>
</p><div align="center">
<a href="http://ml7.stuycs.org:7203">
<img width="400px" src="http://cestlaz.github.io/img/recipe-pricer.png">
</a>
</div>
<p>
<a href="http://ml7.stuycs.org:7203">Recipe Pricer</a> scrapes <a href="http://allrecipes.com">allrecipes.com</a> for a
recipe then uses Google's shopping API to price out the ingredients
(with some interesting results).
</p><p>
</p><div align="center">
<a href="http://ml7.stuycs.org:7205">
<img width="400px" src="http://cestlaz.github.io/img/stuy-page.png">
</a>
</div>
<p>
One group remade the <a href="http://ml7.stuycs.org:7205">Stuyvesant
Home Page</a> but since they're using a Twilio test account you won't
be able to see the really neat stuff they did.
</p><p>
and
</p><p>
<a href="http://ml7.stuycs.org:6206">Tweet Stat</a> tells you how well
your favorite celebrity spells.
</p><p>
This is just a sampling.
</p><p>
You can see all of them at <a href="http://ml7.stuycs.org/project2-results.html">Our Projects Page</a> and all the code is up on GitHub (linked from the page).
</p><p>
I'd encourage you to take a look. It would be terrific if you could
give the class feedback either by commenting here or on the project
page.
</p><p>
I can't wait to see what they do for their next projects.
</p><p>
Special thanks to Ben, Moisey and the entire <a href="http://digitalocean.com">DigitalOcean</a> team for providing us with server space for all of this.</p>Sorting from the top and from the bottomhttp://cestlaz.github.io/posts/2010-03-14-sorting-from-top-and-from-bottom.html/2010-03-14T00:00:00-05:002010-03-14T00:00:00-05:00Mike Zamansky<div id="content"><h1 class="title">Sorting from the top and from the bottom</h1> <p>I've been meaning to write this post for a couple of weeks, but some times life just gets in the way. </p><p>I've always thought it important to arm students with as many different tools with which to attack problems as possible. As such, the courses I teach use a number of different languages, each highlighting a different paradigm and thought process. The hope is that by the end of the sequence, they can look at problems from many different angles. </p><p>In my advanced placement classes, we recently studied sorting algorithms. It think the quicksort is a good example of a problem that can be looked at from multiple points of view. </p><p>In my experiences talking to teachers and students who cut there teeth using languages like Java, C, or C++, much of the discussion deals with the actual partitioning of the array. Comparing elements, swapping them and arriving in the middle. One might end up with something like this as a first cut: </p> <pre class="src src-java"><br><span class="linenr"> 1: </span><span style="color: #a020f0;">public</span> <span style="color: #228b22;">void</span> <span style="color: #0000ff;">qsort</span>(<span style="color: #228b22;">int</span>[] <span style="color: #a0522d;">a</span>,<span style="color: #228b22;">int</span> <span style="color: #a0522d;">l</span>, <span style="color: #228b22;">int</span> <span style="color: #a0522d;">h</span>)<br><span class="linenr"> 2: </span>{<br><span class="linenr"> 3: </span><span style="color: #a020f0;">if</span> (l>=h)<br><span class="linenr"> 4: </span> <span style="color: #a020f0;">return</span>;<br><span class="linenr"> 5: </span><br><span class="linenr"> 6: </span><span style="color: #b22222;">/* </span><span style="color: #b22222;">Just use lowest index as pivot for now */</span><br><span class="linenr"> 7: </span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">pivot</span> = a[l];<br><span class="linenr"> 8: </span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">low</span>=l;<br><span class="linenr"> 9: </span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">high</span>=h;<br><span class="linenr">10: </span><br><span class="linenr">11: </span><span style="color: #b22222;">/* </span><span style="color: #b22222;">partition the data set around the pivot value */</span><br><span class="linenr">12: </span><span style="color: #a020f0;">while</span> (l<=h)<br><span class="linenr">13: </span>{<br><span class="linenr">14: </span> <span style="color: #a020f0;">while</span> (a[l]<pivot)<br><span class="linenr">15: </span> l++;<br><span class="linenr">16: </span> <span style="color: #a020f0;">while</span> (a[h]>pivot)<br><span class="linenr">17: </span> h--;<br><span class="linenr">18: </span> <span style="color: #a020f0;">if</span> (l<=h)<br><span class="linenr">19: </span> {<br><span class="linenr">20: </span> <span style="color: #228b22;">int</span> <span style="color: #a0522d;">tmp</span>=a[l];<br><span class="linenr">21: </span> a[l]=a[h];<br><span class="linenr">22: </span> a[h]=tmp;<br><span class="linenr">23: </span> l++;<br><span class="linenr">24: </span> h--; <br><span class="linenr">25: </span> }<br><span class="linenr">26: </span>}<br><span class="linenr">27: </span><br><span class="linenr">28: </span><span style="color: #b22222;">/* </span><span style="color: #b22222;">sort items below and above the pivot */</span><br><span class="linenr">29: </span>qsort(a,low,l-1);<br><span class="linenr">30: </span>qsort(a,l,high);<br><span class="linenr">31: </span><br><span class="linenr">32: </span>}<br></pre> <p>A fair amount of time and detail is spent dealing with the low level movement of data within the array . This is important – good stuff, but it takes the emphasis away from the higher level elegance of the algorithm. </p><p>The quicksort can be described as: </p> <ol><li> If the size of the list is <= 1, return.</li><li><ol><li> Select a pivot element</li><li> Generate the list L of items smaller than the pivot</li><li> Generate the list H of items larger than the pivot</li><li> the sorted list is qsort(L)+pivot+qsort(R)</li></ol></li></ol> <p>Having seen some scheme in their intro class, our students have a tool with which we can describe the quicksort in terms much closer to the description (allowing for the fact that this doesn't deal with multiple values equal to the pivot correctly): </p> <pre class="src src-scheme"><br><span class="linenr"> 1: </span>(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">makefilter</span><br><span class="linenr"> 2: </span> (<span style="color: #a020f0;">lambda</span> (op x)<br><span class="linenr"> 3: </span> (<span style="color: #a020f0;">lambda</span> (n) (op x n))))<br><span class="linenr"> 4: </span><br><span class="linenr"> 5: </span>(<span style="color: #a020f0;">define</span> <span style="color: #0000ff;">qsort</span> <br><span class="linenr"> 6: </span> (<span style="color: #a020f0;">lambda</span> (l)<br><span class="linenr"> 7: </span> (<span style="color: #a020f0;">cond</span> ((null? l) '())<br><span class="linenr"> 8: </span> (<span style="color: #a020f0;">else</span> (append (qsort (filter (makefilter > (car l)) l))<br><span class="linenr"> 9: </span> (list (car l))<br><span class="linenr">10: </span> (qsort (filter (makefilter < (car l)) l)))))))<br></pre> <p>This allows us to discuss the quicksort at a much higher level and focus on things like selecting a good pivot or the analysis of the run time. I believe this makes it much easier to really understand what's going on. </p><p>Having discussed it in this functional context, we can also look at the same thing in a scripting language such as python: </p> <pre class="src src-python"><br><span class="linenr">1: </span><span style="color: #a020f0;">def</span> <span style="color: #0000ff;">qsort</span>(l):<br><span class="linenr">2: </span> <span style="color: #a020f0;">if</span> <span style="color: #a020f0;">len</span>(l)<=1:<br><span class="linenr">3: </span> <span style="color: #a020f0;">return</span> l<br><span class="linenr">4: </span> <span style="color: #a020f0;">else:</span><br><span class="linenr">5: </span> <span style="color: #a020f0;">return</span> qsort([x <span style="color: #a020f0;">for</span> x <span style="color: #a020f0;">in</span> l[1:] <span style="color: #a020f0;">if</span> x <= l[0]]) + [l[0]]+\<br><span class="linenr">6: </span> qsort([x <span style="color: #a020f0;">for</span> x <span style="color: #a020f0;">in</span> l[1:] <span style="color: #a020f0;">if</span> x > l[0]])<br><span class="linenr">7: </span><br></pre> <p>Again, the focus is on the algorithm, not the array or list manipulation. </p><p>Looking at the problem from both the more abstract side, which in this case functional languages allow, and the more concrete, as we did in Java gives our students more tools with which to attack problems. </p><p>Just some food for thought. </p> </div><div class="blogger-post-footer"><img width="1" height="1" src="https://blogger.googleusercontent.com/tracker/468689896075458340-2070280110494147035?l=cestlaz.blogspot.com" alt=""></div>What's Nexthttp://cestlaz.github.io/posts/2010-02-18-whats-next.html/2010-02-18T00:00:00-05:002010-02-18T00:00:00-05:00Mike ZamanskyJust a short follow up on the last post.<br><br>In thinking about how I frequently programs, once I have a plan, I work on one part of the project, and then ask myself "what's next?" That is, what is the next step towards completion.<br> <br>It reminded me about a guest speaker we had a about a year and a half ago at one of our "professional development" days. For the past two years, our school has had "writing across the curriculum" as one of it's goals. While it's a laudable idea, I find the rationale for this goal to be poorly communicated to our faculty and the implementation weak at best.<br><br>Regardless, the guest speaker, <a href="http://en.wikipedia.org/wiki/William_Zinsser">William Zinsser</a>, made a few good points.<br><br> The most important reason for most of us to write is to convey ideas or arguments. In short, communication. Many students have problems organizing and ordering their thoughts and as a result, their writing is all over the place. Zinsser simplified it to the following:<br><br><ol><li>What does the audience know?</li><li>What do they need to know next?</li></ol>That drives your next sentence. You continue this 1-2 punch until you've communicated your ideas.<br><br>This makes loads of sense, but here I was 40 years old and it was the first time I heard writing explained this way. What really struck me, however was that this concept wasn't new at all. Every ninth or tenth grader goes through this process time and time again.<br><br>Think about geometric proof. We have some given information and a conclusion we wish to prove. At each step along the way its:<br><br><ol><li>What do we know so far?</li><li>What's the next step to get us closer to the conclusion?</li></ol><br>Same idea.<br><br>The same can be said for program development.<br><br>Of course this makes tremendous sense since all thee things: writing, proof, and programming, are methods of communication.<br><br>Just something to think about.<div class="blogger-post-footer"><img width="1" height="1" src="https://blogger.googleusercontent.com/tracker/468689896075458340-1983623605693836355?l=cestlaz.blogspot.com" alt=""></div>Towers of Hanoihttp://cestlaz.github.io/posts/2010-01-10-towers-of-hanoi.html/2010-01-10T00:00:00-05:002010-01-10T00:00:00-05:00Mike Zamansky<div class="figure"><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/_7YN3bkG0cSc/S0pFwojEDmI/AAAAAAAAFa8/WMWXtwK6nxo/s1600-h/Hanoi.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/_7YN3bkG0cSc/S0pFwojEDmI/AAAAAAAAFa8/WMWXtwK6nxo/s320/Hanoi.jpg"></a><br></div><br></div>Closed out last week teaching the <a href="http://www.cut-the-knot.org/recurrence/hanoi.shtml">Towers of Hanoi</a>. It's a wonderful topic. Not because it's so interesting in and of itself, but as a platform from which you can explore any number of interesting topics.<br><br>Many books appropriate for the AP (AB) curriculum mention the towers, but to my knowledge most only scratch the surface. I randomly grabbed two books that I consider good from the shelf before writing this. One that I actually use when I teach AP comp sci and another more appropriate for a follow up course. Both discuss the towers, but merely show a solution and talk about the run time a little.<br><br>So many possibilities left out. <br><br>I usually do these lessons with my sophomores but since many of my AP students (juniors) hadn't ever seened the problem, I felt it was worth covering. <br><br>By looking at a few small examples, 1 disk, two disks, three disks, four disks, it's easy to notice the symetry in the solutions ultimately leading the this short routine: <br><pre class="src src-java"> </pre><pre class="src src-java"> 1: hanoi(n,src,dst,tmp) {<br> 2: <span style="color: #a020f0;">if</span> (n==1)<br> 3: System.out.println(<span style="color: #8b2252;">"Move from "</span>+src+<span style="color: #8b2252;">" to "</span>+dst);<br> 4: <span style="color: #a020f0;">else</span><br> 5: {<br> 6: hanoi(n-1,src,tmp.dst);<br> 7: hanoi(1,src,dst,tmp);<br> 8: hanoi(n-1,tmp,dst,src);<br> 9: }<br>10: } <br></pre><br>Now, the fun can really start: <br><br>We want to talk about the correctness of our algorithm and also how many moves it will take, that is, the run time. First, we'll use inductive ideas to show our algorithm is correct. This "proof" (we do it somewhat informally) can be enlightening. As sophomores, the only proofs students have seen are those statement/reason things they do in math class. Here we can introduce them to the idea that proof is just an "irrefutable argument" and apply it in a more practical setting. <br><br>From there we look at run time, that is, how many moves will it take to solve the n disk problem. It's easy to see the pattern of T(N) = 2T(n-1)+1 . Students will usually see that we can rewrite this as T(N)=2<sup>N</sup>-1 which we can also prove by induction.<br><br>Now we can see the ramifications of the run time. At 1 million moves per second, it works out to close to 600,000 years. This in and of itself is revealing, we can't just "get a faster computer." Here we can discuss <a href="http://en.wikipedia.org/wiki/Moore%27s_law">Moore's Law</a> and the physical limits on our computers, making sure to make appropriate reference to <a href="http://en.wikipedia.org/wiki/Grace_Hopper">Grace Hopper</a> and her <a href="http://www.flickr.com/photos/shinythings/154816771/">nanosecond</a>. <br><br>This leads to a discussion alternate approaches such as parallel processing, but that doesn't work if our problem can only be solved sequentially.<br><br>The rest of the class is used discussing other hard problems and other approaches including heuristics, probabalistic, randomized, and anything else that comes up. <br><br>So, there you have it. From this one simple problem we get to introduce students to: <br><br><ul><li id="sec-1">Alternate forms of proof (specificall induction) <br></li><li id="sec-2">Intractable problems <br></li><li id="sec-3">Unsolvable problem <br></li><li id="sec-4">Moores law and the limits of our computing power <br></li><li id="sec-5">Alternate approaches to computing <br><br><br><ul><li id="sec-5">Parallel programming <br></li><li id="sec-5.2">Protein based computers <br></li><li id="sec-5.3">Randomized algorithms <br></li><li id="sec-5.4">Probabalistic algorithms <br></li><li id="sec-5.5">Heuristics</li></ul><br></li></ul><div class="blogger-post-footer"><img width="1" height="1" src="https://blogger.googleusercontent.com/tracker/468689896075458340-6512019415176840666?l=cestlaz.blogspot.com" alt=""></div>Looking for interesting questionshttp://cestlaz.github.io/posts/2010-01-03-looking-for-interesting-questions.html/2010-01-03T00:00:00-05:002010-01-03T00:00:00-05:00Mike ZamanskyFor the winter break, I assigned <a href="http://apcentral.collegeboard.com/apc/public/repository/ap08_comp_sci_a_frq.pdf">this</a> set of A exam questions (actually, just the three that don't deal with the case study) to my AP classes. I wanted to assign something that wasn't particularly heavy but I didn't want my students to forget everything over break. <br><br>As with most AP exam questions, they're long, wordy, and somewhat brain dead. They take a long time to read, but they frequently take you step by step through what they want you to do. <br><br>I remember the first time I really thought about this. It was back when the exam was given in Pascal. The curriculum required that classes cover one of the nlogn sorts but didn't specify which one. One of the free response questions literally walked the students, step by step, through the merge sort. Part one had them split an array in to two parts, part two had them write a routine that merged two sorted arrays (and explained step by step how to do it). You could get a perfect score and still know nothing about the algorithm, or even about writing a recursive routine (since the question told you exactly what to do). <br><br>I hate these types of questions. The exam tests coders, not computer scientists. Programming competition problems (such as from the <a href="http://www.uwp.edu/sws/usaco/">USACO</a>) are much more interesting, but from a beginners point of view they have their own problems. Beginners might not have enough tools to attack them, and at times they're all or nothing – they're not set up to develop a simple, working solution that you can then improve on. <br><br>So, I'm always looking for interesting questions for my students. Problems that a student can attack with a minimal skill set, but can be refined through analysis or upon studying more advanced techniques. <br><br>I guess the first problem of this nature that I usually do with my AP students, usually deals with counting frequencies of test student test scores, identifying students by their four digit ID number. Most students start by creating a huge list all the tests for all the students, but some, and soon all, realize that by using the ID number as an index into an array, they can solve this type of problem much more efficiently. Looking at this technique early also sets the stage for looking at topics such as radix sorting and hashing later on. <br><br>This weekend I stumbled upon <a href="http://20bits.com/articles/interview-questions-two-bowling-balls/">this</a> problem and we'll probably look at in in class some time this week. I like it because you can easily get a naive solution, but it lends it self to a step wise refinement that works well in the classroom. <br><br>A few years ago, I also discovered a wonderful article by David Ginat, titled "Effective binary perspectives in algorithmic problem solving" which you can get if you are an ACM member <a href="http://portal.acm.org/citation.cfm?id=772942&dl=">here</a>. <br><br>Both the stuff in Ginat's piece and the bowling ball article are nice because they can be handled naively with brute force approaches using arrays, but with a little cleverness you can do much better. <br><br>Of course, as students progress through our classes, we have more flexibility as to types of questions. For example, once we do search and other recursive algorithms a few weeks from now, I can present problems that lead to dynamic programming solutions. <br><br>I'd love to hear any interesting accessible problems you've come across in your computing careers.<div class="blogger-post-footer"><img width="1" height="1" src="https://blogger.googleusercontent.com/tracker/468689896075458340-7947206663945758208?l=cestlaz.blogspot.com" alt=""></div>