Drawing (a) Circle at City College San Francisco

This is my second semester being an instructor and professor for the Introduction to Java course at City College. The classes are currently being taught mostly with material made available to me by Craig Persiko. I mostly come up with exam questions but follow a variant of Craig's in-class teaching structure.

One of the things we do is have in-class exercises immediately after the introduction of a new topic. For example, if we introduce Arrays, then we'll have an in-class exercise immediately afterwards to get students familiar with the concept of declaring, initializing and using arrays. We might go over a particular topic several times with progressively more difficult in-class exercises. This semester, we managed to cover arrays as well as the concept of sorting algorithms. In class, students learned how to implement Selection Sort. On an exam question, many of them implemented Bubble Sort on their own and then explained the difference between the two types of sorting.

In class, I try to make all of the concepts accessible. CS111A Introduction to Computing in Java will be phased out in Fall of 2018 and replaced with Python. I emphasize in class that students should not be focused on the syntax of the languages but rather the more abstract concepts being introduced. Toward the beginning of the course, this is more difficult as many of them are being introduced to what a programming language even is for the first time. However, as the course progresses and concepts like Boolean expressions, DeMorgan's Law and Logic Operators are introduced, I am surprised again and again by the ideas that fresh minds come up with.

This semester, I had an absolutely beautiful moment in class during the last planned lecture covering 2D Arrays. Typically, I talk for only a short amount of time (<30 min) before breaking off into the in-class exercise. During this class, the in-class exercise involved simply writing out the code for initializing, declaring and creating a 2D array which would represent the pixels drawn to a screen. Using a 2D array, students had to draw a grid like so:

Col# :	0 1 2 3 4 5 6 7 8 910111213141516171819
Row 0:	1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 
Row 1:	0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 
Row 2:	0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 
Row 3:	0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 
Row 4:	0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 
Row 5:	0 0 0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0 0 0 
Row 6:	0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 
Row 7:	0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0 
Row 8:	0 0 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 
Row 9:	0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 
Row 10:	0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 
Row 11:	0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 
Row 12:	0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 
Row 13:	0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 
Row 14:	0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
Row 15:	0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 
Row 16:	0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
Row 17:	0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
Row 18:	0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
Row 19:	2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 

This didn't take too long to do for a small group of students in the class. Usually, about 1/3 of the class finishes quickly and need an extra challenge. 1/3 of the class finishes around the allotted time and the last third of the class waits for me to go around and help them out in some way to get something basic working. In this particular class, the extra challenge I gave was to animate the "X" in the pixels display by simply redrawing on a timer.

This is what I suggested. On this particular day in class, however, a student named James quietly said that what he'd like to do was to draw a circle rather than a "X" in the square. I thought that was pretty exciting and encouraged him to do that. Another student with some foresight, Arhan, commented that this would be quite challenging to do within the allotted class time and when she mentioned that I agreed with her.

As I continued milling around the classroom helping the other students complete the base exercise, I noted that Griffin had finished his exercise and had overheard James' self-defined challenge. Griffin is bright and I encouraged him to help James and Arhan complete the assignment in the twenty minutes left in class.

Well, Griffin immediately took initiative and began brainstorming ways to use Pythagorean theorem to define constraints for drawing the circle. Not long after that, Vernon, who normally finishes in-class exercises fairly quickly and chats with neighboring students declared he was also done. I asked him to get to the computer at the front of the classroom and share his solution to the base exercise with the entire class. I was completely floored by what happened next.

Vernon clearly explained his solution to the base exercise to the whole class using the projector screen. Griffin then went to the front and explained the challenge that James had proposed and was quietly working on. I looked around the classroom to see if anyone else had demonstrated any interest in the extra challenge and was hoping that one of my other bright students Zach was still around. He had asked me earlier if it was alright to go and take a nap. Of course, per my nap policy (i.e. you should never be ashamed to take a nap), I had dismissed him. In hindsight, I wish he had gotten to see how his classmates finally came together with him to solve a very challenging problem.

Griffin explained the ideas for drawing a circle in the square grid. Vernon, who was still manning the computer, suggested defining the center of the circle. Griffin quickly took to that and suggested an if statement using the i and j indices of the grid. Vernon, in real time, wrote down his ideas. As the rest of the classroom started paying attention to what it was they were trying to do, a couple students threw out some ideas. And, within a few more tries, collectively, they come up with a simple if statement:

if (i^2 + y^2 == r^2)
  draw marker
else
  draw filler

Vernon massaged the ideas a little and soon a square-ish circle showed up on the screen! I was so happy that they had gotten this far and had not expected this to happen during class. Meanwhile, James was quietly working on his own solution which he subsequently shared with Arhan to share during the following class.

At this point, with not much time left in class, I mentioned that this was probably as close as they were going to get to drawing a circle but had already way surpassed any expectation. Griffin, however, would not let go. He continued to think about it and take in suggestions from the classroom who also did not want to let go. In the end, Griffin said, OK, just draw a thicker outline of the circle. Better yet, change the "==" to a "<=" and fill in the circle. Fair enough. Filling in the circle does make it much less spiky.

With just a couple minutes left of class, I pointed everyone to Brezenham's algorithm and/or Wu's algorithm which addresses the anti-aliasing problem in real time. I explained that the anti-aliasing problem doesn't exist just for a circle. Even if we were just trying to draw a line with different slopes, we would still have the same problem of choosing which pixels to draw in to get a smooth line. Try searching for Shivam Pradhan's explanation of drawing a smooth circle. Google led me to a solution at Geeks by Geeks.

Not too shabby for a one-semester long Introduction to Computing course!

Written byadmin

Documenting makes the mundane seem interesting. Interesting matters seem to demand attention on their own.