# CSE 110 : Introduction to Computer Science

Class Website

## Sorting

- Radix Sort : An O(n) sort that works without comparison.
- Radix Sort : Distribute into bins based on the 1's place, then 10's, 100's, etc.

## Regular Expression

- Regular Expression: A kind of query.
- De jure Standard : IEEE POSIX (SRE, BRE or ERE)
- De facto Standard : PCRE

## Regular Language

- Regular Language: A language constructed as the set of all responces of a
particular Regular Expression.

## Regular Grammar

- Regular Grammar: A grammar that describes a Regular Language.

### Backus-Naur Form (BNF)

- BNF: A notation for describing a grammar.

- C ← B means B can replace C/li>
- A 3 line BNF:

### Parse Trees for Regular Grammars

- In a Regular Grammar Parse Tree, a node's children are those that can replace it.
- A ← B means B can replace A (think B points to its parent A)