Significant algorithm from CS for DrRacket that emphasize cons, car, and cdr When my students move up to junior year, they make a series of transitions: from programming to theoretical computer science, and from imperative to functional programming.  We use DrRacket, and one of the goals of the course is to give them a very broad exposure to theoretical computer science.  Part of that is choosing labs that can be coded using the tools that they have learned so far.

They are already familiar with linked lists, Big $O$, $\Omega$, and $\Theta$, binary trees, the runtime stack, BFS and DFS before they arrive at this class.  They have also been exposed to recursion a fair amount (though most of them are not highly skilled at it yet)

My first lesson with them in Racket is called "Cons, Car, Cdadr, and Contracts" and it contains exactly the sorts of material you would expect from that title.  I have created a lab that makes them use these tools, but adds up to no further significance.  What I want is an algorithm that has some theoretical significance and that they can do with those tools.  The algorithm itself can come from any part of computer science - I just want it to be something worth exposing them to in the first place.

The lab goals would thus be two-fold: first, to give them a chance to play around with and familiarize themselves with the beginnings of Racket.  Second, I want to give them a chance to learn about an important algorithm.

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

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

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

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

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

These two additional resources may spark some ideas as well:

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


How to get girls more interested in computer science? It’s no secret that despite the phenomenal rise in computing over the last 50 years, women are still not engaging with computer science at the same rate as men.

Girls are less likely to enroll in introductory computer science courses in school and the number of females studying computer science is near an all-time low. Therefore, the vast majority of computer science jobs will be pursued and filled by men.

According to Google's Diversity Gaps in Computer Science report of 2016:,

  Twice as many male students (34%) as female students (16%)
  saying they are “very interested” in learning CS in the future,
  and nearly twice as many female students (24%) as male
  students (13%) saying they are “not at all interested.”

Since I am very passionate about helping girls and women take an interest in computer science I would like to know the main ideas and theories about what keeps them back from learning it to eventually come up with a solution.

If you're just looking for the key points on how you can begin to solve the problem, you need only read the second section, but the first section provides valuable context on what the actual problem is and the root causes.

Why are so few girls interested in Computer Science?

There is an issue, not limited to CS, but throughout STEM fields (particularly Physics, Mathematics and Computer Science, according to recent examination statistics) with gender balance, where women are extremely underrepresented. In 2014, only about 10% of entrants for the Computing A-Level were female.

Miura (1987) suggests that women's self-efficacy regarding computing is lower, which leads to lower interest in the field and lower uptake at undergraduate level.

Fisher, Margolis & Miller (1997) also propose that women have less previous experience than men in the field—many have already started to self-teach or practice at home, whereas this is less true for women in the study. They also state that, from their interviews, women seemed to appreciate computing more as they went through their studies, whereas many of the men in the study showed a keen interest as soon as they were introduced to computing.

Fisher & Margolis (2002) discuss the "Geek Mythology"—the stereotypical male computer scientist—and its effect on women:

  While the stereotype of the computer science student as someone who is
  myopically focused on computing is rejected by many male and female students,
  women report more distress and are more affected by the perceived
  difference between themselves and their peers. One-third of the male students
  we’ve interviewed say they differ from the stereotype, that they have
  a broader range of interests than just computing. But twice as many women
  (more than two-thirds of those we interviewed) feel different from the
  stereotype. And 20 percent of the women we interviewed question whether
  they belong in computer science because they feel they do not share the
  same intensity in focus and interest that they see in their male peers.

How can this be changed?

Benbow & Vivyan point to a pedagogical solution which may benefit:

  Pedagogical interactions are an important factor in determining
  whether students feel included or excluded in a particular educational field, and our findings in
  this regard confirm results from previous studies. Most significantly, students across our sample
  reported that working with real-world problems, as well as active instructor encouragement in light of student
  questions and peer collaboration, made them
  feel more comfortable and more confident as computer science majors—often despite
  brogammer-oriented field norms.

There are many groups aiming to change the culture around computing, such as Django Girls, an organisiation running free, one-day courses for girls and women interested in web development with HTML, CSS and Python. Events like this would seem to satisfy the goals of a supporting group of instructors, and a real-world problem to solve, which favours participation from women.

