Expanding list of things that should be part of the Computer Science curriculum.

Undergraduate CS

Introduction to imperative/unstructured programming (assembly)

At least 3 different programming paradigms, from e.g.:

Functional. Clojure, Haskell or Scheme are good choices. Languages where functional programming is "optional" (such as C++, Common Lisp or Python) might not be that suitable in a pedagogical setting.

Imperative and structured. C or Java might be good for this.

Declarative. Prolog, SQL or XSLT, or perhaps some vendor/domain-specific XML based language.

Logic programming. Prolog.

Object-Oriented. Common Lisp or Smalltalk. Should be introduced to students before exposure to C++, C# or Java. A nice exercise is implementing OO using a functional or imperative language.

At least 2 different development and runtime paradigms

One with a compile-and-run cycle. C, C#, Java.

One with a REPL. Common Lisp, Clojure or Python.

One running on a platform independent virtual machine featuring garbage collection (C#, Clojure, Go, Java, Scala).

One running on "the metal" and not featuring garbage collection (C).

Using a text-based build system (CMake, Gradle, Make, Maven).

Using a version control system (Git, SVN) together with 3 or more people on a project spanning two months or more.

Continuous integration

Testing

Algorithms and Data Structuring

Encapsulation and modularisation.

Message-passing.

Recursion.

Speed, size and representational trade-offs: Hash tables, linked lists.

Trees and tree traversal

Storage and retrieval strategies and their trade-offs (CAP-theorem, etc.):

Scalable "NoSQL".

Structured RDBMS using SQL.

Usability and user perspective.

Not only for those who intend to work directly with user interfaces, but formative and important for all CS students (who by definition are "technical" of nature).

A particularly good resource is "The Design of Everyday Things" by Donald Norman.