INFORMATION ABOUT LECTURES 1–10-INFORMATION ABOUT LECTURES 1–10
Information about Lectures 1–10
SORTING AND SEARCHING-LECTURE 11: SORTING AND SEARCHING
Getting Started
Supplements for Lecture 11
A typical client
()
Binary search
()
Insertion sort
()
Mergesort
()
Longest repeated substring
()
Optional Enrichment on Sorting and Searching
STACKS AND QUEUES-LECTURE 12: STACKS AND QUEUES
Supplements for Lecture 12
APIs
()
Clients
()
Strawman implementations
()
Linked lists
()
Implementations
()
Optional Enrichment on Stacks and Queues
SYMBOL TABLES-LECTURE 13: SYMBOL TABLES
Supplements for Lecture 13
APIs and clients
()
A design challenge
()
Binary search trees
()
Implementation
()
Analysis
()
Optional Enrichment on Symbol Tables
INTRODUCTION TO THE THEORY OF COMPUTING-LECTURE 14. INTRODUCTION TO THE THEORY OF COMPUTING
Supplements for Lecture 14
Overview
()
Regular Expressions
()
DFAs
()
Applications
()
Limitations
()
Optional Enrichment on Theory of Computing
TURING MACHINES-LECTURE 15. TURING MACHINES
Supplements for Lecture 15
Context
()
A simple model of computation
()
Universality
()
Computability
()
Implications
()
Optional Enrichment on Turing Machines
INTRACTABILITY-LECTURE 16. INTRACTABILITY
Supplements for Lecture 16
Reasonable questions
()
P and NP
()
Poly-time reductions
()
NP-completeness
()
Living with intractability
()
Optional Enrichment on Intractability
A COMPUTING MACHINE-LECTURE 17. A COMPUTING MACHINE
Supplements for Lecture 17
Overview
()
Data Types
()
Instructions
()
Operating the machine
()
Machine language programming
()
Optional Enrichment on A Computing Machine
VON NEUMANN MACHINES-LECTURE 18. VON NEUMANN MACHINES
Supplements for Lecture 18
Perspective
()
A note of caution
()
Practical implications
()
Simulation
()
Optional Enrichment on von Neumann Machines
COMBINATIONAL CIRCUITS-LECTURE 19. COMBINATIONAL CIRCUITS
Supplements for Lecture 19
Building blocks
()
Boolean algebra
()
Digital circuits
()
Adder circuit
()
Arithmetic/logic unit
()
Optional Enrichment on Combinational Circuits
CENTRAL PROCESSING UNIT-LECTURE 20. CENTRAL PROCESSING UNIT
Supplements for Lecture 20
Overview
()
Bits, registers, and memory
()
Program counter
()
Components and connections
()
Optional Enrichment on the CPU