# Computer Science for Mere Mortals: An introductory course in CS theory (with some programming)

June 4, 2012Hello everyone,

So, something I've always wanted to do is put together a theory-first approach to
getting into computer science and programming. While many people think that there's
no harm in getting into a programming language right away, I feel that there is a
lot to be gained by understanding the theory behind programming and computing before
you ever touch a programming language. To that end, and with my significant-other as my
guinea-pig student *and* educational-advisor, I will be running an impromptu course
here on my blog and in person with her. The planned course outline is as follows:

- Models of Computation
- \(\lambda\)-calculus
- Intro (Lesson 1.1)
- Arithmetic (Lesson 1.2)
- Boolean Logic (Lesson 1.3)
- Advanced Logic and Arithmetic (Lesson 1.4)
- Flow-control and recursion (Lesson 1.5)

- Grammars and Languages
- Natural Languages vs. Formal Languages
- Context Free Grammars
- L-Systems

- Formal Machines and Automata Theory
- Finite State Machines
- Stack Machines
- Turing Machines
- Register Machines
- Memory Machines (RAM machines)

- \(\lambda\)-calculus
- Number Systems
- Decimal (review)
- Place-value system
- Base Conversion

- Binary
- Bit vs. Byte vs. Word
- Basic arithmetic
- Overflow

- 2's compliment encoding
- More arithmetic

- Shannon's Information Theory
- ASCII

- Hexadecimal
- Utility

- Octal
- Utility

- Decimal (review)
- Selected Topics in Graph Theory
- What is a graph?
- Complete graphs vs. Sparse graphs
- Directional graphs vs. non-directional graphs
- Paths and cycles
- Edge weights
- The DAG (directed acyclic graph)

- Intro to Programming
- Intro to Io
- Some basic programs

- The Object Oriented Paradigm
- The standard object model
- Data and Behavior
- Inheritance
- Polymorphism

- The prototype object model (as used by Io)
- The interface/trait model

- The standard object model
- The Functional Paradigm
- The \(\lambda\)-calculus strikes again!
- Functional-style programming in Io

- Intro to Io
- Intro to Data Structures
- Lists
- Linked-list
- Stack
- Queue
- Deque

- Maps/Hashes
- Key-Value pairs
- Representation as lists of lists
- Hashing

- Trees
- Binary tree
- Binary search tree
- Intro to algorithmic complexity (big-O, big-\(\Omega\), big-\(\Theta\))

- n-ary tree
- Trie (binary)

- Binary tree

- Lists

That's a lot of stuff to cover, so as you can guess, there will be a lot of material generated through the course of this. I'm hoping it turns out nicely.

So, how will this run? I'll be posting lessons (textual lectures, I guess), and at the end of each lesson will be some homework along with some recommended reading. The answers to the homeworks will be linked to in PDF format along with the lesson. To really get the most out of this course, you should really try to do all of the homework questions. But, it's your education, so it's really your call. I won't make any of them too difficult, though.

As for a course prerequisite, I would suggest some basic mastery of college-level algebra, as well as some foundational set-theory, though you can pick that up later.

Here's to hoping I don't give up on this halfway through!