Syllabus

What is a computer?

This section will give students the tools to effectively describe a computer. In this section, models of computation such as the von Neumann model are discussed. Students end this section able to answer the question “what is a computer?”

Core keywords: von Neumann model, Harvard model, data and instructions, memory, bus

Related assignments: problem set 0

Theory of computation

This section introduces students to the theoretical model of computation proposed by foundational computer scientist and mathematician Alan Turing. Theoretical implications of Turing’s theories expose students to the mathematical background and practical limitations of computers. Students end this section able to answer the questions “how does a computer work?” and “what can a computer actually do?”

Core keywords: Turing machine, function, computability, decidability, the halting problem

Related assignments: problem set 0

Information storage

This section describes binary positional notation and shows how a wide variety of data are stored in binary. Students are introduced to basic electrical engineering concepts and are shown how computers do math on binary numbers. Boolean values are also introduced as a basic data type. Students end this section able to answer the questions “how are data stored in a computer?” and “how do computers do math?”

Core keywords: binary notation, binary string, data type, two’s complement, binary addition, binary multiplication, bit operations, arithmetic logic unit, Boolean logic

Related assignments: problem set 1

Computational methods

This section discusses how humans control and program computers to produce a result. The concept of an instruction is made concrete. Branching is introduced. Efficiency and correctness are introduced. Recursion is introduced as a way to solve problems, and related to the divide-and-conquer approach. Students end this section able to answer the questions “how do I tell a computer what to do?” and “what is a programming language?”

Core keywords: instruction, branching, if-then-else, recursion, divide-and-conquer, programming language, syntax

Related assignments: problem set 1

Programming input and output

This section is an introductory lesson to programming in the real-life language, Haskell. Students gain a practical knowledge of how to write functions in Haskell that do simple calculations. Students gain first-hand experience in writing, debugging, and running programs from an interactive interpreter session. Students are exposed to real-life examples of a program’s efficiency and correctness. Students end this section able to write several simple Haskell programs and use basic debugging strategies.

Core keywords: function call, call stack, prompt, list, infinite recursion, substring, logic error, syntax error

Related assignments: problem set 2

Problem solving with programming

This section extends students’ understanding of programming and equips students with more tools to solve problems with a computer. Polymorphic functions are introduced. Code style, good organization, and use of comments are introduced. Basic recursive data types are introduced, and their efficiencies are discussed. Students end this section with the confidence and ability to write their own, complete Haskell programs.

Core keywords: type, type class, recursive data structure, map, fold

Related assignments: problem set 2

Advanced programming structures

This section completes students’ understanding of Haskell by presenting monads and more advanced types like Maybe.

Core keywords: Maybe, fmap, monad

Related assignments: problem set 3

Algorithms and algorithm analysis

This section presents the concept of an algorithm and introduces mathematical and scientific methods for evaluating the efficiency of an algorithm. Asymptotic analysis is presented. Several well-known algorithms are presented for solving practical computer science problems. Insertion sort and merge sort are introduced. Students end this section with the ability to evaluate the performance of their programs and recall efficiency proofs for many classic problems.

Core keywords: algorithm, big-O notation, big-theta notation, asymptotic analysis, insertion sort, merge sort

Related assignments: problem set 4

Data structures

In this section, classic data structures are introduced and their usefulness in different contexts are discussed. Students apply their analysis skills from the previous section to categorize and reason about the time and space complexity of each data structure. In a final programming assignment, students implement and use several data structures to solve novel problems. Students end this section with a strong grasp of common data structures.

Core keywords: abstract data type, stack, queue, binary tree, balanced binary tree, hash table, graph

Related assignments: problem set 5