TOPICS FOR TENTH GRADE CS

Managing complexity

We introduce the formal study of algorithms by making concrete the kinds of problems they can solve. These should be paired with application domains where students can find authentic uses for them. (For example, I’m avoiding the classic algorithmic problem of sorting because I can’t think of a lot of examples where you would actually implement your own sorting alogrithm.) These should also be sequenced so that shared concepts can built on each other.

Algorithms which offer a clever way to solve a problem, where a naive approach is available but scales poorly

Algorithms

Recursion – factoring numbers / finding primes

Memoization / Linear programming – computing high values of the fibonacci series – computing rows of Pascal’s triangle – finding optimal paths through sequential choices

Search – breadth-first – depth-first

Algorithms which solve some problem where the solution space is initially hard to see (eg students might not have any idea how to formalize or solve the problem).

Pathfinding – A* – Dijkstra’s algorithm

Encoding – Huffman encoding – image compression – tree lexicon (eg for word-guessing games)

Game-playing – minimax (winning tic-tac-to, nim)

Logic – Some kind of proposition prover?