A second course in computer science. Data structures and algorithms are studied through major programming projects in the C++ programming language. Topics include linked lists, trees, graphs, dynamic storage allocation, and recursion.

In CS 40, you will learn about both high-level programming design principles and the low-level structure of computing machines. Design strategies will focus on modularity, abstraction, and separation of interface from implementation. The following topics on machine structure are covered: memory, caches, registers, machine arithmetic, and bitwise operations. We will also investigate the structure of assembly code, relocatable object code, binary machine code, and the translations between them. You will gain a deep understanding of all of these concepts via large-scale, realistic programming projects.

Principles and application of computer programming languages. Emphasizes ideas and techniques most relevant to practitioners, but includes foundations crucial for intellectual rigor: abstract syntax, lambda calculus, type systems, dynamic semantics. Case studies, reinforced by programming exercises. Grounding sufficient to read professional literature.

Introduction to the study of algorithms. Strategies such as divide-and-conquer, greedy methods, and dynamic programming. Graph algorithms, sorting, searching, integer arithmetic, hashing, and NP-complete problems.

Models of computation: Turing machines, pushdown automata, and finite automata. Grammars and formal languages including context-free languages and regular sets. Important problems including the halting problem and language equivalence theorems.

Introduction to the theory of vector spaces and linear transformations over the real or complex numbers, including linear independence, dimension, matrix multiplication, similarity and change of basis, inner products, eigenvalues and eigenvectors, and some applications.