Syllabus

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

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

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

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

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

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

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

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

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