Breaking down problems and writing

This question appeared on Facebook a few days ago:

Does anyone have an effective way to teach students how to break down a problem into steps and then solve each step one by one? I think my students are struggling with a large question and breaking it in subsequent parts.

There were some good suggestions. I wanted to add something but didn't have time then so I thought I'd write it up now.

As an aside, it took me forever to find the post again over on Facebook. If there's a way to mark posts or save a direct link I'd love to hear it. I had to look through all the CS Ed groups I belong to manually until I found it again.

When I read the program I was reminded of a PD session we had to attend back at Stuyvesant. Back then the fad was Writing Across the Curriculum. Every teacher in every class was to give some significant writing assignment, evaluate it and provide feedback. Let's forget the fact that most of us never had any training or preparation to do so.

On that PD day the guest speaker was William Zinsser. The first thing he said was that what we were being asked to do by our principal was bunk. He then proceeded to give advice on simple good writing.

The procedure he recommended following was to ask yourself (or have the student ask themselves) "what does my audience need to know next?" That's your next sentence. Then ask the question again. Rinse and repeat until done.

It was simple and it made sense. It also applied to introductory CS problems. When starting out, students have a limited CS / programming tool box so a good question for them to ask when trying to solve a problem is not only "what do I need to do next? but also "what can I do next?"

When students have a limited CS vocabulary and set of idioms - loops, conditionals, functions, whatever, there will only be so many things they can do to move a problem along. If they go through the things the can do they will likely fall on to what they should do.

It's similar to doing a proof in geometry. Students have a set of givens. Given that set, what can they do? They only know so many theorems at the beginning.

Over time, they'll recognize patterns and develop as problem solvers.

If you're part of the AP CS A teachers facebook group you probably saw the question. Many good answers were posted. I just wanted to add this thought to the collection.

New York State moving forward with CS Teacher Certification

Last April I woke up early and trekked up to Albany along with a few of my Hunter College colleagues to share our thoughts on K12 Computer Science teacher certification with the Board of Regents. We gave a presentation to the Regents Higher Education Committee and afterwards had a chance to talk with some of the Regents as well as other members of the New York State Department of Education.

I left feeling that our proposals were well received and I think everyone present - both the Hunter and NYSED contingents hoped that things would move forward on this important issue.

Fast forward to today, December 8, 2017. I was up at the crack of dawn. Driving in the dark in the snow from NYC to Albany to once again attend a Board of Regents Higher Education Committee meeting. This time, the agenda item was:

Proposed Amendments to Part 30 of the Regents Rules and Section 52.21 and Part 80 the Regulations of the Commissioner of Education Relating to a New Certification Area and Tenure Area for Computer Science

No discussion or debate this time around just the proposal. If I understand the process correctly, this should come up again at the March meeting at which point it will be voted on. If approved, it looks like we'll have a pathway towards certification for CS teachers.

I haven't had a chance to dive into the details but at the meeting a few key points came up:

  • As the proposal indicates this will be a subject area in which a teacher can be certified and be awarded tenure.
  • There will be a traditional pathway for new teachers - Bachelors / Masters degree
  • There will be an alternative pathway for people entering from the workforce
  • There will be an extension for teachers with another license so they won't have to give up tenure in their current license.
  • There will be an "individual evaluation" pathway which sounds to me like it could catch people who fall through the cracks.
  • There looks to be a sensible ramp up period - until September 2022
  • There's a grandfathering provision that looks to last 10 years.

This sounds like a smart sensible plan. Multiple pathways, shallow ramp up and provisions to protect existing teachers.

Of course, the devil is in the details. What's an approved program? Can a grandfathered teacher teach all CS classes or just intro ones? etc.

As I said, I haven't had a chance to dive into the details yet but this is very exciting.

Prior to the meeting I was chatting with a few other people attending. One, a UFT representative was very excited about the prospect. Another contingent, a group from NYSUT was very much against a new certification area. Their position was that this would create a teacher shortage because no one would have a CS license and no one would get one due to the difference in salary between teaching and the tech industry. I've already written on how I feel that this is a red herring. What shocked me though was their feeling that "we already have many non-CS teachers effectively teaching CS across the state. They're doing a great job and don't need any additional content or pedagogical knowledge." I think they're wrong and I also think that when we as a community talk about how our summer professional development is all that's needed, we undercut CS education and the teaching profession as a whole.