As a teacher, even changing the classroom environment may help to favour women and girls. Cheryan, Davies, Plaut & Steele (2009) state:

  People can make decisions to join a group based solely on exposure to that group’s physical environment.
  Four studies demonstrate that the gender difference in interest in computer science is influenced by
  exposure to environments associated with computer scientists. In Study 1, simply changing the objects
  in a computer science classroom from those considered stereotypical of computer science (e.g., Star Trek
  poster, video games) to objects not considered stereotypical of computer science (e.g., nature poster,
  phone books) was sufficient to boost female undergraduates’ interest in computer science to the level of
  their male peers.

The solution to this problem might not be one big change; rather, lots of little changes might improve participation from girls and women in CS classes.

Trying to create real-world scenarios, in a balanced classroom environment may bring some more success, but it's often hard to know if the solutions you try actually have any effect. Ensuring the culture of the class doesn't become too male-oriented might also help to avoid bias against women in the demographics.

I'd be very interested to hear anyone's experiences with applying methods like this, and whether they did seem to make a perceptible difference.


CS educators collaboration communities? What are collaboration sites for CS teachers?
The CS Educators StackExchange is nice'n'friendly, but here are some topics I'd like to be discussed, which are outside of StackExchange policy:

case studies: show to others direct experience when teaching a class
honest skill transfer efficiency for a specific methodology, the real percentage of students who "got it" and became programmers or got computational thinking
practice set tasks, which were used alongside main course
collection of programming problems, which student found "interesting" and which turned students into love/understanding with programming
collection of bad practice problems, which made more frustration than learning benefit

So far I haven't found any centralized resources except this StackExchange, but maybe there are others? I struggle now because I have to create practice task set for my course and really can't use the knowledge of precious generation of teachers, as information is highly decentralized.

Strangely, just after posting a question I found a list of additional link collections:

https://github.com/zamansky/awesome-cs-education
https://github.com/quobit/awesome-python-in-education
https://cseducators.stackexchange.com/a/3947/9632

And one chat:

https://chat.stackexchange.com/rooms/59174

I still think there should be more, but this is a start.


Abstract data type that has "include" "remove" and "is in" and only those In a data structures course, we see trees, balanced trees, hash tables. These have an important thing in common: we can use them to keep a collection of elements (with operations add and remove) and test for an element in the data structure.

I want to use them to define a "overarching" abstract data type, with each of them as an implementation. Is there a name for this ADT?

