Notes: Automata, Grammars, and Computability

Week 1 (01/09, 01/11) Automata are machines. They have a grammar that they can follow. Deterministic finite automata are a subset of FSM. It can take in input from the set $\Epsilon$. For each input character from the set, there is an arrow drawn for each state. $\epison$ is used to represent an empty String. Strings are sequences, not sets. Order matters.

Notes: C and Software Tools

This class focuses on the C99 standard. ssh [unity_id]@remote.eos.ncsu.edu # To access Common Platform, used for grading gcc -Wall -std=c99 # To compile Week 1 (01/09, 01/11) C is a procedural language, not object-oriented. Both C and Java are imperative. They contain series of instructions on HOW to compute something, not just what to compute. The first C standard was C89 (1989/1990-ish). Features of C can be hardware-dependent. For example, the capacity of int can be limited depending on the machine compiling/running the code.

Notes: Data Structures and Algorithms

Week 1 (01/09, 01/11) Week 2 (01/17, 01/19) Sorting Algorithms Comparison Sorting Algorithms Best Worst Description bogo already sorted: $T(n) = n - 1 = O(n)$ $T(n)$ is unbounded Shuffle until sorted, O(n) bubble already sorted: $T(n) = n - 1 = O(n)$ reverse sorted: $T(n) = n(n-1) = O(n^2)$ Adjacent values are swapped until the end is reached, O(n^2) insertion already sorted: $T(n) = n - 1 = O(n)$ reverse sorted: $T(n) = \sum_{1}^{n-1} i = \frac{n^2-n}{2} = O(n^2)$ Smaller values are shifted forwards so that a larger value can move up in the data structure, O(n^2) selection $O(n^2)$ $O(n^2)$ Smallest value is selected and moved to the front, O(n^2) Other Sorting Algorithms Best Worst Description counting O(n + k) Creates a dotplot, which can be used to calculate index of each element radix counting sort, but focuses on place value rather than creating a “bucket” for each value in the range of elements