Why do computer-science majors learn calculus?

There are several answers:

Answer 1: Not all CS programs

First, not all CS programs require calculus in order to get a bachelor's degree. The Bachelor of Arts (BA) program at Mills College, where I teach, does not require calculus. Instead, we require two semesters of discrete mathematics, which we consider far more useful to computer scientists, because it (at least the way we teach it) includes:

inductive proofs
Boolean logic
proof by contradiction
sets
combinatorics
basic probability
recurrence relations
graph theory
matrices
regular expressions
finite state automata
formal languages

Answer 2: Scientific foundation

That said, getting a Bachelor of Science (BS) degree from Mills or just about any other school requires calculus as part of general scientific knowledge, along with introductory chemistry, biology, physics, etc., none of which we claim someone will necessarily be useful to a computer scientist. These courses are part of the college-wide BS core, not specified by any individual department. The idea is that anyone holding a BS degree should understand the fundamentals of major scientific fields even if they will never apply them in their careers. (Similarly, most colleges require students to take classes in history, even though they are unlikely to become time travelers.)

Answer 3: Historical reasons

Computer science as an academic discipline has not been around that long. Most CS programs started within either Mathematics or Electrical Engineering programs. Both of those fields legitimately require calculus. I went to MIT, where CS was added to the EE department. All CS majors were required to learn both digital and analog electronics, the latter of which requires calculus.

Personal thoughts

In my decades as a computer scientist, including in industry, I never used any of what I learned in the required calculus (I, II, and III), linear algebra, or differential equations. That said, they did give me the background to go into computer graphics, electrical engineering, or machine learning, had I later chosen to.

Whether programs should require calculus is another question.


How to teach C++ language to beginners of (BSCS) students who have no any idea about it?

While I would suggest a different language for beginners, I'll take it as given here that the students need to learn C++ and not just programming for general use.

In that case, teach them Modern C++. That means C++ versions 14 and 17 and don't bother with anything earlier. To do this find a good book that focuses on those versions (or later if you are reading this in the future) and has been developed by someone who has good knowledge of pedagogy as well as the language. There are a couple of books available on Amazon that meet this criteria.

Note that you give up nothing by starting with the current version. The book will still cover the low level details that were inherited from C and that are still useful. You won't spend time trying to learn the things that have become obsolete for modern software development.

But, the important point is that a modern language comes with a set of idioms that enable its proper use. A language is not just a collection of features that you combine arbitrarily. It was designed with a vision.

So, once you get beyond trivial programs, you want to learn the current idiomatic usage of the language (whatever it is) along with the lower level details. In particular, you don't want to spend time on the idiomatic usage of an earlier version of the language once they have become obsolete.

I will also note that programming in a language requires the programmer to adopt some mental model. If a language is well designed, then it is possible to program completely within that model without worrying about how that model is implemented in some lower level model. That is to say, the model will be both consistent and complete. So, a book with good pedagogy will emphasize how you use that model to create useful artifacts.

The advantage of Modern C++ is that many of the pitfalls of earlier versions (and especially those of C) have been removed through the use of standard libraries. Lots of the kinds of errors that seem invariably to creep into commercial software don't occur at all (and so fewer viruses,...) if the programmer understands the libraries and the proper idiomatic use.

There is no need to take an historical approach to computing, starting with machine level programming and working UP to some higher level. That was my approach, actually, since I grew up with that history and have been programming for over 45 years. I didn't then use the languages that I use today since they didn't exist, not because it was better, in some way, for me to use primitive languages first.

