Results for Programming Abstractions

Abstraction and its relation to programming. Software engineering principles of data abstraction and modularity. Object-oriented programming, fundamental data structures (such as stacks, queues, sets) and data-directed design. Recursion and recursive data structures (linked lists, trees, graphs). Introduction to time and space complexity analysis. Uses the programming language C++ covering its basic facilities. Prerequisite: 106A or equivalent.

This enrichment add-on is a companion course to CS106B to explore additional topics and go into further depth. Specific topics to be announced per-quarter; past topics have included search engines, pattern recognition, data compression/encryption, error correction, digital signatures, and numerical recipes. Students must be co-enrolled in CS106B. Refer to cs106m.stanford.edu for more information.

Automated logical reasoning has enabled substantial progress in many fields, including hardware and software verification, theorem-proving, and artificial in- telligence. Different application scenarios may require different automated rea- soning techniques and sometimes their combination. In this course, we will study widely-used logical theories as well as algorithms for answering whether formu- las in those theories are satisfiable. We will consider state-of-the-art automated reasoning techniques for propositional logic, first-order logic, and various first- order theories, such as linear arithmetic over reals and integers, uninterpreted functions, bit-vectors, and arrays. We will also consider ways to reason about combinations of those theories. Topics include: logical foundations, SAT-solving, techniques for first-order theorem proving, decision procedures for different first- order theories, theory combination, the DPLL(T) framework, and applications of automated reasoning in program analysis and hardware verification. Prerequisites: CS154 Introduction to the Theory of Computation, or CS106b Programming Abstractions and CS103 Mathematical Foundations of Computing, or consent of instructor