In any event this was a big step for New York. I tried to individually thank as many of the participants as I could for helping shepherd this along but could only speak to a few so I'll just give a blanket thank you here to the NY State Board of Regents, Board of Education and State Education department.

Making contest problems and writing tests

I'm now well behind in Advent of Code. Traveling up to Michigan to see my son and my brother and his family will do that.

I was planning on working to catch up but got distracted earlier by this thread on the Advent of Code subreddit. Specifically this comment by Eric Wastl, the contest creator. The thread is about the level of difficulty of the various problems and Eric's comment talks about some of the factors that go into creating a good collection of problems for a contest and the difficulties involved.

It made me think of a conversation I had twenty years ago with Rob Kolstad. We were chatting at a programming competition while the students were hacking away. We were discussing that there were only so many questions that a typical high school or college competition can ask:

  1. The Mathy question
  2. Recursion / divide and conquer etc.
  3. Graph stuff
  4. Dynamic Programming

and I think one or two more. The actual questions were just window dressing on these fundamental question types.

You can see this in many competitions including Advent of Code - particularly if you look over all three years. This is not a criticism. I love Advent of Code and think that Eric and the people he's working with are doing a great job . Read Eric's comment to get a deeper dive into what he thinks about as a contest designer.

I also got to thinking how similar creating a competition is to creating an exam. Maybe that's because I'm currently writing the final my students will take in a couple of days. In class tests are certainly not the best of assessments but they do have their place and in any event, they're frequently required by school or departmental policy.

There are many similarities between what teachers consider when making tests to what contest designers consider. What concepts and techniques must the students use? Are the problems too similar? Do they ramp up in difficulty? Are they all or nothing or can a student incrementally work their way to a solution? Does one problem lead into another?

There's no big reveal or surprise here today. Just something I've been thinking about.

A couple of busy days coming up but maybe over the weekend I can get back to Advent of Code.

Tools can shape how we think

I've been having fun with this years Advent of Code 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.

After solving a problem, I like looking over some of the other solutions on the Advent of Code subreddit. 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.

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.

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.

I decided to do this rant as a video. I hope you enjoy it:

Thoughts On A Hackathon

Yesterday I was one of the judges at StuyHacks. A one day hackathon at Stuyvesant run by and organized by the students. I don't have attendee stats but there were kids from all over the city and at least one team from New Jersey. The youngest student that I met was in sixth grade and the oldest were high school seniors. The judging was at the end but I decided to stop by earlier to see how the hackers were doing.

There was an incredible variety of projects using a wide array of tools. There were projects built with:

  • Java
  • Processing
  • C#
  • Scratch
  • A-Frame
  • Python / Flask
  • and more

A personal highlight for me was running into Sophie - the daughter of two of my students from #Stuy95. Well, both a highlight and a reminder that I'm getting old.

The StuyHacks team did a terrific job running things and at the end I told them I'd love to help with future events.

I did notice a couple of things at the hackathon that echo things I've learned as a teacher over the years and I thought they were worth sharing.

The first was the a number of the beginner groups needed more direction. This didn't seem to be related to grade level or age as much as CS experience. This isn't a hackathon only issue. It exists in all learning environments. If as teachers we're too prescriptive students end up with a single formula to follow. Sure, that'll get them through a standardized exam like APCS-A but too much of it can hinder them in becoming creative problem solvers.

On the other hand, not enough structure will leave many kids staring at a blank page. I remember I gave a quiz years ago. It had one problem: "You have 20 minutes to prove to me that you learned something about the past unit on Cellular Autmata" or something like that. Some kids absolutely loved it but many hated it. Stuy kids are trained test takers. They're prepared for structure. This threw many for a loop.

I noticed this issue with some of the hackers at StuyHacks. Some beginners really had a hard time figuring out what they could do and what they should do.

A hackathon isn't a classroom so I think the problem is pretty easily remedied. Groups that were able to latch on to a good mentor seemed to get the guidance they needed. A beginners hackathon should make sure they have not only plenty of mentors but they should make sure that the mentors are prepped with a number of project ideas in a number of the standard beginner platforms. A hackathon could also provide an assortment of ideas in a list.