The set ADT unfortunately supports more operations (see https://en.wikipedia.org/wiki/Set_(abstract_data_type)#Operations)

Carrano, Data Abstraction & Problem Solving with C++: Walls and Mirrors begins by introducing a simple ADT kind of like you're talking about, called a "Bag". But it is not used as a base class for later examples (e.g., trees, et. al.). From Sec. 1.5:


Cormen's "Algorithms" pre-requisites What to recommend as a pre-requisite reading before Cormen's "Algorithms" to make this book easier to get through for 10-12th graders? Any courseware available for kids, books, courses, etc.?

Basically some experience with Discrete Mathematics and Probability , elementary Calculus is also recommend. And students are expected to be familiar with mathematical proofs, proofs by induction and good knowledge of a programming language.
An Excerpt From CLRS

What are the prerequisites for reading this book?

You should have some programming experience. In particular, you should understand recursive procedures and simple data structures such as arrays and linked lists.

You should have some facility with mathematical proofs, and especially proofs by mathematical induction. A few portions of the book rely on some knowledge of elementary calculus.

From a OpenCourseWare course thought by Prof. Charles Leiserson (The L in CLRS) based on CLRS in Fall of 2008

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.

Prerequisites: A strong understanding of programming and a solid background in discrete mathematics, including probability, are necessary prerequisites to this course.

These are the prerequisite courses recommended for Introduction to Algorithms

6.001 Structure and Interpretation of Computer Programs

This course introduces students to the principles of computation. Upon completion of 6.001, students should be able to explain and apply the basic methods from programming languages to analyze computational systems, and to generate computational solutions to abstract problems.

6.042J / 18.062J Mathematics for Computer Science

This course covers elementary discrete mathematics for computer science and engineering. It emphasizes mathematical definitions and proofs as well as applicable methods. Topics include formal logic notation, proof methods; induction, well-ordering; sets, relations; elementary graph theory; integer congruences; asymptotic notation and growth of functions; permutations and combinations, counting principles; discrete probability. Further selected topics may also be covered, such as recursive definition and structural induction; state machines and invariants; recurrences; generating functions.

Professor Cormen's answer on this subject

We assume that the reader has some programming experience, including recursion, and knows how to read and write rigorous mathematical proofs. The discrete mathematics facts needed to analyze the algorithms in the book appear in the appendices.

More of Professor Cormen's answers

First, it’s possible that you do not have the mathematical sophistication to follow all the mathematics in the book. You should have had a discrete mathematics course or, at the very least, know how to read and write proofs. The mathematical foundations appear in the four appendix chapters.


How necessary is UML for a course in object programming patterns? I'm gathering my wits to create a course that will focus a great deal on OO programming patterns (things like singleton, flyweight, command, etc, etc.)  I do not have a lot of background in this topic yet.  I am currently learning the material as I develop the course for next September.
It seems like having a way to graph out the patterns is necessary to such an endeavor, but UML also seems a bit nuts -- there are entire textbooks on the specifications.  Now, I understand that most of the UML diagram types would not be useful for a course in OO design patterns, but a few of them would be quite helpful.
So my question, then, is how deeply into UML should I go?  Should I cover class and object diagrams?  Sequence diagrams?  Should I cover them in depth, or only in a shallow way?  Or is there a completely different method that I should be looking for in order to notate design patterns for my students?

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.


The Starting Gun vs Freedom of Choice According to research, if people are to develop abstract reasoning capabilities (Formal Operations and Post-Formal) they need the proper exposure at age 7 to 12 - generally speaking. Adults that were not exposed properly at the right time do not progress past Concrete Operations well, or at all. Thus, it is difficult or impossible for them to become programmers later on, or to go in to other fields requiring abstract reasoning capability.

If we accept that this is true, then we must provide the correct training at age 7 to 12 and beyond, if we want to have people who are capable of performing in these sorts of ways, because later on is too late for them to acquire those capabilities. We can't wait for them to reach the age of majority and then say, "I want to become a programmer", because if they didn't have the right sort of background preparation, they cannot. We have deprived them of the ability to make that choice for themselves.

But, if we push the students in to this sort of schooling before they can decide for themselves, then they also are not acting with free will in that case either.

The first case prevents them from choosing something, the second allows them to choose it, but only because we made other choices for them. Studying one thing tends to mean not studying other things, as there are only 24 hours in a day. Successful Gymnasts and Musicians usually start as soon as they can walk, or reach the instrument. Successful programmers will need some exposure to thought processes that they need, early on.

How can we balance the objectives of allowing people choice, enabling them to choose by preparing them properly, providing the economy with prepared workers and supporting values like freedom of choice? It seems to me that some decisions are forced, and the timing of education is one of them. We get to choose, but we don't get to choose the choices we are presented with. So we have to make wise choices on behalf of (lots of) others, often without being able to obtain their consent, perhaps because they are too young to give it.

I think that the assumption of the question is overly deterministic. I am also pretty sure that I'm a living counter-example, though my case won't prove much. I was a terrible student into about 10th grade (say age 15), especially in math. My teachers once wanted to hold me back because I hadn't learned my multiplication tables. A plane-geometry class was my first positive educational experience of any kind. A bit later, a writing course appealed to me. Up until that time, I would rather have been anywhere but in school.

I was also told once, in high school, that, based on a standardized test, I probably wouldn't be successful in College and so should set my sights lower.

I later earned a PhD in Mathematics.

But there were no jobs for mathematicians at that time so I taught myself programming, with plenty of halts and stumbles. Then some deeper Computer Science. Still later I was lucky to have been mentored by some of the CS superstars in education.

But my early history would predict none of that, nor were my teachers particularly enlightened when I was young.

I worry about the question from another standpoint also. I don't think many individual teachers have much power over the overall curriculum. Groups and associations can make a difference, however, but this site doesn't really help with that sort of question.

However, if you are a teacher, you must not have a defeatist or deterministic attitude about your students: they can't learn so why bother. Every student in front of you, given some desire, can learn. You  have to be there to help them. You may even need to teach them how to learn in general, since their background may be like mine was. I eventually got desire, and the rest followed. Your job as a teacher is to educate them no matter what their background, be it advantaged or disadvantaged. The prime directive.


Demographics in Programming Teams in Early CS Courses I frequently teach CS1 and CS1-and-a-half in a very diverse, working-class,  commuter public sector college. I have my students to work in small groups (2 or 3) on their larger homework programming projects. The students rarely know each other from outside class, and I take it upon myself to assign them to the groups. With the best of intentions and considerable misgivings I use demographics and to-date academic performance to construct the teams: same gender, different ethnic background, similar academic performance. This seems to "work" but maybe that sense is merely expectation-fullfillment.

Do others use these criteria, or opposite ones? I'm curious to learn of others' experiences and possibly perspectives I haven't considered.

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.


Dealing with students who are underly-motivated Occasionally I have students who are 'under-motivated': they put way too little effort in to trying to memorize any of the textbook, any idea, each diagram I draw. I used to think that perhaps some people are "not suited" for some kinds of learning, but I threw that idea out: it is insubstantiable, and it is not my job to decide who is in the class anyway!

There is a raft of reasons why (adult) students could be having difficulties. They might have issues with medical conditions, medications, anxiety, depression, unstable home life, economic concerns... But these are not my purview either.

Assuming that the students can do the work if they work rightly, and that I can teach them if I teach rightly, what are some ways to deal with students who seem lost, have insufficient background knowledge, are unused to thinking in programming terms, who have issues with their energy, or are distracted... What are some effective ways to improve teaching in these situations (aside from the obvious of dealing with the cause, which is not in my scope).

You've mentioned before that your students are adults who are attempting to make a career change to a programming role. With that in mind, I think the best thing you can do is show them how what you're teaching helps them achieve that goal.

Think about it from their perspective: I'm an (older?) adult, who has had a "real job" for the last X years. Now I'm trying to change careers. I want to know how to get a new job, and how to perform the tasks of that new job. So it's hard for me to sit in a classroom and memorize stuff from a textbook and from lecture slides.

You and I know that memorizing that stuff will help them in their new careers, but that's not always obvious to students- especially novice programmers.

So my suggestion is to always make sure that your lessons directly tie into their goals. Find out what kinds of applications they plan on working on. Make the first assignment a very basic version of that. With each lesson, build on that assignment so that every step gets them closer to a "real life" end product.

Instead of saying "okay now you have to memorize that" and pointing to some lecture slides or a textbook chapter, ask "how can we improve our product?" and then show them concrete things they can do to make those improvements. The lectures and the textbook become references that help get them to their end goal, which I think is easier for professionals to digest.

For a concrete example, let's say your goal application is a point of sale system. Maybe your first application is a command-line program that mimics a basic transaction. Then the next assignment introduces variables by having different items with different costs. Then maybe the next assignment introduces if statements that apply coupons. Then you could have a lesson on creating a basic GUI, or using for loops to repeat actions, etc.

That's just a dumb example off the top of my head, but you get the idea: use your students' goals as a motivator, and tie your lessons directly into those goals. At the end of your course, students should have specific concrete usable information and a newfound ability to accomplish their goals.


Teaching syntactic sugar When I show my code to students I tutor, they ask about "all those things in my code", which refers (quite vaguely) to things such as shortened ifs, post\preincrement etc.

They are confused by these things, but once I explain those things, I see that the students constantly use them (not in excess).

This got me wondering what are some of the benefits of teaching syntactic sugar during regular teaching (as part of the lesson plans in the curriculum). What might the students gain from learning syntactic sugar during lessons?

Examples of things I had in mind:

int x;
if(condition){
    x=5;
} else{
    x=2;
}

is identical to:

int x = condition ? 5 : 2;

Also:

int epoch = 0;

do{
    someEpochDepenentOperation(epoch,x);
} while(++epoch < 100);

would be:

int epoch = 0;

do{
    someEpochDepenentOperation(epoch,x);
    epoch++;
} while(epoch < 100);

The ?: operator is not syntactic sugar (OK in most languages it is, and no guarantees/checks are made). It is a different construct.

if predicate then action1 else action2 is procedural

predicate ? value1 : value1 or value1 if predicate else value2 is functional

The first does something, the second evaluates to something. The value is that the functional form tells you that you are doing something functional, that there are no side effects. Thus making the code easier to read (once you have the vocabulary).

In this example

int x;
if(condition){
    x=5;
} else{
    x=2;
}

the reader must ask, can x remain uninitialized? What are all the values that x can take? Does anything else change or happen?

Where as for this example

int x = condition ? 5 : 2;

We see that we initialize x, to 5 or 2. That is it. We could also write

const int x = condition ? 5 : 2;

This tells us that x is x: it never changes.


Benefits of explaining low-level architecture in a programming class When teaching an intermediate or advanced highschool programming class that also touches on general CS concepts (algorithms, etc), what are the benefits of explaining low-level computer architecture? How much added understanding of programming/computer science does a student get when learning about logic gates, for example?

My question isn't a duplicate of Is it more effective to teach low level languages before high level ones or vice versa? as it's asking about logic gates, registers, instruction set architectures, etc, and the benefits of teaching those in a programming class, not about low level programming languages in particular.

Students should understand the importance of the memory hierarchy, including how caches use temporal and spatial locality to tremendously speed up memory accesses. Otherwise, a student would not know there is any difference between:

for (int i = 0; i < 1000000; i++) {
    for (int j = 0; j < 1000000; j++) {
        arr[i] += j;
    }
}

and the logically equivalent reordered code:

for (int j = 0; j < 1000000; j++) {
    for (int i = 0; i < 1000000; i++) {
        arr[i] += j;
    }
}

The difference is that, in the first piece of code, each array element is retrieved from memory once and placed in either a register or the cache, from which it is operated on a million times. Ignoring spatial locality (which would apply equally to both versions), the total number of reads from memory would be 1,000,000, and the total number of writes would be 1,000,000.

With the second version of code, each array element is fetched from memory once for each value of j. The total number of reads from memory would be 1,000,000 x 1,000,000 (10^12); the total number of writes would be the same.

Per Latency Numbers Every Programmer Should Know, a main memory access takes about 100 ns; an L1-cache reference takes .5 ns. Accessing a register adds no time to instruction execution.

Ignoring the times for the writes (which may not be in the critical path) and spatial locality (which applies the same to both versions) and assuming that a[i] is stored in a register, the data memory access time for the first is 10^6 * 100 ns = .1 s. The data memory access time for the second is 10^12 * 100 ns = 10^5 s.


AP Computer Science A vs. OCP Out of my own interest, I have been self-learning Java over the past few months.
I decided I should take this to a greater advantage, so I have been considering taking the OCP (Oracle Certified Professional) . I presume that the OCP is more useful than AP Computer Science A, which is my other option.
However, my concern is whether admission officers know anything about the OCP, compared to AP Computer Science A, which university admission officers are familiar with.
Therefore, would it be a bad decision (and waste of money) to take the OCP over AP Computer Science A? Should I take both?

First, I applaud your ambition!
The first OCP exam covers roughly what AP did until this most recent year, when the college board stripped out Interfaces. I would still suggest that they are mostly equivalent, but there are a few practical advantages to the AP Test:

It is substantially cheaper.
Colleges recognize it for admissions purpose. (As you point out, an admissions officer is unlikely to have heard of the OCP, and would question how it compares to AP, and why you didn't just take AP)
Many colleges, at least in North America, automatically award credit or alter your course placement based on your AP scores. No equivalent system exists for OCP.
Because OCP is a professional exam, and you are unlikely to join the profession for at least 5 years (assuming a 4 year college), the exam may be considered dated by the time you get into industry, and it seems obvious that a college major will count for more than the lowest-level Oracle exam in any case. TBH, I've never heard of anyone asking for job applicants to provide Oracle scores, though I imagine that it probably happens somewhere or they wouldn't still offer the exam.

One last thought for you: you do not have to take the course to register for the test, so you can self-study. If you wish to go this route, but your school won't allow you to register yourself for the exam without being enrolled in the course, you should still be able to sign up at a different location.
Good luck!