How to learn computer science from bottom to up?

Yes, it is possible to do that, but it is terribly inefficient. It will take you approximately forever, partly because it is no longer true that any single person can now understand all of Computer Science. The boundary was passed somewhere around the turn of the century, just as in mathematics it happened around the turn of the previous century.

If you start from the very beginning, ignoring everything that came later, you will deny yourself the possibility to benefit from the big ideas that developed along the way that the history followed. One of the biggest ideas in computing is the idea of abstraction and understanding that buys you a lot in understanding and also in guiding your learning.

A Turing Machine, just like pure Machine Language, has no abstraction facilities whatever. Assembly language adds a bit. Fortran and Cobol added more. But it was the Algol family of languages that really solidified the importance of abstraction and it was languages like Lisp and Smalltalk that extended it to modern levels of understanding. But if you have a good understanding of abstraction, such as you would learn from programming in Java or Python, then you can more easily move down to simpler (less abstraction) languages and move upwards to higher levels (database, AI, etc).

I think you have a misunderstanding, actually, and are conflating Computer Programming with Computer Science. They are not the same. Programming at a high or low level is just a tool for understanding more important and more interesting things. (I'm not claiming you have this misunderstanding, but your question leaves hints of it, at least.)

Most students of computer science start with some high(er) level language, often Java or Python. From there they move up and down the abstraction scale. I've built (finite) Turing Machines and explored them deeply when studying Algorithms. But I didn't start there. I'm old enough that Fortran and Basic were my first languages. But then Pascal taught me about a certain kind of abstraction (procedural) and later Smalltalk taught me object abstraction.

I've never built a full OS, but have built a kernel. A micro kernel is really only a few lines of code, actually, but to understand that you have to take a layered view of an OS (abstraction again).

I've built a lot of compilers, but always in higher level languages (C and higher). I've built editors, but not text editors. Graphical drag and drop editors are more interesting in today's world. Think Scratch, though that wasn't me. But my higher level view of what constitutes a program (abstraction) enables me to build any of those things as well as future things for which the need might arise.

So, again, while a purely historical, low level to high level, approach is possible, it isn't, in my well-formed and long-held opinion, the best way. In particular, you don't have to independently re-develop the idea of abstraction to become a good programmer and to use abstraction effectively to get to the "interesting" things.

But that is just the programming part. There is much more in Computer Science and you won't get to that soon enough if you recapitulate the entire history of computing.


How to introduce problem solving to primary school pupils?

I have taught problem solving to older learners who studied a range of diagnostic, design and contingency problems. I'm not sure what age group you are talking about which would be handy to know in answering this question.

This is a diagnostic group activity solvable using informal constraint satisfaction.
https://sites.lsa.umich.edu/inclusive-teaching/2017/08/16/who-owns-the-zebra/

Planning activities also work well, surely there will be an end of term party to plan?


Significant algorithm from CS for DrRacket that emphasize cons, car, and cdr

I learned Racket using the material taught by the UW MOOC on Coursera Programming Languages, Part B, which is modeled after this UW course.

Here are the relevant helpful documents, which do provide an introduction to the language along with quite advanced material which involves implementing a programming language within Racket:

Notes for Unit 5 and Unit 6
Homework 4 and Homework 5

The materials in this course are heavy on recursion, so some of the earlier exercises in Homework 4 may help your students with this concept while getting them comfortable with basic Racket exercises.

I also can't speak highly enough of the free, self-paced course materials for UC Berkeley's CS61AS found on the "Textbook" tab.

These two additional resources may spark some ideas as well:

Example programs in Racket
A* Search in Racket (this relates to one of your other posts as well - two birds with one stone?)


First, there is a scientific journal that may include publications of such material that are what you are looking for: The Journal of Open Source Education, "An educator friendly journal for publishing computational learning modules and educational software."

Second, but I am not sure this is completely relevant to your question, there are the open source computational lesson from The Carpentries:

Software Carpentry has lessons on the unix shell, version control (git and mercurial), programming in Python or R, R for Reproducible Scientific Analysis and more
Data Carpentry has lessons more tailored to a research domain, on data analysis, but includes programming as well
not yet part of The Carpentries, but under development is HPC carpentry lessons: shell, Python, Chapel, Snakemake
there is also Library Carpentry, but their lessons are more tailored to librarians

All these lessons are CC-BY.

Disclaimer: I am on The Carpentries Executive Council


What's a good initial lesson for teaching arduino?

My preferred lesson, using any board that has servo headers (and you can do it even without these), is to show them how to make a servo turn (I have a wheel attached to it ahead of time).

The program is fairly easy to follow for students, and there is a look of shock when it starts moving. I then tell them that they need to attach the servo along with another one to a box, and make a robot that drives forward, and they will need to add three lines of code to their program.

The challenge of adding the three lines is just different enough from what they have, that they will struggle, but similar enough that they can figure it out.

I then introduce the delay command and tell them they need to program their robot to drive around a big box.

This takes about an hour and a half if I prebuild the robots and it is just programming. If they are building them, add at least another 30 min.

The nice thing is that this acts as a great starting lesson to lead into others. Later you can give challenges that require sensors and introduce conditionals. Serial Communication can be used to make them remote control (works better if you have a board with blue tooth communication).

Depending on your budget there are some arduino robot kits starting around $80 that I think are a good value.


A real world example for the divide and conquer method

Back around 1985, Susan Merritt created an Inverted Taxonomy of Sorting Algorithms. The idea is that to sort an array you have two phases, the split phase and the join phase. She divided the various algorithms into two types easy split/hard join and hard split/easy join varieties. Merge sort is of the former type. Quick sort is the latter.

But all sorts, envisioned in this way are divide and conquer. Her original paper (part of her doctoral work) is a wonder and worth exploring by any CS teacher.


Show them the cool stuff they can do with Scratch.

Don't focus on explaining that they can't make a AAA game. Focus on showing them examples of stuff that is engaging and interesting, that they can do with Scratch. Come up with a showcase of interesting programs. Make sure your assignments are engaging and interesting.

Taking a step back, I'd also recommend you give your students the benefit of the doubt. Don't come in with an attitude that assumes they only care about modern video games and smartphones. Connect your lessons with stuff they do care about. Have them draw a scene from their favorite show, or have them make a game or animation about their friends.

And taking another step back, the age range of your students is very high. A 6 year old and a 16 year old are very different. I'm not sure Scratch is the right choice for 16 year olds. Maybe try something like Game Maker or Processing? I've mentioned Processing in a bunch of my other answers, and I'd be happy to talk more about it with you if you're interested.


How can I improve my understanding in Computer Science?

Abstract definitions are a deep rabbit hole. To illustrate the point:

First attempt

Imagine a non-English speaker trying to read the dictionary. First word: Aardvark. A nocturnal badger-sized burrowing mammal of Africa, ...
Wait, what does nocturnal mean? Done, occurring, or active at night.
Wait, what does occurring mean? ...

And this is the core of the issue: you end up with an ever-growing web of definitions composed of words whose definitions you don't understand. You've already had to look up more than three words and you're still not quire sure what an aardvark (the first word) is!

Second attempt

Let's try again. You're learning English because you want to work as a chef cook in an English speaking zone. You're going to be a pasta chef, so how about you look up the translation of dishes you know how to make. Afterwards, look up the translation of the ingredients you use to make these dishes.

Why was the second attempt so much more succesful? Simply put, because you were looking up the words that belong to a concrete concept you already know and understand.

  When I read about it words like 'parsing'

When you look up what parsing is, you will get some vague and generalized definition. The dictionary isn't much help here, even when looking at the computing definition. Google tells me:

  [COMPUTING] analyse (a string or text) into logical syntactic components.

This definition won't help you if you've never done any parsing before, or you haven't even thought about doing the act of parsing (even if you didn't know that it's called parsing).

So let's approach this from the other way: You are writing an application, and the users expect to be able to upload an excel file so that the data from the file can be saved in your application('s database).
How do you do that? Well, you will have to open up the file, look at the content of the file, and then add this data to your database.

Now you know that, it will make more sense what parsing is: parsing is making sense of the content you receive.
This can take on many forms, not just the reading of excel files. For example, when you ask Siri (or Alexa, or the Google Assistant) a question, it parses your sentence in order to understand what it means. When your web browser receives HTML from the web server, it parses the HTML in order to figure out what it needs to show to the user. When you load a savegame in a videogame, the game parses the save file to know what your last saved game state was.

So how do you learn computer science concepts?

The general rule is to approach it from a practical side. First, you try to accomplish something. When you struggle accomplishing it, or you want to read up on doing it even better; you will be able to look at the documentation and will already understand its inherent goal or what it adds.

For example, I am horrible at trying to understand new frameworks by reading the documentation or even seeing it presented. I learn much quicker by trying to use this, obviously failing because I don't know how to do things, and then look up how to do [simple thing, e.g. make the text bigger] in this framework.