The second thing I noticed was at the end of the day as I was judging. It started with one particular group. They were pretty apologetic about their project. Basically because it wasn't finished. Personally, I thought what they accomplished in essentially 7 hours was pretty impressive. What became clear as we talked is that this group was deathly afraid of failure. Their deepest fear at that moment was that I was going to give them high marks and they might have to show off their incomplete (yet rather impressive) project to a room full of strangers.

This fear of failure was prevalent in groups that ultimately didn't submit their projects for judging and it seemed to be common among students from high performing, high expectation schools where frequently one associates a test score or grade with ones value. I'm not happy to say that Stuy has always had this problem.

This isn't really a problem that a hackathon can or should be able to address. It's just something I noticed. It's a problem for schools and also for a society that's test obsessed.

I hope nobody reads too much into these observations. The day was a tremendous success. A whole bunch of kids had a great day working together to build cool things with technology. Congratulations to the StuyHacks team. They did a terrific job putting it all together. If you're a middle or high school student or know one, keep an eye on the StuyHacks web page and make sure to attend their next event.

Advent of Code 2017 - Day 1

It's once again time for Advent of Code. That one a day programming competition that's been running now for three years.

Here are some thoughts on day 1. The core of the problem is that you have a large string of digits and you have to calculate a checksum. This is done by adding the sum of a subset of the digits. Only the ones that are identical to the digit to their right. To make it a little more interesting, the last digit wraps around to the first for checksum purposes.

For example, the input 2234335 leads to the calculate 2 + 3 or 5. The input 234445662 leads to 4+4+6+2 or 16. We add 4 for twice because the first four is adjacent the second and the second the third. We add the 2 at the end because it wraps around to match the one at the front.

We first read in the data and strip off the trailing newline

f = open("input.txt")
origdata = f.readline()

origdata = origdata.strip()
data = origdata

Then, since we can access the elements of the string as a list (or array) it's a simple loop to calculate the sum:

s = 0
l = len(data)
for i in range(l-1):
    if data[i]==data[i+1]:
	s = s + int(data[i]) # Don't forget to turn the string into an int

# data[-1] is the python way of getting the last element - here we check the wraparound
if data[0] == data[-1]:
    s = s + int(data[0])
print("Checksum: ",s)

Pretty straightforward but I don't like the special case of checking the last element for the wraparound. Sometimes it's possible to get rid of edge cases like this by changing the data. We can do that here by simply appending a copy of the first character to the end of the list.

This leads to a slightly cleaner solution:

data = data + data[0]

s = 0
l = len(data)
for i in range(l-1):
    if data[i]==data[i+1]:
	s = s + int(data[i]) #don't forget to turn the string into an int
print("Checksum: ",s)

This is pretty much what I'd expect from a Python programmer that's just starting out. We can use a couple of more advanced Python features to make what I consider a more elegant solution.

Python's zip function takes two lists and interleaves them. zip("abc","def") will yield [ (a,d), (b,e), (c,f)]. If the lists are of different length, it just zips up until the shorter list is exhausted. We can use array slicing to zip the input string with it's neighbor by using new_list = zip(data,data[1:]). For the string "122344' zipping gives us [(1,2),(2,2),(2,3),(3,4),(4,4)]. We can put this in a list comprehension that only keeps the tuples representing an element with an identical neighbor and also converts it to an int: new_list = [int(a) for a,b in new_list if a==b].

Finally, we can just calculate the sum. This leads to the following complete solution:

f = open("input.txt")
data = f.readline().strip()
data = data + data[0]

checksum= sum([ int(a) for a,b in zip(data,data[1:]) if a==b])


List comprehensions for the win!!!!

Each Advent of Code problem has two parts. You unlock the second by solving the first. Here, the wrinkle is that instead of checking each digit with it's neighbor to the right, you check it with the one that's halfway around the list.

With loops, the solution is just a quick modification of part 1. We just add half the length and use mod to find the digit to compare with:

f = open("input.txt")
data = f.readline().strip()
data = data + data[0]

