| 0 |
Title Page |
|
14 |
Interrupts |
| 1 |
Table of Contents |
|
14.1 |
How does the outside world get my attention? |
| 2 |
The Course, aka CMPUT 296/297, CMPUT 114/115 |
|
14.2 |
The process for servicing an interrupt |
| 2.1 |
Introduction to the Scaled Up Pilot |
|
14.3 |
Pitfalls |
| 2.2 |
IMPORTANT NOTE TO THE STUDENT |
|
14.4 |
Examples of Timer Interrupts |
| 2.3 |
The Story So Far - 2012-09-24 |
|
14.5 |
External Interrupts and Switch Debouncing |
| 3 |
Bits, Bytes, and Modular Artithmetic |
|
14.6 |
Subtle Issues |
| 3.1 |
The Natural Numbers Are All You Have |
|
14.7 |
Code examples |
| 3.2 |
The Division Algorithm |
|
15 |
Queues |
| 3.3 |
Greatest Common Divisor |
|
15.1 |
What is a Queue? |
| 3.4 |
Modular Arithmetic |
|
15.2 |
Implementing a queue in C using arrays |
| 3.5 |
Binary Representations |
|
15.3 |
Implementing a queue in C using linked lists |
| 3.6 |
Hexadecimal Notation |
|
15.4 |
A Queue Implementation That is More Modular |
| 3.7 |
General Base-B Positional Representations |
|
16 |
Hash Tables |
| 3.8 |
Arduino Bit Code |
|
16.1 |
What is a hash table? |
| 4 |
Signed, Unsigned, Byte, Normal, and Long, LED Bit Arithmetic |
|
16.2 |
Implementing a Hash Table with Collision Lists |
| 4.1 |
Part 1: Counting Bits |
|
17 |
Python |
| 4.2 |
Part 2: LED Bit Display |
|
17.1 |
The Python Language and Way |
| 4.3 |
Tasks |
|
17.2 |
What does assignment mean? |
| 5 |
Logical Operations on Bits |
|
17.3 |
Our First Python Examples |
| 5.1 |
Basic Logic Operations |
|
17.4 |
Object Oriented Notions |
| 5.2 |
DeMorgan's Laws |
|
17.5 |
A simple example object |
| 5.3 |
Logic and Bit Operations |
|
17.6 |
Converting the hash table into a dictionary |
| 5.4 |
Bit Shifting |
|
17.7 |
Lists and References |
| 5.5 |
Bit Manipulation |
|
17.8 |
Lists that contain themselves |
| 6 |
Strings and Arrays |
|
18 |
Graph Theory |
| 6.1 |
Internal Representation |
|
18.1 |
Basic Notion of a Graph |
| 6.2 |
String Example |
|
18.2 |
Graph Notions |
| 6.3 |
Arrays |
|
18.3 |
Exercise: An Example of A Graph Algorithm |
| 7 |
Diffie-Hellman Key Exchange |
|
18.4 |
Spanning Trees |
| 7.1 |
Talking Arduinos |
|
18.5 |
Min-Cost Spanning Trees |
| 7.2 |
Diffie-Hellman Key Exchange |
|
18.6 |
Shortest Paths |
| 7.3 |
Implementing Diffie-Hellman on the Arduino |
|
18.7 |
Min-Cost Paths |
| 7.4 |
Thinking like a Computer Scientist: Modular Exponentiation |
|
18.8 |
The Digraph Class |
| 7.5 |
Starter Program |
|
18.9 |
Displaying Graphs and Digraphs with Graphviz |
| 7.6 |
Procedures |
|
19 |
Object-Oriented Class Design Principles |
| 7.7 |
Algorithm Design |
|
19.1 |
Separation of Concerns |
| 7.8 |
Algorithm Analysis |
|
19.2 |
Abstraction |
| 7.9 |
A Better Algorithm |
|
19.3 |
Acessors |
| 8 |
Reasoning About Programs |
|
19.4 |
Law of Demeter |
| 8.1 |
Properties, Assertions, and Invariants |
|
19.5 |
Styles of Reuse |
| 9 |
Using the Adafruit LCD display |
|
19.6 |
Inheritance as Reuse |
| 9.1 |
Recommended Wiring Order |
|
19.7 |
Liskov's Principle of Substitution |
| 9.2 |
Hello World: Graphics Test |
|
19.8 |
Is-a vs Has-a |
| 10 |
Memory |
|
19.9 |
Slicing |
| 10.1 |
Where is stuff stored? |
|
19.10 |
Polymorphism and Virtual Functions |
| 10.2 |
How does a program use memory? |
|
19.11 |
Containers |
| 10.3 |
General Notation and Properties of Pointers |
|
19.12 |
Behaviour Restriction |
| 10.4 |
Big Endian and Little Endian |
|
19.13 |
Foundation Classes |
| 10.5 |
The Stack and Heap |
|
19.14 |
Class Refactoring |
| 10.6 |
Block Variables |
|
20 |
Binary trees |
| 10.7 |
Procedure/Function Calls and the Stack |
|
20.1 |
Binary Trees |
| 10.8 |
Passing Arguments by Value to Procedures and Functions |
|
20.2 |
Binary Tree Implementations |
| 10.9 |
Utilities for Managing Memory |
|
20.3 |
Algorithms over Binary Trees |
| 10.10 |
Other examples for your viewing pleasure |
|
21 |
Dynamic Programming |
| 11 |
Data Structures |
|
21.1 |
Recursive decomposition of problems |
| 11.1 |
Arrays and Address Arithmetic |
|
21.2 |
Floyd-Warshall All-Pairs Min-Cost Paths |
| 11.2 |
Dynamically Allocated Arrays |
|
22 |
How to Read a Program |
| 11.3 |
Dynamically Allocating a Singleton |
|
23 |
Installation Instructions |
| 11.4 |
Making composite data structures |
|
23.1 |
Ubuntu Virtual Machine |
| 11.5 |
Reading and Writing to the SD card |
|
23.2 |
Ubuntu Linux |
| 12 |
Sorting and Big O notation |
|
23.3 |
OSX |
| 12.1 |
Selection Sort |
|
23.4 |
Windows XP and 7 |
| 12.2 |
Big O Notation |
|
24 |
The AVR Tool Chain |
| 12.3 |
Merge Sort |
|
24.1 |
Overview |
| 12.4 |
Quick Sort |
|
24.2 |
Software Abstraction Layers |
| 12.5 |
Stable Sorting |
|
24.3 |
Makefiles for the Arduino Environment |
| 12.6 |
Animated Sorting Algorithms |
|
24.4 |
Makefiles in General |
| 12.7 |
The Sorting Library |
|
24.5 |
Makefiles For Collections Of Files |
| 13 |
Searching |
|
25 |
Git |
| 13.1 |
Bruteforce Search |
|
25.1 |
Version Control |
| 13.2 |
Binary Search |
|
25.2 |
The Various Git Repository Models |
| 13.3 |
A Typical Binary Search Pattern |
|
25.3 |
Using Git on gpu.srv.ualberta.ca with AFS |
| 13.4 |
Performance of Binary Search |
|
25.4 |
Using Git |
| 13.5 |
Other Applications of Binary Search |
|
25.5 |
Installing Git |
| 13.6 |
The Searching Library |
|
26 |
Revision Log |
| 13.7 |
Combining Sorting and Searching |
|
27 |
End of Document |
