Computer Mathematics for Graduate Engineers
Lectures
Tuesday, 10:30-11:50, S311
Lecture notes (PDF)
Lecture videos (MP4)
Automatically generated English subtitles are available for some videos. Watch or download them using the “subs” link next to the original video.
Slides (PDF)
Exercises (PDF)
Programs
Simple CPU simulator (week 10)
First word printer (week 11)
Word counter (week 11)
- wc.py transition table
State machine multiplier (week 12)
Recursive-descent parsing (week 15)
- parse-eg1.py recognition
- parse-eg2.py with semantic value
- parse-eg3.py expressions and AST
Parsing workshop (additional)
- w15.tar.gz workshop software
The slides used in the lectures are available on the left. These should be reviewed before coming to the indicated class.
Class summaries are posted below with PDF files for assigned reading, details of homework assignments, and instructions for any oral presentation that must be made.
Week 1 - Computer organisation
We begin with a brief introduction to computer organisation, how data is stored in memory, the components of a typical CPU, and how instructions are executed.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing positional number notation and conversion between number bases.
The mathematics of data
Week 2 - Positional number systems
Positional representation of integer and floating point numbers. Decimal, binary, octal, and hexadecimal representations. Radix conversions.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing binary arithmetic.
Week 3 - Arithmetic operations
Basic arithmetic operations in positional number systems. Binary arithmetic.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing negative number representations in binary.
Week 4 - Negative numbers
Representations of negative numbers. Radix complement, diminished radix complement representations. Binary arithmetic using two’s complement representations.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing Unicode and compression algorithms.
The mathematics of information
Week 5 - Source coding
Binary coding systems. ASCII, Unicode and the UTF encodings. Gray code. The information content of a message. Data compression and Huffman’s algorithm.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing error detection and correction.
Week 6 - Channel coding
Error detection: parity, cyclic redundancy check. Error correction: block parity, Hamming codes. Find and read a couple of online articles describing digital logic gates.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing Boolean logic.
The mathematics of logic
Week 7 - Boolean logic
Propositions, logical operators, truth tables. Simplification and De Morgan’s laws.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing how to draw digital circuits.
Try to design a logical system that can add two bits to generate a single-bit sum and single-bit carry.
Try to extend it to add three input bits to produce single-bit sum and carry.
Week 8 - Combinational logic circuits
Wires and busses, gates, Half and full adders.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing arithmetic and logic units.
Try to figure out how to turn a multi-bit 2's complement adder into a subtractor by adding only inverter gates.
Week 9 - Parallel logic circuits
Multi-bit adders and subtractors. Bit-wise logical operations. Multiplexers. The design of a simple ALU.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing flip-flops and memory cells.
Week 10 - Sequential logic
Latches, registers, and memory cells.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing state machines and their applications.
The mathematics of control
Week 11 - Finite state automata
FSA representation. Applications: pattern matching, pattern generation.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing regular expressions and their equivalence to finite-state machines.
Week 12 - Sequencing and control
Moore and Mealy machines. Applications: implementation of the Control Unit, complex ALU operations. Mathematics notations: regular expressions.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing non-deterministic and deterministic finite-state machines, and how to convert the former into the latter.
Week 13 - Determinism and non-determinism
Deterministic and non-deterministic finite automata. The subset algorithm for converting NDFA into DFA.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing regular grammars and their relationship with regular expressions.
The mathematics of language
Week 14 - Regular grammars
FSA as language generators. Regular grammars. Equivalence of FSA, regular expression, and regular grammar. Inability of regular languages to match recursive constructs.
Homework
Review the slides and notes for this week's class.
Find and read a couple of online articles describing Chomsky's hierarchy of grammars and the typical applications of grammars at each level in the hierarchy.
Week 15 - Context-free grammars
Grammar types and the Chomsky hierarchy. Context-free grammars. Parsing, ambiguity, and construction of abstract syntax trees. Constructing parsers from grammars.
Homework
Review the slides and notes for this week's class.
Write a parser and/or interpreter for a simple configuration or scripting language.