# a→ab

## computation, game design, and experimentation

front page | about | archives | code dump | c.s. for mere mortals | tags | rss feed

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

June 4, 2012

Hello 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:

1. Models of Computation
1. $$\lambda$$-calculus
1. Intro (Lesson 1.1)
2. Arithmetic (Lesson 1.2)
3. Boolean Logic (Lesson 1.3)
4. Advanced Logic and Arithmetic (Lesson 1.4)
5. Flow-control and recursion (Lesson 1.5)
2. Grammars and Languages
1. Natural Languages vs. Formal Languages
2. Context Free Grammars
3. L-Systems
3. Formal Machines and Automata Theory
1. Finite State Machines
2. Stack Machines
3. Turing Machines
4. Register Machines
5. Memory Machines (RAM machines)
2. Number Systems
1. Decimal (review)
1. Place-value system
2. Base Conversion
2. Binary
1. Bit vs. Byte vs. Word
2. Basic arithmetic
1. Overflow
3. 2's compliment encoding
1. More arithmetic
4. Shannon's Information Theory
1. ASCII
1. Utility
4. Octal
1. Utility
3. Selected Topics in Graph Theory
1. What is a graph?
2. Complete graphs vs. Sparse graphs
3. Directional graphs vs. non-directional graphs
4. Paths and cycles
5. Edge weights
6. The DAG (directed acyclic graph)
4. Intro to Programming
1. Intro to Io
1. Some basic programs
1. The standard object model
1. Data and Behavior
2. Inheritance
3. Polymorphism
2. The prototype object model (as used by Io)
3. The interface/trait model
1. The $$\lambda$$-calculus strikes again!
2. Functional-style programming in Io
5. Intro to Data Structures
1. Lists
2. Stack
3. Queue
4. Deque
2. Maps/Hashes
1. Key-Value pairs
2. Representation as lists of lists
3. Hashing
3. Trees
1. Binary tree
1. Binary search tree
2. Intro to algorithmic complexity (big-O, big-$$\Omega$$, big-$$\Theta$$)
2. n-ary tree
3. Trie (binary)

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!