Note that if a language does not provide a complete and consistent abstraction model for programming (if it isn't Turing Complete) then you would have to try to understand its features in terms of some lower level implementation mode. Otherwise you can learn the language directly and understand how the parts fit together idiomatically to write any program using a single mental model.

If you, as an individual want to learn everything bottom up, then go ahead. But if you are a teacher, I suggest that you don't impose that way of learning on your students. It is inefficient and unnecessary.

Once the students learn to program at a given (complete and consistent) level of abstraction they can then learn about how things are built or use them to build higher level abstractions.

If I had a choice of first teaching language today, it would probably be either Haskell (functional) or Scala (Object oriented). Both of these offer complete and consistent mental (abstraction) models as well as rich libraries. The teaching method would be to teach the idiomatic usage, not just the features. There are others that would serve equally well. The mental model needs to be taught along with the language. That is a pedagogical issue.

However for someone with less background in language principles and in programming pedagogy, I'd probably rather recommend Python or Java, just because of the wealth of teaching materials available, combined with a rational abstraction model. Creating good teaching materials in any language is hard work.

I'll also note here that many people have the experience that the second language they learn is the hardest, especially if it is either quite similar or quite different. That is due to the fact that your first language teaches you (you believe) how to program, so, the new language feels awkward and one tries to apply the idioms of the old language to the new one. It won't work. Even languages as close as Java and Ruby have different idioms.


What are some good problems which can be solved with a queue?

One example I've used for students in the past is a shared printer.

If I have five people using a printer all at once I will have a problem if two of the five attempt to print at the same time.  What can I do?  I can put up a sign on the printer--"Only One User At A Time Please" and hope everyone sees and follows it.  Of course then the users need to coordinate their use.

I can (software) lock it so that only one person can print at any time.  But when the second user tries to print he or she is blocked until the printer is free.  And the third user is blocked longer etc.

Or I can set up a queue.  As each user prints the print job goes to the queue.  The printer looks at the queue for jobs to print and as it prints them it removes them from the queue.  No one is blocked and the printer doesn't fail because two people try to print at the exact same moment.


Go latest - why not? Public facing - I'd say just make them all sign a terms of use agreement.

Great plan - at the moment I don't really get to do much web work due to the courses I teach - if I did, I would totally love this. Particularly if you can get a retired server rather than just a PC, I reckon kids would buy in to it bigstyle!


How to teach beginning students how to find and fix syntax errors?

I would start by showing them a few natural language examples, where changing one letter in a sentence completely changes the meaning, perhaps into nonsense.  Most computer languages respond similarly to almost any syntax change.

Then show students program lines with correct and incorrect syntax (of typical mistakes, perhaps taken from previous sessions of the same course), and the corresponding error message(s), and/or incorrect/unanticipated run results.  Quiz questions to test this might be, given a line of incorrect syntax, what is the corresponding error message (or bogus result) and a possible correction.

The important idea is to help students form a mental connection between changes in syntax and changes in (IDE/compiler/interpreter/runtime/etc.) behavior.


Demographics in Programming Teams in Early CS Courses

I avoid using protected characteristics for any kind of group/class allocation. Personally, I apply a similar approach that I use in experimental research: the randomized block design. Typically, I use levels of prior relevant experience, either self-reported by the students at their point of admission or their grade for their pre-requisite class, as the blocks.


For a beginner, is it better to start with C or a higher level language?

Based on your history and preferences, you have a particular view about what it means to be a programmer. I have somewhat the same history, but come to a different conclusion. Start with a high level language, probably either a good OOP language (Java, Python, Scala...) or a good functional language (Scheme, Racket, ...). Those two groups of languages cover much, though not all, of the "higher level thinking" in programming today.

Programming Languages are all about abstraction. Different languages offer different kinds of abstractions and different levels of abstraction. However, once you choose a language, the programs that you build within that language are usually (always?) about creating even higher level abstractions than those in the base language. We try to write programs "in the language of the problem we are solving" and choose names (abstractions) accordingly. That is why we don't name our variables v1, v2, etc and our functions f1, f2, etc in our programs. Our variables are things like size and done and function names are like compute_capacity.

Every programmer needs to know something at least of a whole range of abstractions. Assembly language is very low, C is a bit higher. Ruby is quite high, as is Racket. Wherever you start learning you will eventually, after totally grokking that language, want to go to other levels. If you start at a low level then you have only one direction to move, but if you start at a higher level you can move both higher an lower. Thus you can learn how things are represented (at a low level) and how things might be hidden/regularized at a higher level.

Each programming language that you learn is built on a set of ideas that encapsulate what a program should look like. The view of a C program is very different from that of a Java program. The difficulty in moving upwards in the abstraction scale is that it is often difficult to give up the low-level constructs that you have become used to for others that are more appropriate in the new language. For example, polymorphism exists in most languages. In low level languages like C, the polymorphism is ad-hoc, implemented by setting and testing flags. In a higher level language (Java), polymorphism can be implemented more directly using certain design patterns (Strategy/Decorator) and helper objects. But the programs written by those who started low, too often still use only ad-hoc methods, which potentially leads to programs that are difficult to read and understand (too-deep nesting of structures).

You say you can learn any language using the "paradigms of C++". I know a few programmers who can validly say that, but most C++ programmers cannot, outside a fairly narrow range of languages. Moving from C++ to Scheme or Standard ML, for example, requires a completely new way of thinking about programs. Adopting this new way of thinking is actually inhibited by what you learned well in C++. Not that it is impossible, but it is a harder climb.

Let me give an analogy. If you want to become a medical doctor, you don't start by  gathering herbs and chanting ancient songs. You don't, then, progress to leeches and bloodletting, following an historical trail. It is true, however, that some medical practice is only considered valid because it was handed down from antiquity but actually has no scientific basis. At some point in history, something was tried and it worked. No one knew why, but it became standard practice. But, and the point is, you don't need to start your medical training with ideas from 100 or 1000 years ago, even though many of the things learned then are still valid today. Nor do you need to start your education at a low level.

One misconception that people often have about high level languages is that they can only be understood in terms of some (supposed) implementation in a lower level language. Certainly compilers take this view, but humans don't need to. If a language is minimally useful it will provide a complete set of abstractions that permit you do any computation (Turing complete) solely within that set of abstractions. When I program in Java, I don't need to think about what the compiler will do with a reference  variable (is it a pointer? is it like a pointer? is it completely different?). I just know that it gives me access to an object so that I can send messages to that object. I think in terms of reference and message, not in terms of pointer and function call and don't care if they are similar or distinct. In fact, thinking at the lower level can lead me astray. In a Java program, with overridden methods, it is not possible, in principle, to know which version of a method will be invoked without a complete trace of the program. You may not be able to discern the precise type of an object without that trace, and a distinct execution of the program may take a different path.

Some people think that low level languages are more efficient than high level languages. That may have been true at one time, but isn't necessarily true anymore. If you examine a few statements in a low level language, like C, they certainly seem to be easily implementable on a Von Neumann architecture. The problem is twofold. Programs consist of many many statements and it is easier to write and reason about complex algorithms in a high level language, especially one that is purpose built (bespoke) for that domain. Compilers today can execute tens of millions of instructions to globally optimize programs, something that a low level programmer can't do, and something that low level coding often inhibits. If I write a program describing explicitly how a problem is solved (typical in C), the optimizer is pretty much limited to following that instruction stream (not precisely, I realize, but that isn't global optimization). On the other hand, if a program describes what is to be accomplished rather than how to do it, an optimizer has many more options for coming up with both a high and low level set of strategies for execution.

The second reason that low level programs are only apparently efficient is that modern computers are only barely recognizable as Von Neumann architectures anymore. With multi-level cache (both data and instruction) and multi-processing on (say) graphics processors, the relation between the programmer notations (the program) and what is executed gets farther and farther apart as time goes on.

Summary:

Languages are about abstraction
A decent language will provide a (Turing) complete set of abstractions. Therefore you can think at that level of abstraction.
Lower level language are not, inherently, more efficient than higher level languages, though they may appear so. Compilers can do more than you think if you let them.
A human, moving to a new abstraction level, will have difficulties made more intense the more they are committed to the "old way of thinking".
Start somewhere. For myself (who started low), starting higher gives you a better, clearer path. But you will eventually want to branch out. Learn to think, completely, within the abstractions provided by the language you use. Understand those abstractions in terms of the other abstractions and idioms in that language, rather than by "mentally compiling" everything.

Here is an odd historical note about medicine, that I'm pretty sure doesn't really apply here:

In a few cases it isn't ethical anymore not to use some relatively ancient practice, so science is blocked from advancement in that area. The Pasteur Treatment for rabies is like that. It works, but is a dreadful process for the patient. But rabies is nearly always fatal, so it is unethical to set up a scientific experiment in which the control group gets Pasteur, but the experimental group gets (only) a vaccine.


What are the merits of including the history of computers in the entry level curriculum?

To give another perspective, when teaching an intro to web development course it's very useful to teach things in a way similar to how they were discovered and contextualize the different concepts in history. It's easy to understand why HTML is a markup language rather than a full fledged language when you consider the time: The Web was used for serving plain text pages, and they wanted a little markup to make it nicer. HTML was born. When styling become larger than HTML could encompass, CSS was born. When interactions wanted to be built in, JS was born, etc. Otherwise you can get into extended discussions about why the front-end environment is the way it is.

In cryptography it's the same way. By following the history you can see the mistakes of those before you, and thus avoid those mistakes. Crypto is all about the cycle of making a new algorithm then having it broken, and the arms race that it causes. History illustrates common pieces of advise, like to avoid security by obscurity, and history also shows why perfect forward secrecy is needed. It shows the need for key exchange, and shows the relationship between unsolved math problems and crypto. All of these are great reasons to teach crypto in chronological order, from the oldest discoveries to the newest.

I would guess that this sense of parallels between the order in which things are invented and the order in which things are taught exists in other fields as well, and so teaching history along with the normal coursework could be very useful.


What is the pedagogical value of Conway's Game of Life?

I really like Ben's answer, but I wanted to add my two cents:
Like Ben and others have mentioned, Conway's Game of Life provides a "wow" factor that's useful in and of itself. It's simple to understand, and easily leads to pretty patterns and cool animations. This inspires students to want to play around with the code, which by itself is pretty valuable.
On top of that, it leads to some pretty interesting more advanced topics, such as:
Emergence
From Wikipedia:

In philosophy, systems theory, science, and art,  emergence is a phenomenon whereby larger entities arise through interactions among smaller or simpler entities such that the larger entities exhibit properties the smaller/simpler entities do not exhibit.
Emergence plays a central role in theories of integrative levels and of complex systems. For instance, the phenomenon of life as studied in biology is an emergent property of chemistry, and psychological phenomena emerge from the neurobiological phenomena of living things.

Imho, emergence is one of the coolest things about computer science.
Swarm Behavior
From emergence, you also get to talk about swarm behavior, including programs like:

Boids
Ant colony optimization algorithms.
Swarm intelligence
Particle swarm optimization
Artificial bee colony algorithm

The list goes on, and the related articles at the bottom of all of the above are a vertiable black hole of fascinating stuff.
Artificial Life
From Wikipedia:

Artificial life (often abbreviated ALife or A-Life) is a field of study wherein researchers examine systems related to natural life, its processes, and its evolution, through the use of simulations with computer models, robotics, and biochemistry.

From here you can talk about artificial intelligence, neural networks, machine learning, etc.
Cellular Automaton
The Game of Life is just one example of a cellular automaton. There are a ton of other examples.
You could use a 1D cellular automaton to introduce the concept to less experienced students.
Simulations
The game of life (and other cellular automata) also has practical applications, such as being used in simulations of bacteria, epidemic / disease outbreak, and forest fires.
Do a search for "cellular automata forest fires" or "cellular automata disease modelling" for a ton of results.


How do I teach "math equality" vs. "CS assignment" vs. "CS equality logic operator"?

I actually cover this idea in my very first lesson in AP Computer Science, because I have found that students find the different uses of = to be confusing, indeed.  I run a unit based on Tom Roger's unit, Java Ain't Algebra, and I also talk about it a little here.

I do this right at the beginning because, if mutability is not made explicit, students do not seem to exhibit a total loss of comprehension or ability right away, but rather, very slowly slip further and further behind.  They will never be able to articulate what they find confusing about the material, because every piece seems to make sense when looked at in isolation.

The confusion itself stems from simply not realizing that there are articulably different uses of equality in the first place.  In my experience, simply pointing it out is actually enough to stem the tide of the confusion.  (You gave a perfectly wonderful explanation in the question itself.)  Then, two or three more times over the first few weeks of class, I will gently remind them that this equals (some code statement we are examining) is a mutating equals, not the constraining equals of mathematics.

I have not had problems from students in this regard since I began this practice.


How do I scaffold students toward building meaningful projects?

For context, I teach high school students as part of a 4-year high school computer science major.  My students do, during their 4th year, a full-year project for a client who has a need.  (The clients do not pay for this, they provide a client experience for our budding developers.)  At the end, we have a big event with presentations, outside judges, and a lucheon. I've been playing with the formula for this class for a number of years (and I am still tinkering!), but here are a few takeaways I can share with you that would apply to younger kids and shorter projects:

Pose a challenge to the 8th graders to address a particular world problem.  (You should choose the problem).  It could be global hunger, or too much partisanship, or not enough kids with access to education.  Tell them that their application should address this problem.  Give them three research resources that they can use to explore the issue further.
Make other projects possible only if they write a few paragraphs about why the problem they wish to address is important, and how they intend to address the problem.  They must include a reference to 3 sources about the problem that they want to address.
Get outsiders to come in for a culminating event and "judge" the final projects.  (The outsiders can be other teachers from your building, your administrators, or true outsiders.)  Let the kids prepare a short presentation about their project, science-fair style, and let the judges walk around with a rubric and talk to the students.  Having people from the outside world come in is a powerful motivator (and will prevent a lot of the fart-joke responses).  Similarly, contact your local newspaper and see if they can send someone in for a small write-up.
Give a certificate to the winner, or even a small trophy.
As they work, have each student (or group) create small milestones that they must meet.  These are the core of the evaluation process.  New milestones are created on the same day as the old ones are graded.  They must be very specific, and you must agree to them.

In the following year, you can choose a new problem to address, and you will have a few example projects from the first year.  By choosing only one or two very strong projects (and saving the newspaper writeup), you can really set the tone the second year.  This project will now be a big deal, and kids will take it very seriously!


To plan or not to plan that is the question

As you suggest, it is a subtle question. Twenty-five years ago, the answer was simple: Plan. But too many software projects crashed and burned because of over-planning and sticking to the plan after it was obvious to all that it was the wrong plan. More recently, the initial failure of the signup system for the Affordable Care Act was likely caused by this same failure of thinking.

Plan if you can, but be flexible enough to deviate from the plan when needed.

That sounds like good advice, but it can, itself, be the root of too many problems. If you have a complete plan you are likely to be willing to expend resources at the beginning that will only recoup their investment if it proves to be the correct plan but will be wasted (sunk cost) if the plan proves to be incorrect.

So, with a complete plan you can build the thing at lowest cost if the plan was correct. But you wind up with a failed project otherwise. Not only have you spent money on the incorrect plan, you have expended time and your competition may have moved ahead with a better solution. You are both late and poor.

When you can't plan, build on a tight feedback loop.

That is the key message of Agile development. All of the practices of, for example, Extreme Programming and Scrum flow from that message. The implication is that you don't expend resources on speculative assumptions about where the project will go. It does mean that (a) you sometimes can't take advantage of economies of scale and scheduling but (b) you don't get caught with sunk cost that you get no benefit from. In today's development environment (rapid change) this is usually a better assumption to make.

My advice to educators is to learn everything they can about Agile Development, whether you decide to adopt it or not. The ideas are interesting in themselves and can prove transformative if not viewed too narrowly as just a set of practices.

And, of course, read the Mythical Man Month. Its message is valid yet, though it was written for the BUFD (Big Up Front Design) era.

Note that agility goes beyond software development. The principles of agility (see the Agile Manifesto) can be reapplied in different ways to vastly different things.


What are some good real-life examples of pipelining, latency, and throughput?

Production lines in factories, eg. for assembling cars.

In theory, a single person could assemble a whole car from scratch. But they would need to memorize a lot of different steps and it would be hard for them to find an ideal working mode. For example, they might need very different clothes and tools for assembling the engine and painting the body. What is worse, the only way of speeding up production is assembling cars in parallel. Parallelising tasks this way does not scale well in the real world (eg. think of the logistics for getting the parts to every worker as you keep growing the number of parallel workers). In software and hardware design this also applies: (Task-)Parallelism introduces significant additional complexities into a system, so we can't blindly rely on it for scaling up indefinitely.

What factories do instead is, they break the assembly process down into distinct steps and then have each worker specialize in a specific step. This allows them to quickly learn how to complete that singular step as efficiently as possible.

In software and hardware design this is also true: Finding the most efficient design for a single, self-contained step is way easier than optimizing a big system that does everything.

Now, breaking your assembly line into its parts has its caveats: You introduce additional overhead by eg. having to move the car from one assembly station to the next. So a single car might in the end still take longer to move through the assembly line than if one person did the assembly all by themselves. But we can compensate for that by making use of the fact that the steps are independent: As soon as the first car leaves my assembly station, I immediately start working on the next one, even though the previous car still has to reach the end of the assembly line before it's completed. The latency is the total time it takes for a car to pass through the complete assembly line. Throughput is how many cars the assembly line can complete per hour. Once the pipeline is full, this is determined by the time of the slowest assembly step - the clock rate of the line.

The challenge in designing such a system is to find the sweet spot for how much work we can fit into a single step. If a single step gets too big, it again gets difficult to optimize. If it gets too small, the overhead of managing the line might be bigger than the actual work required for the assembly. But we also need to ensure that all tasks are about the same size: If a worker is able to complete a task significantly quicker than the clock rate, they will be forced to idle for the rest of their time until the next car is delivered to their station. All of this applies 1:1 to software/hardware design.

Now, in our production line scenario we have a pretty ideal situation, as the different cars can all be assembled in isolation. If someone makes a mistake in assembling car A, that affects only car A but none of the others (unless the mistake somehow forces you to stop the complete production line). In hardware or software this is often untrue. For instance, deciding whether you take a branch in a CPU instruction pipeline often depends on the result of a previous operation. However, if that operation has not reached the end of the pipeline yet, we might not have that information available. So we have to delay the execution of the branch until that information becomes available (stall the pipeline). If we have a lot of those dependencies (often referred to as hazards), we might lose all our pipeline parallelism again and our throughput approaches the latency of the pipeline.


Could physical (i.e. lego) models help teach CS?

It would, of course, be foolish to answer no, since you give an example of it. There is a Pedagogical Pattern, in fact, called Physical Analogy that suggest doing just this. Physical analogies of any kind help a student visualize the concept at hand. But it is this idea of aiding visualization that is key here, not the physical object itself.

Metaphors and analogies of any kind are essential to teaching novices, linking their prior knowledge and experience to the new topics. But the pointer thing can also be taught at a white board with a bit of showmanship. "new" means draw a _cell, "next = " means draw an arrow.

You can also provide a computer visualization that abstracts a bit from what the "professor" is showing in the video, which does, in fact use a bit of computer visualization along the way.

But, while I'm a big fan of metaphor and analogy, I want to also provide a caution. The thing you are teaching is "similar to" but not "just like" the metaphor you use. Don't try to push the similarities too hard. At some point any metaphor breaks down and if the student has put too much currency into the similarity he or she may have trouble. Nodes and pointer are not, in fact, physical quantities, but only bit patterns.

For a simple case like cells with next fields you can also do this. A person is a "cell". Their left hand holds a bit of "data" perhaps written on a piece of paper that they hold or some other physical object that they can use. Their right hand is a "pointer" to another "cell" (i.e. person). You can build up a linked list in this way. You can modify the data in a cell, you can modify where "next" points to, etc. If the class is large this may be more effective than the lego idea since it can be viewed by a larger audience. It is also more active than just viewing a "professor" manipulate blocks on a table.

Also, metaphor isn't limited to such low level ideas and can be used at any level. "A database is like...". They are only limited by the creativity of the teacher and the willingness to work at it to get it right. The make a peanut-butter sandwich as a way to introduce algorithms is often used, but the knowing teacher also knows that no one is really likely to treat making lunch as a true algorithm. There it is the differences that are essential to the learning, since over interpreting an "algorithmic" description leads to trouble (and messy floors).


What are the core concepts of discrete mathematics within CS?

In the search for a "core set of concepts that is discrete mathematics as it applies to the study of Computer Science," I kept finding nebulous ideas, without concrete parameters. There seems to be a general consensus that there is the need for a firm foundation in discrete mathematics when studying CS. There is also a broad agreement that "graph theory, and other topics" is part of that foundation. Unfortunately the other topics portion of the requirements are seldom well specified, and seemingly never delineated with any specificity.

I recognize that the question is in a high school (USA ages ~ 15-18) context. Be that as it may I've settled on a source from the university context for a solid, definitive, and delineated set of "core discrete mathematics material" to set as a touchstone.

Williams College requires that students who select "Computer Science" as their major demonstrate a proficiency in discrete mathematics. This requirement is usually met with a "C", or better, grade in their MATH 200 course. In Spring 2017, the Computer Science department added an alternate method of satisfying the requirement: A "Discrete Mathematics Proficiency Exam."

Williams is classified as "most selective" by U.S. News & World Report, admitting less than 20% of the applicants each year. As such it is expected that they have set standards, in all areas, rather high. However, I prefer to avoid the dangers alluded to by Michelangelo (disputed): The greatest danger for most of us is not that our aim is too high and we miss it, but that it is too low and we reach it. If I were to choose a target, aiming "high" has the advantage that I might reach the target. If I fail to reach the target, I will know how high I can go. If the aim is low, however, and I reach that target, I still will not know if I could have reached higher. Therefore, using the materials from Williams College as a guide for a high school course seems worthwhile.

All that being said, here is the "short list" of their subject areas, (taken from their Preparing for the exam web page.)

Sets, Relations, and Functions
Basic Logic
Proof Techniques
Basics of Counting
Discrete Probability
Measuring Algorithm Complexity
Graphs and Trees

There is, most assuredly, a lot of ground to cover there, and it does not look any "easier" with a full breakdown. The referenced web page (ibid.) lists a breakdown of the topics followed by the  learning outcomes. I think the learning outcomes likely to be more significant in answering the OP's instant question, and have reproduced them with their subjects below.

TL;DNR

The seven areas above have following learning outcomes listed in the cited materials:

  Sets, Relations, and Functions

  Learning Outcomes:

  Define, as well as explain with examples, the basic terminology of functions, relations, and sets.

  Perform the operations associated with sets, functions, and relations.
  Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.

  Basic Logic

  Learning Outcomes:

  Convert logical statements from informal language to propositional (and quantified) logic expressions.

  Apply formal methods of symbolic propositional logic, such as calculating validity of formulae and computing normal forms.
  Use the rules of inference to construct proofs in propositional logic.

  Proof Techniques

  Learning Outcomes:

  Identify the proof technique used in a given proof.

  Outline the basic structure of each proof technique described in this unit.
  Apply each of the proof techniques correctly in the construction of a sound argument.
  Determine which type of proof is best for a given problem.
  Explain the parallel between ideas of mathematical induction to recursion and recursively defined sequences.
  Explain the relationship between weak and strong induction and give examples of the appropriate use of each.
  State the well-ordering principle and its relationship to mathematical induction.

  Basics of Counting

  Learning Outcomes:

  Apply counting arguments, including sum and product rules, inclusion-exclusion principle and arithmetic/geometric progressions.

  Apply the pigeonhole principle in the context of a formal proof.
  Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application.
  Map real-world applications to appropriate counting formalisms, such as determining the number of ways to arrange people around a table, subject to constraints on the seating arrangement, or the number of ways to determine certain hands in cards (e.g., a full house).
  Solve a variety of basic recurrence relations.
  Analyze a problem to determine underlying recurrence relations.
  Perform computations involving modular arithmetic.

  Discrete Probability

  Learning Outcomes:

  Calculate probabilities of events for elementary problems such as games of chance.

  Differentiate between dependent and independent events.
  Make a probabilistic inference in a real-world problem using Bayes’ theorem to determine the probability of a hypothesis given evidence.

  Measuring Algorithm Complexity

  Learning Outcomes:

  Be able to meaningfully compare the asymptotic growths of pairs of functions.

  Graphs and Trees

  Learning Outcomes:

  Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each type of graph/tree.

  Be able to prove elementary results about graphs and trees, such as:
  In any graph, the sum of the degrees of the vertices equals twice the number of edges.
  In any tree, the number of edges is one less than the number of vertices.
  Model a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system.

Source: Discrete Mathematics Preparation from Williams College Computer Science Department


Is it bad to introduce language features in ways that are different than they will be used in practice?

This sort of thing is perfectly valid and valuable, provided that students already understand the underlying structure. So if they understand your first loop without continue (but with the print in place) the adding continue lets them see the effect dramatically.

The same is true of your second example. If they understand strings as arrays or lists (or ... whatever term is appropriate in your language) then introducing the [] "box" operator as selection makes sense.

But I wouldn't write a large program as an exemplar of good programming if it had these kinds of things.

But note also, that throwing in a continue in a loop is sometimes good for debugging, so it isn't entirely useless as a technique in "real" programming.

tl;dr teaching by showing modifications to a known base is fine.

By the way. In some languages asking students to decipher obfuscated code can be a useful exercise to make sure they know the basic rules. Asking them to clean it up is even better.


Good example of what isn't a system call?

The simple breakdown is:

Anything that performs input/output involes a series of system calls.
Anything that's purely computational doesn't involve system calls.

Both of these statements have exceptions (I/O through memory-mapped files or peripherals is I/O without syscalls, calling a hardware accelerator or allocating memory is syscalls without externally visible I/O) but they're a good approximation.

So here are some examples of operations that don't involve system calls:

Getting or changing the value of a variable.
Arithmetic operations on integers and floats.
Conditionals and loops whose body doesn't involve system calls.
Operations on strings such as searching, joining, splitting, etc.
Manipulations of data structures such as lists, arrays, matrices, trees, etc.
Memory management, as long as the program doesn't need to obtain more memory from the OS.
Printing to a buffered stream, if the buffer doesn't get flushed during this print call. Likewise, reading from a buffered stream, if enough bytes are available.

It would help to demonstrate by showing the system calls made by some programs, e.g. with strace on Linux, with dtruss on macOS or with Systrace under Windows. Compare a program that does a lot of I/O with one that does one big computation and prints the result.

The case of buffered I/O, suggested by ctrl+alt+delor, is an interesting one because the same library functions may or may not trigger a system call depending on the state of the system.

There is sometimes possible confusion between a library call and a system call. Unix programmers in particular tend to believe that what is documented in section 2 of the manual is system calls, but this is not true on a modern Unix systems. Every function callable from C is a C library function that's a wrapper (possibly very simple, possibly even a macro rather than a function) around a system call that usually, but not always, has the same name and takes more or less the same parameters. You can observe that on a modern Linux/x86_32 system, where many system calls have been upgraded from 32-bit arguments to 64-bit arguments, e.g. strace ls will show calls of getdents64 and fstat64 rather than getdents and fstat. Under the hood, system calls and library calls have a different calling convention. At the very least, a library call involes a jump/branch instruction while a system call involves a privilege change instruction. Depending on the system, the rules for placing arguments in registers may be different.

You can discuss how a program could make as few system calls as possible by starting from strace /bin/true. Most of its syscalls are due to dynamic linking, so write that one-line program, compile it statically and look at the remaining system calls. Reduce it even further with a more minimalistic libc such as dietlibc.

# Install dietlibc, e.g. apt-get install dietlibc-dev on Debian
$ cat a.c
int main(void) {return 0;}
$ diet gcc a.c
$ strace ./a.out
execve("./a.out", ["./a.out"], [/* 82 vars */]) = 0
arch_prctl(ARCH_SET_FS, 0x7fff98099fe0) = 0
_exit(0)                                = ?
+++ exited with 0 +++


How to teach algorithms: implementation or application?

The answer here, as it seems to be so often, is "it depends." The courses you've compared are comparing apples to oranges. Which are you trying to make, apple juice, or orange juice? You have to select to version implementation or application, which best moves the lessons, and the students, toward the objectives and goals set for the course.

The Apples

Coursera (AP CS A): The students are provided the finished algorithms and expected to apply them properly to solve some larger problem. The emphasis is on solving the problem with the given tools, not creation of the tools. All the coding, by the student and supplied to the student, is done in Java.

Target

Java
Object-oriented methodology
Problem solving

Pros

The students have a firm foundation in Java and are ready for 2nd semester college courses employing Java
The students can understand, and use, the object-oriented programming paradigm common in most newer development models.

Cons

While students will have more to learn in Java before using it professionally, they will need to return to the beginning to switch to a different language.
The students will have a good grasp of using existing implementations of common algorithms, yet not have the skills to develop new algorithms to solve problems they don't know about yet.

The Oranges

CS50 AP (AP CSP): The discussion leads from comparing the algorithms to see how they do what they do, and probably the costs of doing it each way, to creating the code that will actually do that sort. The clear pseudo-code that they are given the programming assignment was presumably developed during the discussions of the algorithms, and is merely repeated in a concise format for them to convert to C code. They are learning how to conceptualize the objective, work through creating the algorithm and carry that into live code.

Target

Computational thinking

Pros

The student have a firm foundation for implementing new algorithms, as well as an understanding of how to apply current, and new, algorithms
The students are equipped with an understanding of how to apply computational thinking to solve new and unique problems not yet reduced to algorithms

Cons

The students may have used a language which is not used in later courses, so they will have learn a new language to continue with programming courses
-The students may not have been exposed to, or practiced much with, the object-oriented approach.


What intro CS coursework is most useful for life science students?

I'll say upfront, I'm familiar with both life sciences and CS, but I've never applied one to the other.

In life sciences, computing is used for a lot of heavy processing. Stuff in genomics and molecular modeling, for example. It's not fast work. Efficiency, then, must be important for researchers to know about. The course you're designing should cover Big-O and and related topics in its discussion of algorithms.

That theory won't be much use if the researcher can't communicate with the computer. I'd say Java may not be the best language to use. The upside that's usually cited is that it's very common, and similar to other languages in industry, but these students aren't going to be professional programmers, so that doesn't really count for much here. With Java, you'll also be spending a lot of time teaching semantics about the language itself rather than CS principles; time you can't afford to waste if you get only a single course with these students. Alternatives: Python seems to be used more in science, and Ruby has a nice learning curve. Both are well-established languages with plenty of documentation and communities available online.

Doctors and vets who are frontline healthcare provider types rather than in-the-lab researcher types are more likely to be users of software than writers of it. Depending on specialty, they'll be dealing with assorted medical records suites and similar programs. They should understand principles of cybersecurity, including more technical things like how passwords really work (or, just as important, fail, e.g. lack of salting or e-mailing in plaintext) and what makes them important as well as less technical ones such as social engineering, which are often both easier and more effective.

(Thanks, xkcd 538.)

Doctors and researchers are already looking at images on computer screens a lot, and I don't think I'm predicting the future too much by saying that's only going to increase. Understanding how lossy compression works, or JPEG format tradeoffs, and why the "zoom in and clean that up" CSI magic from TV doesn't happen in real life could be useful.

Beyond all that, there are some fundamentals that everyone should know, life sciences or not. The basics of how a computer operates, so that it's not a mysterious magical process between pressing keys or tapping the screen and pixels lighting up. Some brief coverage of programming, algorithms and data structures. The fact that no matter how fast we make computers, there are some problems they can't solve, and we can prove that using math (even if you don't go through the proof itself).


I finally found out that the right keywords for what I was looking for, given the course objectives and the course content are:

Service-oriented software engineering
Service-driven software
engineering
Service-oriented software architecture
Service-driven software architecture
Services-centered software architecture design, ...


What's a good platform for independently teaching computer science and programming?

Your question is quite broad, but I think you're suggesting that you wish to tutor, and wish to tutor programming specifically.  In which case, I'd consider tools like Zoom and repl.it.
The ability to live-code alongside your tutee, and watch as the work, closely approximates the experience of sitting at the same computer.  A video-conferencing app then allows you to talk directly, and the whiteboard feature of Zoom allows you to draw on a common paper together while you analyze problems together.


Do automatic style hints help students to understand the language they're learning?

In my experience, immediate feedback is helpful in speeding along development, but rarely enhances understanding.  In fact, I am often frustrated with the immense level of help that is provided to my strugglers, because they wind up moving words around until whatever they've written stops being underlined.

The only exception to this has been for norms that don't cause errors, such as using CAPS for static final variables in Java.  In those instances, it is very helpful to have some sort of indicator that what they've done isn't perfect.

Edit: Now that I've seen your edit with examples, it seems like what you are contemplating is basically all of the stuff that I feel is helpful.  In which case, I believe that it could be very helpful!


Is it possible to ensure division of labor on a group assignment?

Make each group member explicitly be 'responsible' for one aspect of the project.

Let's think about why group work is a useful tool in terms of teaching your students. I'd imagine one of the big reasons you would assign a group task is to prepare your students for a job, working with a team to build a product. In the workplace, you typically have a way of assigning individual roles and responsibilities; if you're building a website, you generally would have someone responsible for design, someone for the backend logic, etc.

You should do the same thing here. Specifically require that your students build a plan, with each member being given a role that they are individually responsible for, and before allowing them to proceed, make sure each role is relatively equal in scope. You wouldn't want Alice to have ten times the work of Bob in the plan—it won't give you the scope to analyse each bit of work individually.

Obviously, each piece of the project likely depends on another, so it's very difficult to isolate each person's contribution individually. That's why I'd suggest not weighting the group work too highly, because the difficulties of evaluating the outcome far outweigh the benefits of making the group work count for a high percentage of the grade.

Carnegie Mellon's Design & Teach a Course section has some useful tips:

  In addition to evaluating the work of the group as a whole, ask individual group members to demonstrate their learning via quizzes, independent write-ups, weekly journal entries, etc. Not only does this help you monitor student learning, it helps to prevent the “free-rider” phenomenon. Students are considerably less likely to leave all the work to more responsible classmates if they know their individual performance will affect their grade.

  To create individual accountability, some instructors combine a group project with an individual quiz on relevant material. Others base part of the total project grade on a group product (e.g., report, presentation, design, paper) and part on an individual submission.

You'll need to think about your aims. Do you want to test the group's ability to spot people not contributing as part of the teaching? If so, don't put in those safeguards, and see what happens. If you just want to test their CS knowledge, make sure that you can fairly evaluate individual contributions, as well as the overall result.


What statistics should be in a computer science degree?

My first thought to provide a bit of something for you to go on was CS2013: The ACM/IEEE Joint Curriculum Guidelines for Undergraduate Degree Programs in Computer Science. This is available at https://www.acm.org/education/CS2013-final-report.pdf. I've copied out two relevant passages from that here:

"Computer science curricula should be designed to provide students with the flexibility to work across many disciplines. Computing is a broad field that connects to and draws from many disciplines, including mathematics, electrical engineering, psychology, statistics, fine arts, linguistics, and physical and life sciences. Computer Science students should develop the flexibility to work across disciplines." (p.20)

"Similarly, while we do note a growing trend in the use of probability and statistics in computing (reflected by the increased number of core hours on these topics in the Body of Knowledge) and believe that this trend is likely to continue in the future, we still believe it is not necessary for all CS programs to require a full course in probability theory for all majors. (p.50)".

It is worth searching that document for 'statistics'. It is mentioned in many other areas, but mostly as something learned in other areas such as Networks, HCI, Cryptography, etc.

The December 2013 issue of ACM Inroads had a good article (http://dl.acm.org/citation.cfm?id=2537777) on the role of mathematics in CS. This included a section on "The Current State of Mathematics in Computer Science Curricula". The article states that "The most-connected mathematical topic [to CS] by far is probability and statistics" and has some references to such. They also present the mathematics requirements of 25 'high quality' CS programs. Stats and Prob was required for 15, Calculus for 21 and Discrete Mathematics for 22.

http://dl.acm.org/citation.cfm?id=1240202 discusses statistics in liberal arts CS curricula.

Searching the CITIDEL syllabus collection (citidel.villanova.edu/ then look for syllabus collection) for 'statistics' might be worth a try, although the website has been varying between unresponsive to slow to responsive lately. Also, some of the material in there is a bit dated, but then again, statistics dates fairly well!

Given that in 2013 60% of sampled 'high quality' CS programmes had statistics, maybe it is more prevalent than you think. Perhaps the best way to obtain the most up to date information is to check the websites of several good CS programmes and hope that if they include statistics, the syllabi are available online.


What should be in a CyberSecurity Course in secondary school?

The course that I offered was all about gdb, hexdumps, buffer overflows, and format string vulnerabilities.  As a textbook, we used Hacking, by Jon Erickson.
 AP CS A was a prerequisite of the course, though I permitted students to join the class if they were currently enrolled in that course, as long as we had a discussion outlining expectations first.  There were no mathematical prerequisites.

The course was designed with the assistance of a Navy officer. The students practiced fuzzing and hacking (admittedly insecure) programs on old, virtual systems.  This was quite deliberate!  I didn't start by asking, "what will the kids be able to gain entry into at the end?"  Instead, I posed this question to the officer: "High school students are also quite young, so there is little pressure to give them useful skills right now. CTF competitions abound, and my students are already joining those. What is hard to pick up from CTFs, but nevertheless is ultimately quite central? What can we offer them that will help them develop into top minds in this field in the future?"  And that became the central mantra of the course.

Everything was done by hand at a *nix prompt, and they got a fair amount of practice reading and examining hexdumps.  By the end, they could look at a hexdump and see at a glance where, for instance, the text strings were stored.

It was ultimately a computer science course on binary and hexadecimal, on system variables, and on the intricate operations of a runtime stack.  As an additional bonus, they all got pretty adept at navigating a bash prompt.  The students kept asking for network hacking as well, though we didn't have time to get that far.

The material was quite dense and unintuitive.  (Though, I suppose, if these practices were intuitive, they wouldn't have been vulnerabilities in the first place.)  It was an extremely difficult class, although the material itself kept the kids pretty interested, so you will have that working in your favor if you go down this road.


How to make someone enjoy programming if they don't like the products they make?

I don't normally answer questions that I've voted to close, but I'll make an exception here. I think your quest is doomed. Sorry.

I also think that pressing is just going to make it worse. Perhaps you can impress that on the mother.

One can be successful in applied math or physics without programming. It is a helpful tool, but not essential for everything. She can be a success without it, most likely.

But, the time will, perhaps, come when she needs to use programming to solve some problem that really drives her interest. That is the time that you might be of help, but not now. It is now just a distraction. Wait for the need to become obvious to her.

In Tai Chi we learn to be soft in our actions and movements. But that doesn't mean they are ineffective.


An Intro to CS course in C++ for CS majors: laying a solid low-level foundation or simple tools and algorithmic thinking?

You wrote:

  The first incentive is that the course needs to provide a solid foundation, which includes understanding how things work under the hood and implies teaching pointer, raw array and string, dynamic allocation etc.

This is not the only definition of a "solid foundation".  I would suggest that your second approach is also a "solid foundation", but towards a different goal.

You could make a wonderful course out of low-level computer workings, and your students could learn a tremendous amount.  Your "second incentive" is higher-level, and you could make a wonderful course out of this as well.

In truth, I am not sure that your goals are entirely opposed to one another.  You can teach high-level thinking and still mention what is going on under the hood, and you can teach good coding style in a low-level language.  No matter which basic approach you take, you really should make an effort to help students see at least a bit of the other side.

But in answer to your question about a basic initial approach, I might suggest the following: we often think about introductory courses as preparing us for our long-term futures, but I would argue that on a far more practical level, course 101 lays the foundation for 102, 103, 201, 202, 303, and so forth.  You are setting the stage for future learning.  Therefore, the best (introductory) course is the one that helps the students get the most learning out of their later, more advanced courses.  After all, those courses are where the rubber will really meet the road.

So, what will set them up for success as they proceed through your entire program?  Have a few conversations with your colleagues, and take a careful look at your program's course catalog.  The answer may become fairly obvious.


Using questions from a code-competition website in homework and exams

Whether this is a good plan or not depends on some things, most especially the nature of your students.

However, it seems a bit too unstructured. If you have a general mix of student ability it could cause problems unless you incorporate the questions from the site(s) more formally into your teaching. There are a lot of questions available, I would guess and some of your students will panic, thinking that (a) they need to do everything or (b) it is hopeless. This is a special problem if these extra questions are above and beyond all necessary assigned work.

However, one good aspect of your plan is to show them in advance the kinds of things that they will be expected to know and that other students also regularly deal with. Much better that than hiding your intent and springing things on them unexpectedly.

But I think a better plan is for you to incorporate a sampling of the found questions into your labs and homework assignments. For the most challenging questions you could have five minute brainstorming sessions as part of several class periods.

In short, as part of the regular process it should work out, but if it is completely "extra but not formally rewarded" work it might backfire on you.

An additional dimension here, of course, is that you could use the site(s) to teach yourself how to ask better questions. And your focus on "creative questions" rather than necessarily "challenging questions" is a good one, I think.


How can I get through very long and very dry, but also very useful technical documents when learning a new tool?

Man, I'm right there with you. I understand completely your situation, as I've been there myself many times.

The key, I find, is not reading the tutorials.

Instead, I pick a few projects - starting with something that's "hello, world" level. I google and read enough to be able to do that. Then I pick a slightly harder project - for Vulkan, maybe pick a scene of intermediate difficulty, and google and read enough to do that.

If you keep doing this, you very quickly obtain a practical base of knowledge. There are, however, disadvantages to this - obviously, there will be holes in your knowledge, and you could miss style guidelines depending on what you're looking at to write your code (e.g., when I first learned python, I came into it knowing how to program in javascript - so my first instinct was to write variable names in camelCase, and it was only after several years that I actually read PEP8 and changed to under_scores, though in my defense I didn't even realize style guides were a thing at the time).

You might even wish to go through this approach, and then read through the tutorials with the perspective of someone who's "brushing up" - this might fill in the crevices the more trial and error method doesn't fill.

If, however, you wish to fully work through the documentation straight off, I'd recommend reading a paragraph/section, and writing down something about how you'd use what you just learned about in a real program - i.e., mentally applying the small details. You want to build up a 'web' of details, with lots of connections between the nodes, so that every node is much easier to 'get to' (remember). The more you know, the more you remember (as odd/obvious as that sounds).


Any materials on fractional/quotient languages?

An Introduction to formal Languages and Automata
Included in the University of Nottingham's Languages and Computation Course resources

The book An Introduction to Formal Languages and Automata  by Peter Linz can be used as an alternative or complement to Hopcroft-Motwani-Ullman.

An excerpt from

The latest edition of Linz’s theory textbook follows the same outline as the previous one: it begins with a chapter on mathematical preliminaries; moves through the Chomsky hierarchy (regular, context-free, and recursively enumerable languages, with a brief mention of context-sensitive languages); and concludes with one chapter each on the topics of undecidability, alternate models of computation, and complexity classes.

The presentation suits your needs : gives formal definitions, provide examples, give mathematical justifications (usually complete proofs), and end with a set of exercises. Solutions to some of the exercises appear in the appendix.

More than anything else, the book needs to provide readers with a broader framework that naturally motivates the many topics covered. Instructors looking for a general reference on automata and formal languages, or a textbook for a mathematically sophisticated audience, should take note that Linz’s book lacks a comprehensive bibliography (the one-page list of references consists primarily of other theory textbooks).

Overall, the work is appropriate for the author’s stated purpose: a textbook for an introductory undergraduate course on the theory of computation—provided that the students have sufficient mathematical preparation.


Book to substitute "Compilers: Principles, Techniques and Tools" by Ullman et. al. (popularly known as the red dragon book)

The "problem" with the dragon book is that it is so complete; intentionally so. Over its lifetime there have been tremendous advances in the theory and practice of building compilers. If you want "state of the art", then you want the dragon book, probably a later (harder) edition, even.
But it is a bit much, as you have seen, for a first course, or an overview of compiling. It is often used in graduate courses, for example, and, even then, in a follow up course to one in Language Principles which discusses much of the underlying theory separately.
While it is hard to find and a bit expensive, one of the best books for an introduction, and separately a bit of real literature in CS, get a copy of Brinch Hansen's On Pascal Compilers. It shows how to build a compiler as well as a machine to execute the code using Recursive Descent Parsing, which is easy to understand and suitable for LL languages (with a few extensions for non LL features).
Most commercial compilers use LR compiling techniques even if the language is LL, simply for efficiency reasons, but the theory is much harder as are the compilers. For state of the art understanding you need to delve into LR, but for a first introduction, LL is enough, and easy to understand.
LL compiling is also called Predictive Parsing, since it is easy to look at a language statement and choose a method for translating it, usually using keywords. The suitable languages for LL parsing are also easy for a human to read and understand. If a language (feature) absolutely demands LR parsing, then it will be difficult for a person to read.
For example, the Dangling Else Problem in if statements is a consequence of the construct not being LL, though  LL parsers usually have special hacks to handle this common construct.
Once you can handle Hansen's book, the dragon book won't be so daunting.


Where can a student independently learn elementary recursion, preferably in Java?

Often times, google is our best of friends (I hope). A rather simple search leads to a very informative site:

http://introcs.cs.princeton.edu/java/23recursion/

It is very thorough, and explains many use-cases for recursion.

Another very handy resource is, inevitably, Stack Overflow: this question also provides some information, but it is rather specific. Instead of staying there, one can navigate to the Related Questions section, and from there choose a promising question (usually the one with the highest votes, but not always) and reading it. And so on, and so on... (recursively ;)).


How to teach students not to use jump statements

I don't believe that your question is entirely valid; some languages require jumping.  The first principle, therefore, is to follow the norms of your language.

However, I suspect that you are asking about languages that discourage (but do not ban) jumping, such as Java, or C++.  In these cases, I agree with Peter that the solution is to give them the negative learning experience of having to parse code with bad jumping usage.

I would only add two things to what he said:

Do not teach about break statements and jump statements if you can avoid it until they really have have absorbed the norms of looping.  This can take some time.  If kids start using them earlier than you would like, simply tell the students that, while such statements have a time and place, please avoid using them for now.
As an idea for an exercise, just make some code that has for loops and replace them with awful while(true) loops.  For instance, consider this bit of foul excrement, which will print out the first 10 Fibonacci numbers:

int daffyDuck = 10;
int[] bugs = new int[daffyDuck];
bugs[0] = 0;
bugs[1] = 1;
int whynot = -1;
while(true){
    whynot = whynot+1;
    int whistlersmother = 0;
    if (whynot == 10) break;
    int animeRocks = 0;
    while(true){
        if (whynot-animeRocks <= 2)
            whistlersmother += bugs[animeRocks];
        animeRocks++;
        if(animeRocks>whynot)
            break;
    }
    bugs[whynot] = whistlersmother;
    System.out.print(bugs[whynot]+",");
}

Give it to your students, but don't tell them what it does.  Give them a chance to attempt to trace it.  Tell them that they only have 4 minutes (240 seconds!)1 to figure out what it does!  Presumably, they will struggle mightily to figure it out, but mention that, if anyone thinks that they've solved it (and can back that up), not to call anything out, but to instead raise their hand.  If anyone does call you over, ask the to whisper the answer into your ear, and if they get it right, ask them to silently try to re-write the code segment in a way that would be easier to follow.

Now, give the class a new version, with another 240 seconds.  Do not mention that it is exactly the same code as before, but with nicely-defined loops (and modified variable names).  Once again, tell them not to call out the answers.  The process here should be the same.

    int n = 10;
    int[] f = new int[n];
    f[0] = 0;
    f[1] = 1;
    for(int c = 0; c < f.length; c++){
        int s = 0;
        for(int j = 0; j <= c; j++){
            if (c-j <= 2)
                s += f[j];
        }
        f[c] = s;
        System.out.print(f[c]+",");
    }

And finally, give them this version, same 240 seconds, same procedure:

    int fib_nums_to_print = 10;
    int[] fibonacciNums = new int[fib_nums_to_print];
    fibonacciNums[0] = 0;
    fibonacciNums[1] = 1;
    for(int currentNum = 0; currentNum < fibonacciNums.length; currentNum++){
        int sum_so_far = 0;
        for(int j = 0; j <= currentNum; j++){
            if (currentNum-j <= 2)
                sum_so_far += fibonacciNums[j];
        }
        fibonacciNums[currentNum] = sum_so_far;
        System.out.print(fibonacciNums[currentNum]+",");
    }

At this point, you can reveal, for those that hadn't figured it out yet, that all 3 of these bits of code were the same function.  Ask them what made the later versions easier.  They should be able to pinpoint the two problems pretty easily.

Point out that loops can grow to be very, very large - hundreds, or even thousands of lines of code long.  Ask them why the while(true) version of the loop would be especially problematic in longer code examples. Ask them where, in their opinion, would it be best in such long code for the coder to make clear when the loop will actually end.

All of which brings us to the final principle: we want to be able to figure out, at least in 99.9% of the cases, the basic logic of what will cause a loop to terminate at the moment that the loop is declared, because otherwise, we are left hunting and guessing.

1 - Any time you mention the number of seconds along with the number of minutes, the kids suddenly feel time pressure.  It's a very consistent trick to get the kids to focus on a short task.


What and where should I study for competitive programming?

If your aiming for the IOI, the first step has to be figuring out how to get onto your country's delegation.  In the USA (where I am), that means USACO.  If not, then you will have to determine what that pathway is.  Every country has some method of determining delegates.
The next step would depend a lot on how those delegations are formed within your country.  You may have to join a team, and there will presumably be some sort of coach.  Most of your preparation and learning will probably focus on the competition used in your country.
And in terms of what to study, the competition itself looks to be very, very focused on algorithms.  Until you can find more specific resources to the competitions within your own nation, you could spend time practicing the older, published IOI problems and Project Euler problems, which seem similar in nature.
It's hard to be more specific than that without knowing your country of origin.
Good luck!!


How do you assess students' understanding of abstraction?

tl;dr: Just say no.

This question is difficult on many levels. I seems to me to be a land mine of misconceptions and has the possibility to lead to poor teaching practice.

First the difficulties

Only concepts can be abstract. Abstraction is about ideas. Animal is a concept. Mammal is a concept. Animal is more abstract than Mammal since it contains the idea of Mammal, but isn't restricted to it. The kitty sitting on my hearth is concrete, not less abstract than Mammal. The kitty isn't a concept it is a thing.
Given some ot the examples, there is a misconception about what is abstract and what is concrete. Physical things are not abstract. One can't be more abstract than another. Even things that aren't physical, but which can be manipulated, are concrete, not abstract. A LinkedList (Java) isn't abstract. It is concrete. List, on the other hand (an interface) is abstract.
In computing there are many, many different kinds of abstraction. Even the concept of a while loop is an abstraction. In OOP languages classes implement abstractions. Interfaces (even if the language doesn't have that explicit feature) are abstractions. So, Python has interfaces, though it has no language feature with that name. If two classes have the same interface they are realizations of the abstraction, but neither is more or less abstract than the other. If one interface contains another interface then it is more abstract.But we also have data abstraction. Lists and Maps define an interface (an abstraction). They can be implemented/realized many ways. Each realization is concrete, not less abstract.
The web site cited seems to be trying to test everything with Multiple Choice Questions (MCQ). I question both the possibility of that and the wisdom of it. Some thing are complex MCQ are simple. Trying to push the assessment of complex things through such a small funnel seems misplaced to me - even foolish. I'm pretty sure that MCQ also advantage certain students and disadvantage others. They are fine for rote memory and facts, but pretty poor for deep understanding. I have nothing against their use unless it is overdone. MCQ are also difficult to validate. The wisdom of groups isn't enough. It takes statistical measurement and cross validation to do a good job of it.
The Font Construction example given in the question also seem to be testing specific vocabulary. This example threw me completely. I think I could eliminate one answer, but also think I could justify each of the others if given the chance. If it is specific vocabulary it is just rote memory and hoping that the student "remembered" to remember the right thing.
Often, getting a MCQ wrong and then later learning the correct answer can sometimes leave students simply puzzled and frustrated. This results in a destructive game that I'd rather not play.
MCQ try to put a lot of thinking into the questions so that no one needs to put any thinking into the answers after the student finishes. This may scale well, but is a sub-optimal form of education. After all, it is the students thoughts that we want to get a handle on in assessment.

I don't believe that a single, or even a small number of MCQ could capture the student's understanding of abstraction or any similarly deep concept. I think that if you had quite a lot of questions (say 20-50 of them) you might be able to get a handle on it, but it would take very careful cross evaluation of the answers given to be able to say with any confidence. Getting a single question wrong likely tells you almost nothing. And that, of course, makes MCQ less valuable for its main use - quick and easy evaluation.

I could, on the other hand create a bunch of questions that start to get at the student's understanding. The ones I'd like to use are short response questions, but some can be simple choices.

Assuming that the student have a common language background, something like "Is java.util.List abstract or concrete?" "Is java.util.Collection more or less abstract than java.util.Map". One choice for the answers needs to be neither of course.

You can show code fragments and ask whether they implement an abstraction properly or not. But a follow up "why or why not" gives you better information. And some of those questions would necessarily be a bit long to be meaningful and thus take some time for the student to evaluate.

"How can functions be considered abstractions?" Well, that was poorly stated, since a single function is concrete, not abstract, so you need to be careful: "How can the idea of a function be considered an abstraction?" is better. You could probably give a few suggestions for answers to this to turn it in to a MCQ, but it would be hard to come up with four, of which three were viable and yet not correct.

However, I've only hit the surface here and only explored a very small part of the abstraction space in computing.

Caveat: I never had to teach or evaluate a hundred or more students at a go. My classes were always small enough that I could use better evaluation techniques than MCQ, though would be likely to use a few in a larger assessment that allowed the students more creativity. If you do have to evaluate 800 students I hope you have help. If you don't something is deeply wrong. I note that Harvard CS 50 is run by a team of about 80 people, with quite a number of roles. I hope that each student has some individual person responsible for them. It isn't the professor.

My initial "just say no" is to the idea that you can completely evaluate a student with MCQ, not that they can't be useful, dangerous drug though they are. And note that I have the highest respect for Simon Peyton-Jones.


How to teach so that your student doesn't feel stupid?

The idea is that I somehow make it sound... too easy? Like it should
  be obvious. But when it doesn't immediately click, it makes the
  listener feel stupid. And that's when learning stops and inecurities
  kick in.

This reminds me of the first time I was teaching an intro to programming class and I was going through a live demo of how some code worked. I mistakenly had an error in my code and got a compilation error. One of my students gasped and said, "You get those too?!"

Previously, it hadn't occurred to me that students thought that people who are "good" at programming didn't get errors. They thought there was some inherent quality that I had that prevented me from making errors like they did.

I'd recommend modeling the problem-solving process. Try doing one of the problems yourself and just let her watch and ask questions. Think aloud and describe everything that goes through your head. Even try explaining different approaches you might consider in solving the problem. It helps demystify the problem solving process of programming when novices get to witness your thinking (and debugging) process.


Why Computer Science students learn Digital Logic Design?

Logic is used A lot in programming.

There is little difference between hardware and software. It is just an implementation detail. The choice of what goes where is a balance between cost and speed, but where ever it goes it is just logic: if you implement it in Python, C♯, assembler, HTML, electronics, or mechanical.


How should floating point inaccuracies be explained and justified?

If your students can understand why:

$$\frac{1}{3} = 0.\dot{3}$$

then you can explain simply why floating point calculations are "broken".

When you divide one by three on a simple calculator, you can observe that it usually shows 0.333333333... until it runs out of digits (unless you have a more advanced calculator that can show recurring digits like this).

You can explain that the phenomenon observed here is because of the same thing: one third in floating point is an infinitely repeating sequence:

$$ \frac{1}{3} = 0.0\overline{10}_2$$

If we could store that fully, then multiplying it by three would indeed give us one, as expected. But, like our naive calculator, we don't store all the bits in the sequence, so you end up with a slight inaccuracy. Pointing out that
$ 0.333333333 \times 3 = 0.999999999$ should be enough to illustrate the point that with an infinitely repeating decimal, you will not get the correct answer unless all the digits are taken account of (and you'll always be ever so slightly off the correct value, no matter which approximation you use).

It should then be clear to them that unless you use the exact value of $\frac{1}{3}$ in the binary representation, you will also get inaccuracies.

Something to note is that a finite decimal may be a repeating binary fraction (a significant example is $\frac{1}{10}$, which is $0.1_{10}$, but $0.0\overline{0011}_2$), but not vice versa. Clearly, because of this, seemingly finite decimal numbers added together can lead to an infinite binary fraction, and hence an imprecise answer.

If your students are also familiar with scientific notation, then explaining the floating point system of a significant and mantissa should also be relatively painless. Since floating point can represent both very small and very large numbers, representing numbers as $\text{significand} \times 2^{\text{exponent}}$ is the most flexible option. You need not elaborate much further than that, though, I don't think. As Ben I. mentions, a functional knowledge of floating point is needed, but the internals are probably not needed at this stage.

I don't see any reason why you shouldn't introduce the reason why floating point numbers are inaccurate to them quite early on — it's probably worse not to tell them, and leave them to be very confused when their program doesn't work because of the tiny inaccuracies ruining comparisons.

I think floating-point-gui.de does a great job at explaining, very concisely, without any implementation details (and you can read on about the details if you want). Using that as a resource may be helpful to find the right level to teach.

If you want to give your students something to play around with and get an understanding of the format of IEEE 754 floating point, you could try this floating point number converter which will show the representation of any number you enter.

It might also be wise to introduce a strategy to solve this problem—epsilon values. It should be relatively straightforward to explain that you just compare if a number is 'close' to what you expected with a floating point operation, rather than exactly equal; there are plenty of resources available that explain epsilon values further if necessary.


What do A-level students, that have not done GCSE, struggle with?

Insufficient programming experience is the thing that impedes progress at A-Level, in my experience.

The current UK A-Levels from OCR exam board (less so AQA) emphasises "Computational Thinking" (CT), such as abstraction, as a theme of the course. CT, as delivered in the course material, has some overlap with stages in system development stages such as analysis. Also there is another strand "problem solving" and another "computational methods". There are more "traditional" topics such as data structures and algorithms. There are questions in the exam where a student has to analyze, correct, modify or create from scratch a pseudocode "snippet" to address a particular small-scale algorithmic problem such as navigating a tree data structure.

With that context, the most basic exercises in the course are usually beyond those A-Level students with little prior exposure to programming. The rigours of getting code to run or compile without syntax errors or fix basic logical errors is an alien task to these students and they often give up, submitting source code that does not compile or run (if Python). These students often have no "framework" of what an algorithm is; to take input data and transform it in some way. Lack of this "mental framework" means CT is just "pile of words" to neo-programmers; they have no concrete experience against which to relate abstraction, decomposition, recursion, concurrency etc. Often assignments are submitted, which if in a programming language don't run, let alone produce correct outputs under any inputs. Pseudocode assignments are very difficult to mark because of a host of basic syntax errors. For some, submitting "something" is "job done" by the student because the time to develop the necessary skills, understanding, approach, identifying and diagnosing errors is just not "there". Pseudocode is used because the exam uses it rather than a specific language such as Java or C# or C++ or .... to "level the field" among all candidates who may have been taught by someone with knowledge or preferences for a specific language.

There is also a requirement to produce and document a non-trivial program / system - weighted at 20% of the final course mark. Those students with no programming background make slow progress in all stages of the development and the resulting code is usually rather limited in technical complexity - although there is ongoing debate on teacher's forums as to the necessity for "complexity" in the project.

One possible explanation for this (and it's just my opinion) is the inexperienced students haven't had exposure to 1) short term failure of their efforts, i.e. their programs don't work, but 2) the reassurance that eventually, with effort, they can fix their "local" errors and solve the overall problem. So, some prior programming experience develops the right perseverence mindset which I feel is more important than "good" programming style or wide/deep knowledge. Continued engagement will refine the skill.

It is entirely possible for a student with no programming background to develop those technical and problem-solving skills over 18 months - but it is rare - and often the student will drop out feeling the course is completely inaccessible. However, if the above sounds entirely negative our highest achieving student last year had no programming background prior to starting the course.


What do programming novices need to know when using MatLab?

With only 5 sessions, I would abandon the idea of building something cool, and focus with laser-like precision on whatever they need to know going forward in their coursework.  There is such a small amount of time to learn the basics of any programming language.

MatLab supports lambdas, objects, and GUI design, but unless they are going to get into rather serious programming, I imagine that you would steer clear of these.  (I don't know how you would cover any of them in 5 days with novices in any case.)

The danger in heading towards UI and a game is that they will come out without being able to do what they presumably need in the next class, such as matrix multiplication, or graphing an integral multiplication.  You may be better using your five sessions to delve into five areas of greatest need, as determined by the future required coursework of your students.


Take a look at the Edison Programmable V2.0 Robot. (https://www.robotshop.com/en/edison-programmable-v20-robot.html)  Available from Amazon.  Also Makeblock mBot Robot Kit (Amazon.com)

I have read some articles about the Edison be used in school successfully.  The Makeblock I just saw on Amazon.


Mental Model of Type Conformance/Subtype Polymorphism

The problem is that you don't really have subtype polymorphism here. While the language permits it, it is poor practice to change the interface (set of public methods) as you move down the hierarchy. I'm not speaking of the formal interface but only of the messages that an object is allowed to handle. Your class Vehicle doesn't have honkHorn, but a subclass does.

The problem with this is that if I have an object, I need to know its specific type to know what methods it supports. Some Vehicles support honkHorn, but others don't so I need to test.

This is, at best, ad-hoc polymorphism.

If you want true subtype polymorphism define a class as an interface or abstract class as you have done here, but all subclasses should exhibit exactly the same interface.

Then, if you define a variable to have the interface (abstract class) type, then it can refer to any object of any subclass and it can field any message defined at the top level. You never need to ask instanceof and you never need to cast.

It is, of course, harder to build a system keeping such a pure rule, but it can be done and it saves you a ton of grief later.

One of the reasons we want to build OO software is to let the system figure things out without explicit testing. If you change "interfaces" within hierarchies you are just back to ad-hoc decision making. You are defeating the notion of IS-A that the OO paradigm was built for.

In your example you can't really say that a Bicycle IS-A Vehicle. You can say that it is a Vehicle, but something more, and we have to determine what by ad-hoc means in many instances. Sometimes by declaring variables to have a specific type (rather than a general type) and sometimes by testing.

In terms of "contracts", if you change the contract as you come down the hierarchy, it wasn't really a contract.

Sadly, too many books don't understand this and define meaningless, and difficult to work with, "hierarchies".

One way to avoid this issue, is to define Vehicle as an interface and then define Bicycle as another interface that extends Vehicle. Now your intent is clear. Classes implementing an interface have only the public methods defined in their interface and nothing more. Now you have interfaces of concepts which is what they are really intended to model, and classes of objects that conform to specific concepts. This may be the mental model you seek, actually.

I discussed Polymorphism at some length here: https://cseducators.stackexchange.com/a/4050/1293

Let me add some things here to point to a better way. One of the lessons is that subclassing is generally overused. Some books present it as the "really big thing". Instead, programming by composition is much more valuable. When you create a class give it parts that are instances of some other, simpler, class.

For the immediate problem here. Give Vehicle a method makeSound. Give each subclass of it an instance field that refers to some kind of object that might make a typical sound. For a bicycle object it might be a Horn object. Then when any vehicle is sent the makeSound message it delegates the making of the sound to the object that is part of its composition. Delegation is the big idea here. Now you don't need to change the protocol in different classes. Just change the implementation, but giving different "parts" to different vehicles.

At least one very commonly used book has something like the following hierarchy. First a Point class. A point has some coordinates. Then, for the first (ugh) example of subclassing is a Circle class. This is "easy" to write, since if you subclass Point all you need to add is a radius value. But to a mathematician, is every circle a specialization of point?  It is backwards, of course. Taking it farther, a Cylinder can subclass Circle just by adding a height value. This makes it very easy to type in, but very foolish, both mathematically and from a program design standpoint. If you create a Cylinder, what sort of variable should you use to refer to it. If you don't use a Cylinder variable, then within the next few lines you are very likely to have to cast the variable, or, if you have put such things into a List then you are going to have to type case them (or equivalent) when you look at them again. Don't do that. But what can you do better. Use delegation.

When you build your Circle class, don't make it an extension of Point. Instead, give it an instance variable of type Point. A Circle is a different kind of thing. It isn't a point, but it HAS-A point as a field.

Likewise the Cylinder HAS-A Circle for its base. Much cleaner. The cylinder delegates some of its actions to its base when it receives a message. Likewise the base (a Circle) delegates some messages to its location (a Point).

Now you have a defensible design, but it might not have used subclassing at all. You get reuse (via delegation) and don't confuse the nature of things and require ad-hoc decision making throughout a long program.


What are healthy, productive ways to encourage students to progress to more advanced constructs as opposed to staying with the familiar?

I'm afraid that there is no single silver bullet.  The problem you've pointed to is very real, and isn't limited to students.  All of us tend to stick to our own familiar toolsets because, well, it's easier.  We know how to use them already.

Enter the Motivating Example.  This mythical thing makes a new topic so useful that the new topic is practically a requirement.  Want to motivate recursion?  Try having kids determine the file-size of a folder (including its sub-folders).  Want to motivate methods?  Try giving a main method that calls them, and ask the kids to create the code that will make everything work.

Finding a great, motivating example feels like a search for hidden treasure; it is painful and slow.  You're seeking something of great value, and it's hard to know where to look.  To make matters worse, a good motivator for one teacher may not work for another, because what makes a motivating example work is intricately tied into both the broader curriculum and what sorts of things the teacher emphasizes within the classroom.

And once found, they are indeed treasures!  Clean, motivating examples make the value of a topic immediately apparent to students.  Resistance melts away, and is replaced by enthusiasm for the new tool that is now making their life easy.

Sometimes I spend weeks trying to find a good motivator.  I've found that teacher communities (such as this very one!) can be great sources of inspiration for them, as can algorithms books.  Or, as Kevin pointed out in a comment (before it was deleted):

  As far as finding motivation is concerned, it may be helpful to look into the history of the construct. For example, foreach used to be called "the iterator pattern," and even appears in the GoF book under that name, before there even was a foreach loop. So foreach isn't about simplifying the code so much as it is about abstracting away the implementation details of "get the size of the container" and "get the nth element" into a single opaque accessor. That suggests that a motivating example might begin by introducing trees, showing traversal code, and then contrasting it with an array.

Even with all of these tools, there are no easy guarantees. I sometimes have to simply wait for my "Eureka!" moment, and teach the best I can in the meantime.


How necessary is UML for a course in object programming patterns?

As a professional software developer, I would recommend minimizing the time spent teaching UML.  Teach the patterns.  If they learn some UML along the way, so much the better.  But don't burden them.
In my experience, I've found value in using UML for somewhere around 3-5% of my work.  It usually provides its value after the fact, once I've already identified the design patterns, and I need to describe them to others quickly.  Often they don't actually need to understand, they just need enough of a warm-fuzzy to check off on my work.  UML is great for this!
All too often I find that I need something that isn't handled in UML (like handling dependent types), or something that can easily be explained in one sentence rather than a dozen fancy boxes (like object lifespan management).  I can't think of a time where I've ever looked at a UML diagram and thought, "wait... if I use the Decorator pattern here, I can make this diagram look better."  It never helped me for actual understanding of the patterns.  And I can't count the number of times where neither aggregation nor composition adequately described my relationships, leading me to fall back on just drawing a line between them and calling it a day!
That being said, use a tool for what it is good for.  In the cases where UML does a good job of describing the pattern, use it!  I love UML for drawing basic inheritance hierarchies.  But I don't think it needs to be taught.   It's simply the way you choose to draw the patterns so that you can point to boxes and talk to them.  If a sequence diagram is the right way to describe Mediator, use it.  Use it correctly, and don't spend too much time explaining what all of the symbols mean or why.  Don't worry about explaining why the activation box on the Mediator in the Wikipeida page is broken into two part.  Doing so will teach UML as one learns a natural language.
If any of your students go on to become systems engineers, they will have to learn UML the "right" way.  And they will get to learn all of the kludges we use to make UML work in situations where it shouldn't.  You wont want any of those in your course.
If you wish to support the students who will work under a systems person in the future, go with the natural learning approach -- show them the tools, and let them riff on them.  Let them express themselves in almost-UML.  Then construct the assignments in a way where requirements come down from a systems person in proper UML speak, and use that as your tool for teaching UML.