By using this practical approach, my search for information is a directed search (like the chef looking for the translation of a dish he knows), as opposed to an abstract search (learning random words in the hopes that you'll want to use them in the future).

I'm not saying abstract searches can't be interesting. We've all spent some times clickbrowsing through Wikipedia or TV Tropes to find interesting things. But the abstract nature of computer science makes it hard to innately understand something you didn't know about before.

The best science teachers I've had always employed a similar strategy. At the beginning of the class, they pose a seemingly simple question, but the students are unable to actually find the answer. And only when they're curious about the answer to this question, the teacher starts to explain how to find the answer.

Other resources

The above answer is written in regards to your desire to self-learn. Of course, there are better ways of learning CS through courses and lectures. These courses are specifically designed to introduce concepts to you in a way that you understand them.
When self-learning, it's hard to know where to start and to separate the simple topics from the complex ones.

This is part of your issue. E.g. "parsing" is by no means a beginner topic. But if you had already learned the basics of file manipulation, collection (and preferably some OOP), the concept of parsing would've been a lot easier to understand from the get to. This is where guided courses help to, they ensure that you learn the necessary basics before starting on the more complex topics.

As an aside

  I was given a problem of image processing yesterday by the seniors in my company

I don't mean to offend, but if you're currently struggling to grasp what parsing it, you're way out of your league of broaching the topic of image processing. There seems to be a huge disconnect between your current skill level and the tasks you're being given.

Whether you're in over your head at your current job, or your seniors are oblivious to your technical skill level, in either case I suggest being open about what you do and do not yet grasp. Trying to tackle complex subjects without the necessary basic skills is not only going to take a lot of time and effort, but it will inevitably teach you some bad habits because you will be unaware of alternative options.


Is it better to lie to students or to be pedantic when teaching Intro CS?

Lying is good. But advertise it when you lie. Make sure students make a note of it that you are lying.
Pedantic is bad. If you try to explain everything you will wind up explaining nothing. Let me take a simpler example. In java we have a special incantation
public static void main(String [] args)

We put it in every program. It distinguishes a program. But if you start your java course explaining every part of it you will (a) confuse the juices out of them and (b) never get to the point of writing a useful program. For the beginner, it is just an incantation like
Riddikulus; // used in defence against a Boggart.

The Java code is just a "charm" for the beginner. All you need to say is that it is a "hook" for the OS to find its way into your program. Explain it later after you've taken up some of its elements for other purposes.
Beginners need a simple but coherent view of their language and system. When you simplify, work hard to keep it consistent. But it doesn't need to be complete and certainly not exhaustive.
When you are giving an "overly" simplified view, say that explicitly. Have the students mark their notes with an asterisk (or the above charm) so that they know it isn't complete. If you are explicitly asked for "the rest of the story" you have to decide whether it will help to include it (after the commercial break, of course) or to defer it or to enlighten the students out of the class context (email, say), or give a reference for those who "will not be denied."
I used to start some discussions with "I'm about to lie to you, but it will be helpful if you accept my lie for a bit". Of course I had to remember to come back an fill in the blanks  later, but it might not be for a while. Complex, inter-dependent topics are like that.
tl;dr: Lie, but honestly and truthfully.
And, perhaps the most important caveat, don't lie in such a way that the student later needs to unlearn something. Lying is giving partial truths, or temporary world views, not sending students into mental blind alleys and backwaters. Withholding some facts may be necessary and valuable as is presenting an incomplete metaphor. UnLearning should never be part of learning.
I'll also note that infants learn to speak a native language without everything being explained to them before they begin. The deeper understanding comes to them only gradually and over time. We are actually conditioned by evolution to work this way.


What does a person with an undergraduate degree in CS still need to learn to be employable as a developer?

To know that you know nothing.
Recent graduates can be afflicted by arrogance or low self worth. These are two sides of the same problem.
It is important to know that you are at the beginning of a journey, that has no end. The sum of all knowledge that is known, is but a drop in an ocean, and your personal knowledge is but an atom.
However this has not stopped other such as Turing, Lovelace, Hopper, Ritchie, Liskov, Stallman, et al; It has not stopped you in the past; and it will not stop you in the future.
Experience
I have heard many a new journeyman say “To get a job I need experience, but how do I get experience without a job?”.
So get experience: Find a good Free Software / Open Source project, that you are interested in, and contribute to the project.
Software engineering tools
As well as testing (@BenI). Revision control: Learn how to use revision control tools, for example: mercurial (hg), git, subversion (svn).
Of these subversion is previous generation, but still has some use-cases that best suit it. It is still widely used.
Mercurial and git are more modern, distributed systems. git is the most popular, but is a git to use, and very hard to learn. Mercurial is similar in how it works, but much easier to use (it has a more intuitive command line interface, and a nice graphical interface(tortoise hg)).


Introducing self containing objects (Node)

The sample is not "defining something with itself." Rather it is defining two different kinds of things.

The first line: public class Node<T> { is beginning the definition of a template for things to be made later. That definition will be handled at compile time. The third line: Node<T> next; sets up an object that will be instantiated using some template. Later in the compile process, when the object is created, Java will look in the table for the template called "Node" that can handle some type. Since, by then, the complete template will exist, there's no problem. The key point here is that next is not a template, it is object that will use the Node<T> template when it is created.

If you also define public class Node2<T> extends Node<T>, then at run time, next could refer to the template Node<T>, or the template Node2<T>. Exactly which it is will be determined when the next object is instantiated.

If it hasn't already been covered, that would be an opportune time to cover early and late binding.


I have a few thoughts on this topic. One is a couple ideas about how quizzes could be implemented (if you choose to use them), and the other is some more general thoughts on the tactics that I use to solve problems like this.

Quizzes Without Extra Grading

What are your opinions on peer grading or self-grading? I've seen both work nicely for things like this (short, low-pressure quizzes that aren't too hard).

They require a little bit of logistics, since each student needs a normal colored pen and a "grading" pen, and it's easiest if you supply those. Then you require that normal pens are collected before grading starts, and that students do not have their own writing implements out, and it typically goes well.

This would require you to put aside more time during class, since a 5-minute quiz takes at least an additional 5 minutes to grade.

The pro of students grading their own work is that it becomes a way of reflecting and learning from the experience. If they get a question wrong, they get immediate feedback about the correct answer.

Alternatively, you might want to look into giving digital quizzes. They would have to be multiple choice or fill in the blank, but they auto-grade, saving you the time. I know that Google Forms has a method of doing this, and there are a bunch of other platforms too. Your students could take the quizzes on their phones, or computers.

This system tends to be quick and you can integrate it into the entire lesson, not just the end. I had a professor in my undergrad who would lecture for a bit and then pause for us to answer a question or two. Before continuing. It was her way of doing understanding checks. You could easily establish small point values for each question so that they "count."

To Quiz or Not to Quiz

Personally, I've found that increased examination does not tend to increase student attention. I theorize that there are two reasons for this.

First, many quizzes happen "later" - either at the end of class or even several days or weeks later. Most students (especially teenagers, although adult students as well) have trouble remembering potential consequences that seem far off. If the exam is important enough to overcome this problem, then it's probably invoking some level of anxiety or fear, which is a large detractor from student focus and engagement. It may solve your problem of looking like your students are paying attention, but I believe that it's unlikely to actually increase their learning.

My second theory is that people tend to believe that they are better at multitasking than they are. If you gave an anonymous poll to your students and asked if they ever do work for other classes during your lectures and how much attention they pay to your lectures, I would bet quite a bit that they all feel that they are always attentive, even though you know that not to be the case. Thus, saying "Oh, it's very important to pay attention!" seems unlikely to change behavior because they really believe that they are/can pay attention while doing other things.

So, what are the other options? You could do the honest but maybe frowned upon thing of talking to your students and saying "hey guys. I know you're busy. I know you sometimes finish up other homework while in this class. I'm mostly fine with it on occasion; as long as you get your work done and feel like you're learning what you want to learn, I don't really see a problem. But it makes us look bad when a senior teacher/dean/etc. sees you doing that. So we have some options. I can change something about the way the class is structured (quizzes, etc.), or you can keep the distractions to a minimum, especially when we have guests." Whether this will work mostly depends on your students and your relationship with them. It also obviously depends on the institution you teach at.

A Non-Quiz Suggestion

You've mentioned that you're already putting a lot of thought and work into every lesson. So this might not be a solution that seems feasible. But my personal strategy for student engagement is to keep the students active throughout the lesson. I try to talk for 5-10 minute chunks, broken up by having students work through practice problems or explore ideas. Maybe you can take your current activities and spread them out a bit more throughout the lesson? If students are changing tasks frequently, it will be easier for them to stay engaged and harder for them to pull out something else to become involved in.

If you want more concrete information on what this could look like, pick an example lesson and post another question. I'm sure that lots of people will have a wide range of ideas for active learning.

I hope some of these things help. Good luck!


How to teach the importance of indentation

It has taken me a long time to get to a point where my students regularly indent properly.  I basically use a 4-part strategy.  (My work here in the context of AP Computer Science, so my examples are all in Java)

First, right from the beginning, and repeatedly, I talk about the two audiences for code: the computer and people.  These two audiences have completely different needs.  I come back to this theme with every new structure that I talk about, discussing coding style and norms with if statements, variable declarations (naming conventions), for loops (hey, why do we avoid break statements?), etc.

Second, I grade most of their labs right in front of them, code-interview style.  The first assignments are always quite simple, so I focus in on indentation, variable names, vertical space1, and the four Cs: clarity, clarity, clarity, and clarity.

I talk through the clarity of their code in depth and inflict outrageous penalties for unclear code, but allow them to go back and refactor for a better grade with no penalty.  Rinse, lather, and repeat (as needed).  The first lab is always painfully time-intensive to go through, but by lab 3 or 4, much of the code (and the grading!) is fast, smooth, and clear.

Third, I provide a few monstrous code examples throughout the year like this:

int n = 17;
if (n < 5)
if (n > 10) System.out.print("A");
else System.out.print("B");
if (n > 17)
if (n == 17) System.out.println("C");
else System.out.println("D");
else System.out.println("E");

It doesn't take a rocket scientist to figure out that poor indentation is the one and only reason that this code is so difficult to read and understand.  In case they miss it, I also reinforce this point verbally every time I give examples like this.

Fourth, the group work that I give requires them to have to provide code to each other, and make sense of what their peers have done.  Over time, they start enforcing norms on each other.

1 Vertical space, you ask?  Two reasons: first, because vertical space is used to separate ideas, like paragraphs, and second, because the very mention of this problem in their code shocks students immediately into thinking about how everything that they write helps to serve clarity.


How to teach sums and asymptotics to students who don’t know limits

For asymptotes in general, one of the easiest examples for beginners is the curve $y = 1/x$ which has asymptotes (at infinity) on both axes. It is easy for them to see that as x gets large y gets small (without bound). Likewise as x gets small, y must get large. You could then look at $y = 3 + 1/x$ for example to see a different horizontal asymptote. Contrast this with $y = x^2$ for an unbounded function and also with a periodic function (sin or something informal that looks like it), that is bounded but has no asymptote.
If you want to go farther, you could discuss a chord and a tangent on a circle. Move the chord parallel to itself and see the two intersection points with the circle converge until you have a tangent parallel to the original chord. This may be more than you want or need, of course.
For infinite series and sums, one of the easiest examples is to first discuss Zeno's Paradox and the sequence 1/2, 1/4, 1/8, ... and its sum. It is pretty clear if you draw the picture that the sum is one and that the difference between a partial sum and 1 is the most recent term in the series. It is also easy to see how to generate the next term.
If you are teaching programming, you can write a program that computes partial sums, but if you do so with floating point then you also need to discuss rounding error, which will get severe, since the sum gets larger as the terms get smaller. Eventually, then, the next term adds nothing at all, due to the fixed precision of floating point data.
But if you want to compute the partial sum in closed form then you can do better in a program to compute that rather than the sum itself. That may be too much to ask, I realize.
That may be enough, but it gives enough of the overall concepts to get you started. And Zeno is always fun in any case.

Here are a few more "interesting" functions that may go beyond what you need, but have interesting things to teach you.
Once you understand what $f(x) = 1/x$ does, you can combine it with other functions to get other sorts of asymptotes. For example $g(x) = x + 1/x$ is asymptotic to the function $h(x) = x$. In that form it is pretty obvious what it does, but less so if you express it as $g(x) = (x^2 + 1)/x$.
Other combinations are possible. If you look at $k(x) = (1/x)*\sin(x)$ you get a function that oscillates but is also asymptotic to zero at infinity.
One of my favorite functions is $m(x) = (1/x)*\sin(1/x)$. As x approaches infinity, this is asymptotic to zero also, but it is much more interesting as x approaches zero. It has the property that it takes on every real value infinitely many times in every neighborhood of zero. The 1/x factor gives it increasing amplitude near zero and the argument to sin makes it oscillate faster and faster. This is a very strange property for a real valued function, but if the student will eventually study Complex Analysis it is an exceedingly important example. I'll leave that explanation for the next course.


Students can solve programming exercises but not explain their solutions. What to do?

I have seen my share of this 'program gets output' but the programmer has no clue how she/he got there. It's funny how that happens so many times.

This is what I have done to at least handle the issue.

Before assessments, I break down the evaluation to include the following.

Simply getting the output gets them the bare passing grade.
Those who can use meaningful names for their variables, function calls get extra.
Those that can back up their loops, method calls and variable declarations with expansive ( 2 to 3 lines at least) comments get extra points.
In addition to that, those that can write psuedocode above the program code (perhaps in a big block of comments) get some more.

Obviously, this makes me their least favourite faculty in terms of evaluation and gets me a lot of complaints but I stick with it.

Update : Please note that, during evaluation, I don't expect all of them to be done. Say, a student is already using meaningful names everywhere, I would not mark her/him down for not writing comments.


This answer will be general, rather than specific to your proposed curriculum. Since you note in a comment that it is set theory that you want to stress over Racket programming, I'll suggest the following.

First, it is difficult to advance students on two orthogonal axes simultaneously without confusing at least some of them. Therefore you want to put the stress on set theory and its beauty and limitations over the programming aspect. If you were using a language that they already knew well, I'd make a slightly different suggestion.

But first, give them a good, traditional, view of set theory and how it relates in general to modes of thought. Any good book, even if it doesn't mention programming at all, could  be used, even Naive Set Theory by Halmos. Use programming primarily to illustrate things in a simple way so that the functional programming doesn't take up too much of their thought space - just enough to get the flavor of, for example deep recursive programming.

The programming exercises can be quite simple, but I would choose them in such a way that they also serve as an introduction to complexity theory and the problem of growth. Something simple with Cartesian product and many dimensions can illustrate the growth. It is also possible to write functional programs for things that seem simple but have terrible run-time. For example, a naive version of reversing a list can easily be quadratic if care isn't taken.

I don't know what libraries Racket offers for support of sets, but it might be useful to talk about the development of such a library - building a tool box of simple set operations.

But, in the main, use the programming as a way to reinforce the theory, not so much as an end in itself. Set theory is rich enough and with enough applications to math and CS that you don't really need to do much more.

If you really want to teach FP in Racket, then a different set of exercises that help the functional thought process develop would probably be better than trying to force it into one realm.


What advantages do students who learn how to touch type have?

Actually, there are a lot of things that benefit a student in CS, such as a degree in Mathematics or Sociology. Likewise interpersonal skills that help a person work in groups. Others are too numerous to mention.

However, a true prerequisite is a block, preventing advancement if you don't have the skill, so no, it should not be required.

Some data points. I was lucky enough to take a course in touch typing (on a typewriter) in about 1960. I was the only boy in the class intended for girls who would likely become secretaries. Not especially enlightened, of course. But touch typing has benefited me most in writing rather than in programming, and any CS professional writes a lot, even if they aren't book authors. But there are technical reports, grant proposals, system documentation, etc. that makes typing skill useful.

On the other hand, I know a lot of professionals, who are also authors, who still use two or three fingers to type and it doesn't inhibit them. The world would be a poorer place if they were prevented from entering the field for the lack of such a low level skill.

Also, modern hand held devices don't adapt well to touch typing. On a phone, I usually use just one finger since the keys are too small and my fingers are too big for me to use even two fingers.

But, students should be encouraged to type effectively, of course. But not as a block to advancement. Students should, of course, also be encouraged to develop good handwriting skills so that they can read their own hand-written notes. But that skill is being lost, unfortunately.

tl;dr: Prerequisites should be required only for required things, not just helpful things.

I'll also note that it isn't typing that makes programming hard. Neither is it typing that makes writing hard.

But if a student's typing skills are so bad that they seem forced to used extremely short and uninformative names for entities, then they need to improve. Readability is required.


How to create webpage slides for teaching?

pandoc can convert slides written in markdown to a html presentation using reveal.js. pandoc can go markdown->latex (beamer) too. Not sure about going latex->reveal.js but it could be possible.


Analogy to teach beginners the concept of interrupt

Fire alarm goes off during exam.

Nasty uncle Ben shows up in the middle of supper.

Tire blows out while driving.

Student raises hand during lecture.

Baby wakes up in the night, screaming.

Anything in general, that happens without warning and that requires attention or action of some kind.


Is it worth it for high school teachers to join SIGCSE?

Yes! (with some qualifications.)

Benefits (most apply to conference attendance):

connections with other teachers to share ideas and experience
research results on CS teaching practices/methods
TIME away from class to reflect and plan
broader perspective on new/existing computing curricula

(especially honest feedback on others' experience with CS material/curricula)

perspective on what is out there for your students in computing careers and in college
information-dense listserv (you hear about sites like this one)

However, most of the sessions/listserv posts are still geared toward research on college classes, so you have to be picky about sessions at the conference. There is a K-12 track for sessions, which makes things easier.

There are more K-12 sessions every year, and more K-12 educators attending as well. This year my district (Chicago Public Schools) had 20 people attend, and there were a good number of other (mostly high school) teachers from other districts. Two of this year's keynotes (Gail Chapman and Mitch Resnick) were people whose main impact has been in the K-12 space, and next year's theme is CS for All, so they really recognize the importance of what is happening in high school and earlier grades.


Curricular Support for a CyberPatriot Club

I'm not sure how engaging these would be, but as a source of exercises and practice content, you might look towards IT professional certifications. There are things like A+ (general IT), Networking+, CCNA (Cisco), or MCSA (Microsoft sys admin), among many many exams that are quite popular and have a variety of study resources online.

This PCWorld article has some decent overviews of the tests. I'm dubious of an article promoting certifications based on studies by a group that sells certifications, but regardless, hopefully it has pointers to resources you might be able to pull from.


First Time Learning Non-Linear Data Structures

I'm not sure this qualifies as an actual answer, but let me suggest that you give yourself a course in Structural Induction. Perhaps you already know of this, of course. But the main idea is that the processing of a data structure (the method invocations) matches the structure of the data itself.
Thus, for a binary tree, a method processing an internal node (or the root) will make (recursive) calls to the two child nodes, with the recursion ending at a leaf. This is actually how a recursive descent compiler works, with the processing (parsing) exactly following the structure of the language as defined in a (LL) grammar.
One important lesson that you have to teach is that a recursion can do "work" both on the winding phase (before the recursive calls) or after (when they return). That is easily demonstrated with the following code (pseudocode) snippet:
Global s <- 0;
Fun recur x {
    If x > 0 {
        Print x; // winding phase
        recur x - 1;
        s <- s + x;
        Print x; // unwinding phase
    } Else {
        Println;
    }
    return s;
}

Translate that to your favorite language and see what it outputs for a call like recur 10.
For a tree structure that means that you can recurse (twice) before you process the current node, thus having the results of the two recursions available. This is often called "bottom-up" processing. OR, you can work top-down by computing something in the current node and passing it down with the two recursive calls. Bottom-up processing can be used to construct a tree, for example as is often done in optimizing compilers.
As proof of a "deeper" understanding of recursion. Ask the students to write a linear running time function to copy a list. A quadratic function is easy, but linear running time is a bit harder.

To teach the winding v unwinding idea I often used a matryoshka. Imagine that you have an unpainted matryoshka (which I do), and you want to "paint" it. You can either "apply colors" before the recursion of "paint" or after, stopping at the innermost doll. You can talk about how messy your fingers get if you do all of the "apply colors" operations on the winding phase, since you have to open a freshly painted doll. A bit weirder, though it demonstrates the point, is that you can "apply colors" to one half on the winding phase and to the other half on the unwinding phase.
As a bridge from linear to tree-like structures, imagine a matryoshka that has two "inner" dolls instead of one for each intermediate doll.


Introduction to programming class: use Spreadsheets to introduce fundamentals

Spreadsheets are probably the most popular functional programming language, and is is some what visual. I have taught it for years 7 to 9, but not part of a qualification based course.

Things to be aware of:

It is a functional language, as long as you avoid VBA / macros etc.
You can do functions, though I am not sure about named functions.
I like to put intermediate calculations in to hidden columns. The alternative is very complex formulae / functions, that are hard to read, and hard to write.
The hard part is making it relevant. Don't make all of the exercises about accounting.
Provide spreadsheets that are started, and give them exercises to add/change something.
Don't assume that this is relevant, to them, or that they have any experience. Ask them, give them a choice about how they learn.
If the data sets are too small, then it will not seem relevant, as you could do it my hand more easily.
There is a lot of copy/paste in spreadsheets, this is the main downside, but to use them well you need to embrace it. This is not so for any other, good, language. In the first lesson, have them enter formula, for about 10 rows. Then show them how to use the little dot in the bottom right of the cell, to make it easier. They love this.
Whenever I am teaching programming, I tell them that I am teaching them to be lazy. This helps to engage the lazy ones. Sometimes a hard worker will comment on this, but I tell them “don't worry, one we have learnt to do it the easy way, then this allows as to do more stuff.”.
Most of what you do in spreadsheets can be done in python (except data entry), so you can link it to the python lessons.

While being a good introduction to functional programming. I do not think it is a good introduction to programming. It may be of some help, but I do not imagine the pace of learning will be high.

Most people start with Scratch. The main barrier with this language is that it seems childish (it is taught to primary school pupils ( ≤ yr 6 ). There is another language call snap. It is like scratch, but taught to 1st year undergraduates. It has some extra features, such as create your own functions. With Scratch you can create your own procedures, but not functions. Both of these languages are available as a web service, scratch also has a desktop app. Both you can download and host locally (if internet access is poor).

With snap you can make it look like any other language. I have made it look like python. Unfortunately I could not get all of the blocks to work, but I did use them to create a printed work sheet scratch to scratchy python to python (they did not know that I used snap to help me create it). You can also teach snap to auto generate code in another language. E.g. write program in snap, click generate, and get a python program (I have not properly tried this).


Lesson Idea: Arrays, Pointers, and Syntactic Sugar

This is a great explanation of why 0-indexing exists. As someone who barely knows what a pointer is, your explanation made perfect sense. If you wanted to dumb it down a little you could phrase it as:

  When you create an array, the variable you assign that array to is actually a pointer to the first element. Lets create an array num. When you want to modify the array, to get a pointer to the first element you want to add 0 to num, because num points to the first element. For the second element, you add 1 to num because num is a pointer to the first element and the second is one after the first. Then for the third element, you add 2 to `num, and so on, so that the first is adding 0, the second is adding 1, and the third is adding 2.

A useful resource is this website which explains how num[i] is syntactic sugar for pointer arithmetic (*(num+i)).

I think that this discussion will increase clarity and be very useful because it makes sense as a logical way to implement arrays and revels a cool thing about the language. I'm not sure that you have to talk about memory, but talking about pointers is certainly worthwhile for this example.


Learning fundamental differences between functional programming and Object Oriented Programming

There are beautiful answers to this question already here, and I will not try to reiterate any of the ground that has already been covered.  However, something important that I have not seen here so far is that comparing OOP to FP is not actually terribly meaningful.  It's a bit like comparing glass (the material) to tables (the furniture).  They each have properties that can be explored, but even if discussions of these properties can help you learn about them, the comparison itself doesn't actually tell you much about either.  Glass tables exist, and have the properties of both.  Similarly, Scala, Clojure, and Swift are languages that are both functional and OO.

A more meaningful comparison for functional programming is imperative programming.  The most popular languages in the world right now are all imperative1.  Imperative languages focus on mutable values and states, and are historically based on Turing Machines.  Functional languages are all about function calls and immutable constants, and are historically based on Church's $\lambda$-Calculus.

The two mathematical systems were developed around the same time in order to solve the same question: what is fundamentally computable?  The Church-Turing Thesis, which was published before electronic computers existed, proved that the two systems were equally powerful, and further hypothesized that they could both compute any computable function, and that any sufficiently complex system could embody exactly this same computability power.

A more meaningful comparison for Object-Oriented programming would be... well, nothing.  The Object-Oriented philosophy, which is about grouping data with functions that govern that data, can be applied to any programming paradigm.  Object-Oriented programming is all about the scope and membership of functions and data.  It doesn't matter if the data is mutable, if the order of operations is defined, how data is stored, whether functions are mutable... if we are creating instances of data that are bundled with their own functions, the we have the kernel of object-oriented programming.

1 - Only if you discount Excel, which is actually a light functional programming language, and is almost certainly used by many more people than any other programming language on earth.


The rules for abstract classes are the same as for other classes, with a few minor differences:

An abstract class may have methods that do not have a body
An abstract class has to be sub-classed, at some level, to a non-abstract class before you can instantiate an object
It is not legal to directly instantiate an object of an abstract class

With an abstract base class that has abstract methods, or methods without bodies, all of those methods must be implemented in the subclass, at some level, before instantiation of an object is allowed.

So, imagine the school's official letterhead. At the top is the school logo, name, address, and maybe their motto. Everyone sending an official letter from the school is supposed to use the same letterhead, and they should use the same style and format as other official letters. Sometimes it's allowed to add to the top, such as when the principal gets to add his name to the letterhead, but others are not supposed to do that. To make it easier for everyone to follow the same format at style, the secretary created a "sample" letter for everyone to use. Still some people just didn't get it right, especially the Athletics Department, who used a totally different letterhead. Finally, to end the problem the principle made one, perfect, letter. Instead of real information, however, he used place holders. It looks something like this:

The School of Choice        $School of Choice$          342-54-87971
15 Our Plaza, NE      $Best Students & Best Teachers$   342-54-87915 fax
Best Town, Milan              $Better Grades$           @school_of_choice

From: {your name here}                                     {today's date}

TO: {name of recipient}
    {address of recipient}
    {address line 2}

Subject: {subject goes here}

{your letter goes here

Mauris ut mattis dolor. Donec mollis arcu a augue varius, eu pharetra
ante gravida. Sed ut posuere mi, vitae luctus urna. Vestibulum porta,
velit quis facilisis hendrerit, nibh magna faucibus urna, a pellentesque
arcu nisi a tortor. Suspendisse nec maximus lorem. Maecenas convallis
lorem quis neque fringilla, sit amet fermentum justo rutrum. Maecenas.

Vivamus elementum consequat semper. Nullam consectetur nunc quis turpis
scelerisque pellentesque. Proin blandit, nulla a imperdiet vestibulum,
odio dui tempor neque, sit amet vehicula magna nibh in tortor. Fusce nec
sapien vitae nibh faucibus hendrerit. Nam fermentum egestas arcu in
vulputate. Proin vulputate metus libero.

}

                                                www.school-of-choice.edu

This "letter" is saved on the school's network where any faculty member can access it, but students cannot. (It wouldn't be right for students to send out "official" letters would it?) The "letter" is also made read only. When a teacher needs to send a note to your parents (oops!) they can Word and load this letter template. They cannot save the template because it's read-only, [it is an abstract letter] but they can save a copy of it with a new name [a subclass of the letter]. Still, if they just printed this, and mailed it, it would look really bad for the teacher [it is still an abstract letter]. In order to make the letter "legal" to send, all the {your name here} type things have to be replaced with real information [replace the abstract methods with real ones]. If the teacher's department has its own web page on the school's site, then it can replace the last line, www.school-of-choice.edu with the full page address www.school-of-choice.edu/comp-sci/ [override a base class method]. Now that everything is replaced it is "legal" to print the letter [instantiate it], and send it to your parents. (Yikes!).


Designing rubrics for AP Computer Science-style free response questions

In the weeks leading up to the test I typically only use the actual past tests for exactly that reason. But even when I don't use the released FRQs I still grade on a 9 point scale so they get used to it.

Here's a few more that tend to come up.

For return methods, create a variable of the correct type, do something to it, and return it.

If it's a constructor, it should initialize the instance variables.

On full class problems - either write a full class, extend an abstract, or implement an interface - it's usually a point or two for the class signature.

  Utilizing the appropriate methods from other Objects passed in is
  often awarded a point, though no penalty is made if they successfully
  recreate the functionality that the Object would provide.

Sometimes. And sometimes they explicitly say that you must use the previous method for credit. #3 on the test this year did that.

I also have a negative rubric point for any of the penalties. Destruction of data, unexpected side effects, returning from a void, that sort of thing.


I am not so certain about teaching people to program by starting out with something like modding Minecraft. There are a lot of technical details that someone just learning to program shouldn't be required to understand or worry about. However, Minecraft can still be excellent playground to learn to program by using pre-made mods like ComputerCraft that add programmable blocks to the game.

In ComputerCraft users are given a couple programmable blocks: computers, which are stationary and have the ability to send serial signals; robots, which you can program to move, pick up elements from the environment, and perform actions; and both elements can communicate over a network. The computers and all the pre-packaged applications are programmed entirely in Lua (including the OS). This means there exists a large existing source code base for students to study. Lua is a very simple and elegant language and I have had no problem teaching it besides the fact there isn't really an introduction to programming book using it (Programming in Lua is written by the language author and is very good, but much like Programming in C in that it isn't meant for beginners).

Using ComputerCraft with blocks from other common mods would allow the students to build machines as well as programs; something more than the sum of its parts. This would allow them to see programs as a part of a greater design, which I believe most students don't get enough experience with in school. Personally, one of my favorite projects I've done in Minecraft using ComputerCraft was implementing a mail delivery system using several computers, ender chests, and pipes.


How is computer science (and education) different today than some decades ago?

Like any field with an active research community, Computer Science changes over the decades, sometimes quite drastically. If a practitioner doesn't keep up he or she will be left behind, not understanding the new work.

Decades ago problems tended to be a bit smaller in scope. How do I sort an array? Now they are massive. How do I scale a cloud environment and make it immune from failure and attack?

For this change in scope and scale to occur we need to learn to think at higher and higher levels of abstraction. It is hard to write complex programs in languages that permit only simple constructs.

Language research is still an active pursuit. The ACM still has a special interest group POPL interested in the Principles of Programming Languages, for example. The papers and discussions are deep and "modern."

There are many other ACM SIGs, some of which, say SIGMobile, couldn't have existed a couple of decades ago, prior to smartphones.

The other thing is that such a field grows so much that no single practitioner can grasp all of it after a certain point in time. In mathematics, for example, this point was passed around 1900. It has probably been passed in CS as well.

Regarding education, the changes in the field have also generated changes in teaching, both the content and the methodology. I can speak only for what happens in the US since all my experience is here. But an undergraduate CS major will get two things. First a broad education, including History, Philosophy, and the rest, including some writing. Second they will get enough education in the major field to either go on to a graduate degree or obtain an entry level position in industry. But they will normally never be deeply taught in any one aspect of CS (or Math, or Literature, or ...), nor broadly enough to say they know much about the whole field.

The Master's degree, on the other hand should, in a technical field teach students the things that every working professional needs to know. Again, this isn't necessarily very deep nor broad, but it has to be vaguely comprehensive for the working pro. It should also get you a bit closer to the ability to do research if it doesn't already include some research component. But usually the research required there is into what is known about a possibly new or arcane topic, rather than the creation of new knowledge in a field. That is for doctoral programs.

The effect of this is that undergraduate teaching now includes more options that were not studied in the past (big data, machine learning, ...) through elective subjects at the upper level. It also means that some things that were needed by working pros in the past (numeric algorithms, say) are not taught to the same degree as much of what was once hard is now captured in standard libraries. But methodologies also change, and now teamwork is much more used in the classroom than was typical a few decades ago.

The conclusion I draw from all of this is that students need to start higher up the learning tree if they are to get where they need to go. In my view, recapitulating the history of computation, starting with low level concepts and tools and building everything up incrementally is a mistake. There is also no need. Students can start at any level of abstraction and work upwards from there intensively. They make excursions down the abstraction hierarchy on occasion as some of that helps the understanding, but a complete understanding of the foundations of, say, IEEE Floating Point algorithms is only needed by a very few working pros. If you start the education, today, the same way it was done 20 years ago there will be no time to get to today's problems and solutions.

I used to tell my students that my job is not to teach them what I know, because much of that is now obsolete. My job was to teach them what they need to know. Not the same thing. One example is the hidden bit in IEEE Floating Point.


The order of subjects in beginner's curriculum

We teach AP CS assuming that our students come to us with no prior computing background. Being that the language for AP CS A is Java, we plan our sequencing accordingly. We don't follow the approach of starting with Hello, world. and user input because I think it (main, System.out.println, and Scanner) produces too much of a cognitive load at once . I always try to minimize hand waving as much as possible in the early parts of a CS course to help students build their confidence in navigating code.

While Eclipse is commonly used in industry and higher academia, an introductory course isn't industry or higher academia. So we use an IDE that is more appropriate for the new learner. We utilize BlueJ to begin demystifying Java from the very first day of class. Thanks to BlueJ, we don't have to discuss main or making tester/runner classes to run our code. In our post-AP CS course we can introduce IntelliJ or Eclipse, once the students can comfortably grasp the idea of multiple classes and project directories.

Our decision to introduce objects early was inspired by Dr. Kolling's book's sequencing and the fact that Java is the language taught in AP CS. Others may chime in by saying they think objects should be introduced late. I disagree for the reasons previously mentioned. Should we leave AP and teach Python or Javascript, I would wait until later in the course to introduce OOP. That being said, here is our general outline:

Introduction to OOP

What is a class and what is an object?

Writing Java Classes

What makes up a Java class?
Fields
Constructors
Methods

Conditionals
Logical Operators
Java Math and the Math Class

At this point it's September and my students can navigate an entire Java class and the hand waving of public static void main(String[] args) is gone. That's hugely important and beneficial.

Classes as Data Types for Other Classes

Encapsulation

Strings
1D Arrays

Looping

2D Arrays
The ArrayList Class
Inheritance, Abstract Classes, and Interfaces
Algorithms

Recursion
Searching
Sorting

Keep the students in mind. Remember where they are coming from and that your goal isn't to turn them into CS researchers or software engineers in a single year. Expose them to the content in an order that appropriately challenges them, while avoiding the statement "You can ignore that for now" as much as possible.


How does IB Computer Science compare with AP Computer Science?

About IB Computer Science.
             Computer Science is regarded as an experimental science, alongside biology, chemistry, design technology, physics and environmental systems and societies – and sits in the Group 4 list of subjects. The IB Computer Science course is a rigorous and practical problem-solving discipline.

AP Computer Science Principles is ideal for students who are less interested in Java or who would like a big picture view of computing. ... Both computer science classes have a great deal to offer high school students. Since they vary in several important ways, students should research each course before enrolling.


What are good projects for metaprogramming?

During lecture, my students and I recreate Javascript objects in Ruby. In Javascript, these two lines are synonymous:

config['indent'] = 2;
config.indent = 2;

Ruby doesn't support this duality natively, but metaprogramming makes it possible.

We create a class AutoObject that internally stores a dictionary to hold all of the object's properties. Its method_missing consults this dictionary when something like config.indent is executed. If the method name suggests an assignment, it updates the dictionary. If it's a read of an existing property, it returns the value. Otherwise we raise an exception.

Once the automatic properties are in place, it's not much more work to add serialization and file I/O. By the end, we are reading and writing configuration files that are useful for any application.

ActiveRecord does something similar when it automatically creates an object and its interface based only on the database schema.


Why did interest in CS majors plummet in the United States after the mid-80s?

The Atari VCS game E.T. came out in December 1982, which led to the start of North American video game crash of 1983, the end of a video game software industry boom.  That market fell from 3.2B to perhaps 100M (in U.S. dollars) in just a couple years. Programmers were being laid off in droves.  Boxed software was being sent to landfill. Software and computer startups were starved for capital, or went under.  Game software developers lost much of their temporary "rock star" status.  That business event may have discouraged lots of kids from picking or sticking with a major where employment would have to come from a visibly crashed job market.

The dot-com stock market crash of 2000 (which also led to a vast number of computer industry related job lay-offs) probably had a similar effect on CS graduations after 2003.

Just after the '83 video game crash, easier-to-use personal computers (Mac, Amiga, Wintel, et.al.) were being introduced, which may have allowed end-user (business, science, etc.) productivity to increase faster than the number of software jobs previously required to support that productivity, thus making alternate (non CS) careers possibly more valuable, or more interesting to students, than CS related ones.

Added: The steep rise starting near 1980 is coincident with the PR leading into and through the IPO of Apple Computer (et.al.).  Computer magazines were becoming thick with ads.  Lots of kids wanted to either become a personal computer start-up company stock option millionaire, or at least work for one.

Added: The Netscape IPO (and PR about the millionaire programmers it created) in late '95 looks like it was a just a few years before a similar steep rise in CS graduation rates.


Computer Engineering student with Holes in my knowledge (i want to improve)

The obvious answer is to get a good textbook on Java data structures. Some are better than others and a few will mislead you. I find John Lewis to be trustworthy (and inexpensive as well).

What you are probably missing is the notion of encapsulation of things in classes and specification by interfaces, both essential to Java and specifically to your quest on algorithms. Some understanding of generics will also help you progress, but that is secondary to encapsulation and the idea of separating interface from implementation.

There are more advanced books on Algorithms, but the grounding, first, in building data structures and reaching the point where you can understand the java.util library is your current optimal path.

I would suggest using Java first, rather than C++ as it has fewer traps for the unwary. Java is built at a somewhat more abstract level than C++ and so provides a better way to think about higher level concepts.


Items on grading rubric for a coding assignment

So, if I were reading code, I would object if someone submitted code with every line commented.  I am not aware of any professional code that does this, and when I occasionally receive code from students where this is done, it is simply cluttered.  I believe that the real criteria here is clarity.  Excellent variable naming will often accomplish this sans comments.
Consider:
if ( maxSoFar < currentValue )

vs
if ( maxSoFar < currentValue ) // Find out if the maximum is less than the current value

Truly, the comment adds nothing to the code here.  As a practical matter, it has been my experience that over-commenting makes my students work difficult to grade by reducing the clarity.
Unrelatedly, a missing criterion is having a run-time appropriate to the desired algorithm.
As a practical matter, you may find this rubric difficult to grade with. You will need to give careful attention to weights, and to how those weights will actually be evaluated.  (e.g. in a 3-point category, what sort of work would grant 3 points, what would grant 2 points, and what would grant 1 point?)


History of educational programming languages

I'd suggest you reconsider. To understand e.g. why Pascal is a nice teaching language you need to have a decent background in programming languages, some notion of teaching programming (the misconceptions by learners are often way, way different than you'd guess in your wildest nightmare), and hopefully some experience teaching.
Languages specifically designed for teaching are a wildly varied  bunch, most never won any sort of wider traction. Or if they did, they soon outgrew the "to teach programming" range. Take a peek at BASIC and its recent incarnations (don't look like BASIC at all); languages like Pascal (designed to be easy to implement and teach); Logo and even (to some extent) Scheme are part of the flock.


The primary drive behind the open/close principle was to avoid having to update programs that used a library when changes were made to that library. Or, in other words, to enforce backward compatibility for old programs that used a library.

By not modifying the object (the close half) any code that uses the object according to the documented API, will always work.

By allowing extension of the object (the open half) new features, data, methods, etc., can be added to the functionality of the object to handle new uses for the object, or its subclasses.

Combining both means that the existing object, that almost fits the needs, can be enhanced to be useful in a new program, and still be used by the old programs, without needing to recode the old programs.

A common API that most high school students are familiar with is the telephone. It is going to be a very rare high school student who has never used a push-button telephone, including the "buttons" on the screen of a smart phone. So it is something that's well within the prior experience for those students.

The twelve standard buttons on the push-button telephone haven't been changed since the Western Electric model 2500 was introduced in 1968. The latest model smart phone still uses the same layout, and it still works the same (from the user's perspective), even if it's now a touch-sensitive screen rather than twelve physical buttons. They way on made a phone call in 1968 using a push-button phone, and they way one makes a phone call now with a smart phone is the same. It has not been modified. What you can do with those same twelve buttons, or simulated buttons on the smart phone, has been greatly extended. Sending text messages is only one change of many. There's no guessing what else those buttons might be extended to do, using new methods or new data. No matter what new extensions are added, the original will not be modified.


Toy Databases for Class Examples/Homeworks

I stil think this is basically a duplicate of this question: Good datasets for intro CS courses?

You're asking for a database of interesting data. The other question is asking about interesting data. The only thing you need to do to get from the answers in that question to the answers to your question is to write a little bit of processing code that outputs the data in a format that's compatible with a database.

In other words, you're going to have to massage the data. This might require writing a program that calls an API to get data, and then outputs that data to .sql files or more basic .csv files or something. Then the students would take those files and work with them to create their databases.

I think as soon as you accept the fact that you're going to have to massage the data, you'll open yourself up to a lot of cool data sets. I think restricting yourself to data that's already in the exact format you need is very limiting, and isn't how things work in the real world. In the real world, data is always in the wrong format. You always have to convert it to something you can use.

Stop looking for data in the format you want it in. Start looking for interesting data, and then figure out how to get it in the format you want it in.


Is it worthwhile for college professors to join SIGCSE?

I would say yes, definitely. It is a great bunch of well informed and friendly people. The conferences are very valuable, including the panel discussions, demos, and tutorials.

The SIGCSE conference is also a place at which some of your students might publish and, if they are interested in teaching as a career, meet people who can help them. The people who go to the conference have broad interest in CS as a whole, not just teaching.

Some of the questions that you ask here would find ready answers in the SIGCSE community. Many things done and discussed in the community would enhance your own teaching.

SIGCSE also has an international conference (ITICSE) at which people from lots of places, but mostly Europe, come together annually.

If you don't care to get conference proceedings, etc, on paper, an electronic only option is available and very inexpensive.

I'm a long time member, never an officer, frequent reviewer. I've maintained membership even after retirement, though I've withdrawn from other, more technical, SIGS. Worth it, always.

Let me add that ethics and related topics are often in the Inroads magazine and a number of members are strongly focused on ethics (say, Don Gotterbarn)


Get them to line up (preferably on a wooden gym bench), then get then ask them to get into alphabetical order. You can use this to help learn names, and to introduce sorting algorithms.

I could also recommend CS-unplugged, it is part of the computational thinking, so aimed at very young pupils (primary school < age 11years old), but can also be used with older students.


What are competitive programming problems that require a tree data structure to solve them?

How about Huffman encodings?

  Given a text that uses an alphabet of $n$ unique characters, how can we uniquely encode the alphabet so that the text uses the smallest amount of bits?

More formally for Huffman encodings (as formulated by Tardos & Kleinberg in their book Algorithm Design):

  Given an alphabet and a set of frequencies for letters, we would like to produce a prefix code that is as efficient as possible - namely, a prefix code that minimises the average number of bits per letters $ABL(\gamma) = \sum\limits_{x\in S} f_x|\gamma(x)|$. We will call such a prefix code optimal.

This has an $O(n \log n)$ solution.


Why teach C using scanf without talking about command line arguments?

I think that the rationale is so you don't have to introduce arrays and array notation on day 1. Typically, arrays enter into the picture at roughly the same time as loops, which would take place a few weeks or months later, depending on the pacing of your course.

That said, if you want to start with command line programs, it's not a huge problem to do so.  At the very, very beginning of programming, there are always a few magical incantations that students must type, but won't fully explore until later.  args[0] could easily be such an incantation.

As a side benefit to this approach, your students may have an easier time when they come to arrays, since they've already used them a bit.


Exercises for teaching GUI / Windows interaction basics

The last time I took a session on UI, that was when I was teaching these students who had finished a course on C sharp (dot net) and now wanted to build simple UI so they can turn their just learned programming skills into visibly usable software.

Since they were on dot net, I advised them to start by building a calculator using WPF. When I say calculator, it was a simple calculator. Build the number pad, and then implement just the addition and subtraction. While many of them were proficient in programming, they found themselves baffled...connecting the UI with code that would otherwise work just fine on the console. As they got the hang of things, I asked them to add more and more UI elements, until they had a full fledged scientific calculator with a fairly complicated UI.

My advice to those who are new to UI is to allow the UI to evolve, and make sure that your backend development skills are up to the mark.


Is the CS50x course enough to get the generic knowledge of a CS grad?

No, not by a long shot, although Harvard's CS50x is an excellent introduction which provides around 10 hours of lectures then problem sets which support approximately 100 hours of practice at programming by solving Computer Science problems (not quite the same as software engineering problems).

Most typical entry-level software engineers (regardless of their background) will likely have spent several thousand hours learning their craft by the time they start their first job (Something roughly equivalent to the amount of time a typical graduate may have had after 3 years at university).

This obviously includes programming and core computer science concepts, but most importantly it involves having hands-on exposure to building some working software (Which is about far more than just writing code -- actually, writing code is only a small part of the total amount of work which goes into building working software).

While it's certainly true that Software Engineering is rooted in Computer Science, and computational thinking skills are an essential prerequisite, that capability is nowhere near enough on its own.

Generally speaking, most software engineering problems also have a degree of subjectivity built on top of that - i.e. they go beyond just needing to find solutions based on logic;  most of the problems faced by software engineers are more about humanity - meaning that the vast majority of issues involved in building software can't be solved just by writing an algorithm.

Just to provide a few examples - this list is neither complete nor comprehensive, but hopefully illustrates the kinds of things that are learned through hands-on experience of working on software projects (even spare-time hobby projects and open-source software):

Requirements gathering and analysis
Software design principles and approaches to software design (e.g. consideration towards interfaces, modularity, and automated testing)
Pragmatism and consideration towards real-world constraints (e.g.  people's time, or their willingness to accept change, etc.)
Communication, knowledge-sharing and collaboration with other developers (e.g. peer reviews, pairing)
UI/UX Design
Communication with users and stakeholders, including managing their expectations and seeking their feedback.
Teamwork and being able to function within processes and procedures that allow many people to contribute to the same project/codebase.

On top of that, there's also the fact that software engineering often tends not to be about using code to solve every problem but to include a lot of effort reusing other people's existing/working/tested solutions to avoid re-inventing the wheel (For example, "devops" tools, app frameworks, cloud services, 3rd-party libraries, O/S capabilities etc.)

This often includes trying out tools/libraries/frameworks to check their capabilities, then figuring out how to integrate your code with those things (e.g. through programmatic APIs, configuration management, build/integration/deployment processes, automation/scripting, etc.)

This is not to say you need to be any kind of expert in these things for an entry-level Software Engineering position, however once you're confident in the core skills of computer science, programming and computational thinking,  it'll be important to focus learning around building software - at which point a lot of issues around tools/APIs/libraries/frameworks start to crop up, and so should the issues around understanding software design, testing, pragmatism, and (ideally) a lot of interaction with other programmers.


How can I design online tests and prevent cheating?

I don't think there are any published tools to generate programming assignments, though there are articles that describe such tools (such as this one from a CUNY, or this one from Croatia, so one option is to try to contact those authors and find out whether they would share their results with you.)
I will state categorically that there is no way of guaranteeing that students will not cheat.  As the old saying goes, "locks are to keep honest people honest."  Putting road blocks in the way of cheating will help dissuade students from trying, both because it becomes more of a bother, and because it gives them a chance to remind themselves of the ethics involved.
The bit about ethics is important, actually, and it can be remarkably effective all on its own.  Dan Ariely did an excellent set of studies about this, which he summarized hilariously in this TED talk.  If you don't want to watch that, then you can read this blurb from his blog, though the talk is well worth the time and much more interesting.

"We used an honor code in an experiment at MIT in 2007. We asked a few hundred undergraduates to do some simple math problems but didn’t give them enough time to finish. We then asked them to score their own tests and tell us how well they had done, with payment of $1 for each question they reported getting right. The students were asked to shred their papers afterward—but our shredder didn’t really work, so we could see how they had done. Many cheated. We had a second group of students follow the same procedure but only after they first signed the honor code. Signing the honor code before the test eliminated cheating altogether.
The effectiveness of such a code doesn’t stem from signing it, though. It comes from being reminded about moral issues. If your students eventually stop thinking about the ethics code as they sign it, it will lose its power. If they keep reading and reflecting on the code, its effectiveness might increase.
I ask my own students to write their own version of an ethics code—not because I’m especially interested in their interpretations but because it helps to ensure thought."
Dan Ariely

So, one way of working around the COVID-19 problem is to combine both ethical thinking and a few roadblocks to help gently dissuade cheating:

Remind students about ethics up front, at the top of your exam. (I make them copy out, by hand, an honor statement.  On a computerized exam, I would provide an image of the statement and make them type it.)
Schedule the exam in advance.  Give the exam at a specific time, and a narrow window (say, 10 minutes) to begin the exam.
There is no need to make different exercises for each student.  Make 3 programming problems, and assign each student to different problems using a rule.  This decreases the chances that they will have a friend in the class with the same problem.
Require that the exam be finished within a reasonable time from the start time.

It's not foolproof.  They could, for instance, have their parent sitting next to them, telling them the answers.  But you can't do anything about such a scheme.  What you can do is set up roadblocks and set the stage for ethical action on the part of your students.  If Ariely's studies are any guide, you should get the large majority of students to submit honest work this way, and that is probably the best you can hope for.


First, be aware that Computer Programming and Computer Science are not the same thing. The term Computer Engineering might, in practice, be the same as Computer Science, but it can also be much different (software vs hardware focus).

Coding bootcamps and other, similar, programs, such as online courses almost certainly lack both the depth and breadth of education and skill building that you should expect from a reputable Computer Science program.

On the other hand, businesses need computer programmers, but the  jobs they offer are not very exciting and are at a pretty low level, lacking an obvious path to a long term career. "Coders" work at the direction of others and have little say in what they build or much in the design process.

Still, computer science graduates often work initially as "coders" but, with more knowledge, can be given more responsibility.

Think of programming as nothing more than a tool that helps you explore deep ideas (database, ai, machine learning, ...), but it is those ideas, not programming that is the important thing. You may need to be adept in using the tool, but it remains just a tool. It is fun, but it isn't the essence of a computer science degree.

Programming can get you a job, but it won't assure a career. Of course, once you are in a company, there may be opportunities for you to learn the rest of it, but a degree provides a (hopefully) well thought out curriculum that meets both the modern needs of employers and the intellectual rigor that lets you build a career either in industry or academia.

To get a sense of it, look at the curriculum of any reputable university. Both the required courses and the electives. That will give you a sense of the breadth required.


Introducing the MVC pattern along with JavaFX

I'd use the following analogy connecting MVC to a teacher's gradebook.

In the context of MVC, the actual gradebook with a complete record of every student's grade on each assignment is your Model. Students may have their individual grade rendered in the View, but they would never have access to the entire database (for obvious reasons). A Controller, say in a school's learning management system, would select the appropriate grades to display to the specific student. A student could then choose only to render her quizzes or her homework assignments to focus on specifically those grades. In that instance a user action in the View, through say a dropdown, would modify what appears thanks to logic in the Controller.

As with all analogies, it is an imperfect comparison. However, this general concept will be something (nearly) all students are familiar with.

The iTunes U course on Developing iOS 10 Apps with Swift has a great lecture on MVC. The lecture video and slides are available here.

The image below from Apple also gives a succinct summary of the relationships among the three components.


How can I automate the grading of programming assignments?

The degree of automation that you can achieve depends on how you want to grade. The most valuable type of grading (to a student) does not only cover whether the code works or not, but also offers suggestions as to how to make it better, including readability, design, and so no. And that you cannot totally automate.

You can (and should) automate basic setups, compilation, and  tests, and generally remove as much grading-boilerplate as possible via automation. Todo so, the first step is to make sure that students will follow certain reproducibility guidelines. In my case,

The instructions for assignments always include a specific test environment and test command, that must run. So for example, this could be "jdk 1.7 as installed in the lab" + "javac of your .java files". This allows me to ignore "works for me in my place" excuses -- unless it works in the test environment, it will not receive a passing grade. Note that this is generally not a the development environment; that may be eclipse or whichever other IDE they choose. I generally try to stick to the lowest common bare-metal standard.
JUnit or other unit-testing frameworks are great to assert minimal performance. You can either request them to write their own tests (make sure to specify what these should cover), or provide them with pre-written tests (more effort, but hopefully more in-depth testing). Ryan Nutt's answer also offers good suggestions. Unit-testing is huge not only because it helps you to grade, but also because it makes students aware of their own errors; they will then fix these errors before submitting the assignments, which is a clear win-win.
Mandating command-line friendly build tools (maven, scons, makefiles, scripts, ...) really helps to quickly pass the above tests.
Students must use an online submission system (eg.: Moodle task) to upload their code.

Afterwards, in my grading setup,

I download all submissions for the assignment, and each will be nicely tucked into files named after the uploading student. I then run a small shell script that extracts each submission into a single folder. After significant frustration, the script has been tweaked to deal with .7z, .rar, and .tgz archives instead of the requested .zip files.
I write small per-assignment scripts that I can point at a submission and will

open my favorite IDE pointing at the submission
compare it side-by-side with previous submissions by the same author, assuming that this is an incremental project, using meld or a similar visual diff tool.
launch any corresponding unit tests to see if anything fails

I then write a per-assignment check-list of items that I want to look at in each submission. This gets refined until I have graded 5 or so, when it sort of stabilizes.
Finally, I get to grade the bulk of submissions, writing comments for students as I go, and often copying and pasting comments from previous submissions. When all are graded (and not before, because I sometimes have to backtrack or refine grading criteria), I copy-and-paste comments and grades to the online submission tool so that students can see them. The most frequent mistakes make the bulk of the next lecture.

So essentially I recommend standardizing as much as possible, and investing some time into per-assignment automation, in order to speed up actual grading.


Are there any conventions for writing logic statements for combinations of logic gate functions?

You ask whether your proposed representation would be acceptable. Offhand, I would be cautious about infix notation for these negative operators.
In English, A NOR B would be expressed as "neither A nor B". A NAND B would be expressed as "not A and B". Often, intensifiers will also be prefixed to emphasise a NAND or NOR case and clarify the scope of the negative, such as "not both A and B", or "not any of A or B".
In both cases, the negative is introduced first in English, before the list of items, which accords more closely with the structure of the representations you are trying to replace - NOT(A OR B) etc..
Even on a technical front, I'm not familiar with a programming language that has NOR or NAND infix operators.
If you must contract these expressions or use the name of the operator, I would suggest NOR(A,B) and NAND(A,B).
Another problem is when there are more than two inputs. Unlike AND and OR, NAND and NOR are not associative, whereas "nor" in English has the same meaning and associative property as "or" (it's the introducing word "neither" which applies negation to the whole set, after they have been ORed together).
So NOT(A OR B OR C) corresponds to the English "neither A nor B nor C" (i.e. none of the set is true), but that is not the same as A NOR B NOR C (the meaning of which I can't mentally parse into English, and I'd have to sit down and write out a truth table to be sure).
Nand, of course, does not exist as an English word, but A NAND B NAND C is equally different from "not A and B and C" in English (i.e. not all of the set is true) and from NOT(A AND B AND C) formally.


Exam question order is known to influence performance via confidence and self-efficacy. Put easy questions at the beginning, hard questions at the end, and group questions together if they pertain to the same topic. Difficulty should be inherent in the question itself rather than in the test taker getting oriented to the topic, question, and answer choices. Example set of recommendation, though the following link pertains to surveying rather than assessment. https://www.socialresearchmethods.net/kb/quesplac.php

I can't find the reference at the moment, but if I recall the details, a not infrequently cited example is that demographic questions accompanied a common college entrance test. Placing the questions at the end rather than at the beginning eliminated the gender difference previously observed.


Since you are doing this in the context of code correctness, one incentive is to tell student that in some cases, you have to prove code, not test it. Anything critical (pick up your example, nuclear plant command system, plane autopilot, …) requires the highest level of confidence. Tests are always going to be partial. They will test 1, 10, 1000 possible inputs but that's it. You need to show that your program behaves well for all possible input.

Since many programs work by splitting their large input into smaller cases, proofs by induction are a good fit. It also gives a high degree of confidence since often, the structure of the proof will follow the program step by step (while a proof by contradiction would only be remotely related to the code).

You can also show that often, a proof by induction will give you an actual program. The basic toy example is the one of the Tower of Hanoi (where you have three pegs and N discs). The proof of the theorem stating "it takes 2^N moves" is actually the recursive algorithm that implements the moves (and you can make an animated version of the algorithm in JS or something to make it visual).

Another example is quicksort. Give the code of quicksort. The (strong) induction proof of correctness has the exact same structure has the code.
You can use several divide and conquer algorithms for this (Binary search also works very well AND is really cool because you can also show another issue with proof of code : Most 'student' implementation of binary search are buggy, since they tend to write middle = (left + right)/2 which will overflow for large arrays (where left+right > max_int). This bug was present in the Java standard library. So you also have to talk about the mathematical model of the program (used for proofs, where you have potentially infinite memory, Natural numbers) and the program (fixed size integer, limited, memory, …).


Rather than try to give you an answer directly, let me direct you to a web site that is full of ideas, not for research, but for how programming and programmers can affect things. Paul Graham is a computer scientist, mostly associated with the Lisp family of languages and has done some very interesting things with Common Lisp.

But his essays are just ideas that are interesting, if nothing else. Reading them is likely to give you ideas as well.

Poking around in them might give you some ideas. But, you might also want to think about not making your research too narrow. Not just programming or programming languages, or even just CS, but how it all relates to the wider world and the other things you've been studying.


What makes imperative programming easier or harder to learn?

This is a topic very close to my heart.  I think that the skeptical attitude you've alluded to simply comes from the fact that most people were taught imperative programming first (and some were never exposed to any other paradigms at all).  Turing's Machine was easier to conceive of as a physical, mechanical device than Church's $\lambda$, and it is presumably by this historical accident that mutability rules the day almost everywhere.

I am not even remotely convinced that imperative programming is more obvious or intuitive than functional programming.  In my experience, setting values is a consistent cognitive trap for students, and one that I have to treat with great care.  My very first unit for AP is modeled rather loosely after Tom Rogers' phenomenal opening AP unit, Java Ain't Algebra, which takes exactly this issue head on.

In my (by now heavily modified) version of Roger's mini-unit, I make explicit that values can change, spend time tracing them, show why x = 4 + 7 is not the same as x - 4 = 7, and spend a lot of time making clear that the programmer's

=

is only barely related to the mathematical

$=$.

We also begin to explore the runtime stack.

Teachers often miss that this even needs to be covered because, once they are thoroughly inculcated in imperative programming, it can become hard to even see why this is hard in the first place.  The variable x was 4, but now it is 5.  What could be simpler?

But of course, students exposure to variables prior to CS comes from algebra.  And in algebra, when we say that $x + 3 = 7$, we mean that $x = 4$, and it cannot suddenly become $5$.  We can solve for values, but we cannot alter them.

Here's the takeaway: if we, as teachers, don't make explicit how very different it is to be able to change values, a certain percentage of students don't ever fully pick up this idea.  They'll get hazy bits and pieces of the idea, but have trouble operating, and ultimately fall behind.

In my experience, they don't appear to get noticeably lost until far later in the year, but by then, it is very hard to get them back on track.  (When I take on a new tutee in the months leading up to the AP test, this is one of the first areas I check if they seem generally lost.)  I have also come to believe that this is one of the key ideas that most CS teachers miss, and is responsible for a substantial portion of computer science's very bimodal results with students.

There is a real cognitive load to considering not the value of x, but the value of x right now, and having to both track that value and figure out when to change it.

In spite of what this all sounds like, I'm not suggesting that functional programming is necessarily easier; it has its own cognitive load, since suddenly we are contemplating many, many simultaneous x's taking place during recursive calls.  It's almost as if learning to talk to something as alien as a computer is always going to be a bit tricky :)


Difference between a Bachelor's degree and a Master's degree in CS

From my experience in Canada, a master's is about specializing and focusing on a particular topic within the field while a bachelor's is about becoming a practitioner within the field.
If, as you state, your goal is to obtain a more practical degree then both options can do that but in different ways:

A four-year bachelor's degree will provide you with breadth in CS;
A 2-year split master's will teach you the basics of CS to allow you to focus on a particular area within CS in your master's.

If you are looking to leverage your existing Economics with CS somehow then the master's is what you are looking for because you are adding CS to Economics.  If you are looking to become a computer scientist or programmer / software engineer, then the bachelor's is what you are looking for.  You will still learn (or be expected) to program in a master's in CS but you will be less focused on that in a master's than a bachelor's.
Note that at the end of either program you will have a CS degree, but you will have different skills and its which skills you are looking to obtain that should help with your choice.


How to learn web design if backround is on mathematics and data analysis?

Just about everything you need can be found in one or another book. O'Reilly has a large selection of reputable work. (No affiliation) But a topical search online or at Amazon will get you what you need.

If you prefer video, a search at YouTube, say, will turn up lots of possibilities.

Prefer recent books and videos, however. Straight html is seldom used for serious work these days.


Is there independent evidence that physical computing improves engagement

There are many academic articles reporting high engagement, especially among students underrepresented in computing, using physical computing. https://scholar.google.com/scholar?q=physical+computing+education . Most of them lack a controlled study design. That doesn't mean they don't provide evidence however. For example, from Peppler 2013:

  The capacity for e-textiles to diversify participation was first
  documented by Leah Buechley and Benjamin Mako Hill,2 who discovered
  that while men created the majority of traditional Arduino projects
  posted on Vimeo, YouTube, Flickr, and other sites (85 percent), women
  created most of the LilyPad Arduino projects (65 percent). What is
  striking about this comparison is that both types of projects share
  the same microprocessor and are programmed in the same language. The
  researchers suggested that the gender discrepancy could be due to some
  combination of the tools and materials used (insulated wire versus
  conductive thread to make connections between components), the
  construction practices employed (soldering versus sewing), and the
  nature of the products (robots versus interactive quilts).

  To understand whether changing these factors could significantly alter
  classroom culture in a similar way, we implemented a series of
  e-textile experiments in middle school settings where we closely
  observed how gender dynamics played out. From videotaped observations
  of subjects working in mixed-gender pairs, we found that both boys and
  girls equally engaged in e-textile activity, as evidenced by body
  language, gaze, talk-on-task, and other indicators, but girls tended
  to play a greater leadership role. The projects were positioned in
  front of the girls 81 percent of the time; the girls also spent 58
  percent of the time directing activity, troubleshooting, and deciding
  next steps and made only 39 percent of the requests for help from
  teachers and peers. We found that this early leadership was predictive
  of having more sophisticated command of the technology in subsequent
  projects, requiring less troubleshooting and assistance from others.

That said, probably wise to heed the central advice of Kicking Butt in Computer Science: abandon gender difference as the underlying theory in what works, and emphasize instead a high value on diverse interests and on applications that positively impact people's lives.