s = 0
l = len(data)
for i in range(l-1):
    if data[i]==data[(i+l//2)%l]: # check halfway around instead of adjacent
	s = s + int(data[i])
print("part 2loop version: ",s)

I wanted to see if I could do this with a list comprehension though. The trick was to figure out how to make two lists to zip together to get the pairs to check then add. Here's the solution:

f = open("input.txt")
data = f.readline().strip()
l = len(data)
d2 = data[l//2:]+data
checksum = sum([ int(a) for a,b in zip(data,d2)if a==b])

The insight was that we could just make a second list that starts halfway through and then wraps around. I did this by adding data[l//2:] + data. l//2 is the integer division of the length (in Python3). data[l//2:] represents the second half of data (from the midway point to the end). Technically I should have only added the second half of data: data[l//2:] + data[:l//2] where data[:l//2] gives us the first half of the list but since zip will just stop when it exhausts the shorter list, this wasn't necessary.

Day 2 also has a nice list comprehension based solution. Maybe I'll write that up later.

You have to trust the kids

A week or so ago I wrote about the event we had to kick off Hunter College's partnering with the NY tech community to build a Hunter to tech pipeline. Each table had two Hunter students and a group of tech professionals. Each table discussed the Hunter CS experience and how the tech community can help support the students. Towards the end of the event a colleague commented that it was a great idea to have the students essentially run the tables and how effective it was. I didn't see any other way to do it.

You have to trust the students. Put them in situations where they can grow.

In addition to the event being a success overall, I think that for the students it helped to break down barriers. These kids are soon to be joining the tech community. They'll be interviewing for internships and then jobs and the whole process can be rather intimidating. By the end of the event the other week, there weren't tables of students and professionals but rather tables of people all having discussions on equal footing. It seems like a small thing. A minor choice on how to run an event but it can have a subtle but substantial impact in ways that are hard to see unless you look.

I was also reminded of this when reading Alfred Thompson's post on school tech management teams and CS teachers. Alfred wrote about the possible tension between the needs of CS teachers and the needs of the rest of the school and the obligations of the people that actually set up and maintain the technology in a school.

Years ago, at Stuy, I skirted the issue by taking on the obligation of maintaining my own labs. This let me run Linux and basically do whatever I felt we needed. It also meant my labs wouldn't be set up for things like standardized testing. This came at a price. I had to maintain it all myself. This is not to say that the tech people haven't helped over the years. Some of them have been terrific but other than swapping out bad machines it all fell on me.

Of course this wouldn't have been possible if it really all fell to me. It only worked because I was able to enlist the aid of students who wanted to learn about building and running a Linux network. Sure I showed them some things but largely we figured it out together. Basically I trusted the kids with access and control and gave them a safe place to learn and explore.

It worked amazingly well.

Of course there were plenty of headaches. There was the time when we only had one AI/X server for the school and Jon somehow erased all the shared libraries or the time when I think Paul or Ilya took away read and execute access from all the system executables. I lost plenty of sleep and pulled out much hair recovering from these messes and others but I couldn't get too upset. They were learning, no one got hurt, and truthfully they never committed any blunders worse than my own.

Giving up control to the kids can be nerve wracking at times but it's worth it. It's why I always found coaching more stressful than competing back when I fenced. You can do everything to prepare your athletes but when they're out on the strip, there's nothing you can do to help. It's all on them. On the other hand, I've always been more gratified with my athletes or students successes than with my own. There's something special about enabling others.

This is not to say that we just turn our students loose. We have to set our students up to succeed. Set up the environment and the circumstance and give the students the tools to work with. At the event two weeks ago I knew that everyone in the room was a friend or when I have students plan a hackathon and have them cold call a company, maybe the company expects the call. There are all sorts of things we can do behind the scenes to set out students up for success.

We set the stage and if we do it right, the kids won't fail to impress.

Reunion Season

Thanksgiving is reunion season. Stuyvesant and I'm guessing other high schools traditionally hold their reunions, at least the five and ten year ones over the holiday weekend. It makes sense since grads who've moved away might still be coming to town for family celebrations.

This year, I was invited to the Stuy07 ten year reunion. I considered crashing the Stuy97 20 year but it was at the same time and too far away.

I'm always really flattered and honored when I get a reunion invite. I've been to my share but I was never the hip popular teacher that gets invited to these things. On the other hand, I'm sincere, honest, and loyal so when I do connect with students it's meaningful and lasting. As one of my students remarked when I was nominated to be graduation speaker a few years ago and I doubted I would be elected "hey, you lead the most popular cult in the school" and I guess in some way the community is a cult, or as I'd rather say, a family. In any event, whenever I'm invited to a reunion I make my best effort to attend.

I find the role of faculty at reunions as somewhat amusing – we're something of a prop. The grads are there and should be there to reconnect with each other. The teachers are and should be secondary. From my point of view, there are three groups of students. The ones that are now part of my alumni family - now friends who I'm in touch with to varying degrees, the ones that never knew me and the ones that knew me a bit. For the second and third groups, as a faculty member, I'm there to remind them of the glory days as a representative of the institution.

As with all reunions I had plenty of "I was never in your class but …" conversations. I also a number of "I majored in fill-in-the-blank but just found my way back into tech so….. thanks." I love these conversations - it gets someone new into "the family." I also had one conversation that was really a nice ego boost. One of my guys introduced me to his wife. She immediately exclaimed "it's so great to finally meet you, he talks about you all the time!" That was kind of weird until she went on "…every time he talks about Stuy." That made more sense. It's like all those times when me and my buddy Ben would reminisce about our Junior High school days and we'd always get back to talking about Herb, one of our best and favorite teachers and a major influence on me while Devorah looked on confused. Eventually she met and got to know Herb and it all made sense. Another grad added "you think we all forget about you but you come up more than you know" so I take that as a shout out to all of the teachers out there who never get to hear back about how much they are remembered and appreciated.

With tools like email and Facebook it's easier to remain connected to former students but it's always nice to connect in person. For the StuyCS family, we have our periodic meetups but for the rest, I love being included in class reunions and hope to be invited to more in years to come.

Using Emacs 38 - dired

The 38th installment of Using Emacs is about dired, Emacs' built in mode for navigating and working with directories.

I'm not a dired power user and in fact am just now making a real effort to explore it and work it into my daily workflow and with that in mind, I'd love to hear some configuration and use suggestions from people who use it regularly.

Here's the configuration I use:

(use-package dired+
  :ensure t
  :config (require 'dired+)

which merely adds dired+ into the mix.

I also started playing with pcre2el which allows me to use the more usual regex syntax in place of Emacs regex syntax in both dired and other places. This is a big win for me since I never remember all the escaping rules for Emacs regex.

(use-package pcre2el
:ensure t

Finally, abo-abo and jcs have both written about new features in , Ivy/Swiper/Counsel that allow you to use ivy-occur to dump results into a dired buffer (link, link) but to get that to work, I needed to install wgrep and also had to install and setup fzf which looks to be useful.

  (use-package wgrep
    :ensure t

(setq counsel-fzf-cmd "/home/zamansky/.fzf/bin/fzf -f %s")

To help get started here are links to a couple of cheat sheets:

I'll probably use dired more frequently but again, would love to hear how other people are using it.

Motivating and understanding quicksort

Thks question was posed the other day - how can one get students to truly understand the quicksort algorithm?

I've written a few posts about quicksort. The last time I did a lesson writeup on the subject I wrote about first looking and quickselect and then moving to the quicksort. The class was first faced with the problem of writing a routine to find the Kth smallest item in an unsorted data set. The first solution was n2 and then refined to a quickselect. This led directly to the quicksort.

I liked the lesson and I think it worked well when I taught it but that was partly due to the overall tenor of that particular group of students.

A similar approach develops the quicksort in a similar way but is both more direct and accessible.

The motivating problem is to put one item in a data set in its proper place. You could select one person in class and arrange the class so that the selected student is in their proper size place, that is everyone shorter on one side, taller on the other. You could also do this for age. A similar exercise could be done with any number of manipulatives.

This operation of arranging the rest of the set around one selected item or person is very easy and in fact it's trivial to show that this can be done in linear time.

Once we've done this arrangement, we can discuss what we can infer from this new arrangement. We can now tell that:

  • everyone to the left of the "pivot" is less than the pivot
  • everyone to the right is greater
  • The pivot element is at its true location if the list were sorted. That is, if we started arranging around item k, then we've moved item k to the kth location in the dataset.

From here it's a small jump to the quicksort algorithm, just repeat the process on the left and right data sets.

This approach not only makes the algorithm and its development clear and simple but it also can be used to illustrate the worst case n2 behavior.

The whole thing, minus the coding, can also be done as an unplugged activity.

In case anyone's interested, I also wrote a post on subtle implementation errors when writing the quicksort (here) and also looking at the qucksort from the point of view of different programming paradigms (here).


Enter your email address:

Delivered by FeedBurner

Google Analytics Alternative