~~NOTOC~~ {{:building1cropalpha.png?128|}} ==== Computer Mathematics for Graduate Engineers ==== == Lectures == Tuesday, 10:30-11:50, S311 == Lecture notes (PDF) == {{ :class:cm:computer-maths.pdf | Computer Mathematics }} == 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. | 4.\_ | {{ :class:cm:cm-04.mp4?linkonly | Negative and floating numbers }} | | | 5.\_ | {{ :class:cm:cm-05.mp4?linkonly | Source coding }} | | | 6.\_ | {{ :class:cm:cm-06-1.mp4?linkonly | Channel coding, parity }} | | | | {{ :class:cm:cm-06-2.mp4?linkonly | Error detection }} | | | | {{ :class:cm:cm-06-3.mp4?linkonly | Error correction }} | | | 7.\_ | {{ :class:cm:cm-07-1.mp4?linkonly | Boolean algebra }} | {{ :class:cm:cm-07-1_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-07-2.mp4?linkonly | Properties }} | {{ :class:cm:cm-07-2_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-07-3.mp4?linkonly | Canonical form }} | {{ :class:cm:cm-07-3_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-07-4.mp4?linkonly | Karnaugh maps }} | {{ :class:cm:cm-07-4.mp4?linkonly | subs }} | | | {{ :class:cm:cm-07-5.mp4?linkonly | Interesting operations }} | {{ :class:cm:cm-07-5_en.mp4?linkonly | subs }} | | 8.\_ | {{ :class:cm:cm-08-1.mp4?linkonly | Combinational logic }} | {{ :class:cm:cm-08-1_en.mp4?linkonly | subs }} | | 9.\_ | {{ :class:cm:cm-09-1.mp4?linkonly | Multi-bit addition }} | {{ :class:cm:cm-09-1_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-09-2.mp4?linkonly | Buses, logical ops }} | {{ :class:cm:cm-09-2_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-09-3.mp4?linkonly | Subtraction }} | {{ :class:cm:cm-09-3_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-09-4.mp4?linkonly | Multiplexers }} | {{ :class:cm:cm-09-4_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-09-5.mp4?linkonly | The ALU }} | {{ :class:cm:cm-09-5_en.mp4?linkonly | subs }} | | 10.\_ | {{ :class:cm:cm-10-1.mp4?linkonly | Sequential logic, delays }} | {{ :class:cm:cm-10-1_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-10-2.mp4?linkonly | Edge-triggered logic }} | {{ :class:cm:cm-10-2_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-10-3.mp4?linkonly | Flip-flops }} | {{ :class:cm:cm-10-3_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-10-4.mp4?linkonly | Designing a CPU }} | {{ :class:cm:cm-10-4_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-10-5.mp4?linkonly | Operating a CPU }} | {{ :class:cm:cm-10-5_en.mp4?linkonly | subs }} | | 11.\_ | {{ :class:cm:cm-11-1.mp4?linkonly | Finite State Machines }} | {{ :class:cm:cm-11-1_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-11-2.mp4?linkonly | FSM representation }} | {{ :class:cm:cm-11-2_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-11-3.mp4?linkonly | FSM example }} | {{ :class:cm:cm-11-3_en.mp4?linkonly | subs }} | | 12.\_ | {{ :class:cm:cm-12-1.mp4?linkonly | Regular expressions }} | {{ :class:cm:cm-12-1_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-12-2.mp4?linkonly | Converting REs to FSMs }} | {{ :class:cm:cm-12-2_en.mp4?linkonly | subs }} | | 13.\_ | {{ :class:cm:cm-13-1.mp4?linkonly | Non-deterministic FSMs }} | {{ :class:cm:cm-13-1_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-13-2.mp4?linkonly | Deterministic FSMs }} | {{ :class:cm:cm-13-2_en.mp4?linkonly | subs }} | | | {{ :class:cm:cm-13-3.mp4?linkonly | Example NFA to DFA }} | {{ :class:cm:cm-13-3_en.mp4?linkonly | subs }} | | 14.\_ | {{ :class:cm:cm-14-1.mp4?linkonly | Regular grammars }} | {{ :class:cm:cm-14-1_en.mp4?linkonly | subs }} | /********* 4. {{ :class:cm:cm-04.mp4?linkonly | Negative and floating numbers }}\\ 5. {{ :class:cm:cm-05.mp4?linkonly | Source coding }}\\ 6. {{ :class:cm:cm-06-1.mp4?linkonly | Channel coding, parity }}\\ \_\_\_\_{{ :class:cm:cm-06-2.mp4?linkonly | Error detection }}\\ \_\_\_\_{{ :class:cm:cm-06-3.mp4?linkonly | Error correction }}\\ 7. {{ :class:cm:cm-07-1.mp4?linkonly | Boolean algebra }}{{ :class:cm:cm-07-1_en.mp4?linkonly | subs }}\\ \_\_\_\_{{ :class:cm:cm-07-2.mp4?linkonly | Properties }}{{ :class:cm:cm-07-2_en.mp4?linkonly | subs }}\\ \_\_\_\_{{ :class:cm:cm-07-3.mp4?linkonly | Canonical form }}{{ :class:cm:cm-07-3_en.mp4?linkonly | subs }}\\ \_\_\_\_{{ :class:cm:cm-07-4.mp4?linkonly | Karnaugh maps }}{{ :class:cm:cm-07-4.mp4?linkonly | subs }}\\ \_\_\_\_{{ :class:cm:cm-07-5.mp4?linkonly | Interesting operations }}{{ :class:cm:cm-07-5_en.mp4?linkonly | subs }} *********/ == Slides (PDF) == - {{ ::class:cm:cm-01.pdf | Computer organisation }} - {{ ::class:cm:cm-02.pdf | Positional number systems }} - {{ ::class:cm:cm-03.pdf | Unsigned integer arithmetic }} - {{ ::class:cm:cm-04.pdf | Signed integer representation }} - {{ ::class:cm:cm-05.pdf | Source coding and compression }} - {{ ::class:cm:cm-06.pdf | Channel coding }} - {{ ::class:cm:cm-07.pdf | Logic and Boolean algebra }} - {{ ::class:cm:cm-08.pdf | Logic circuits }} - {{ ::class:cm:cm-09.pdf | Parallel logic circuits }} - {{ ::class:cm:cm-10.pdf | Sequential logic }} - {{ ::class:cm:cm-11.pdf | Finite state machines }} - {{ ::class:cm:cm-12.pdf | Regular expressions }} - {{ ::class:cm:cm-13.pdf | Determinism }} - {{ ::class:cm:cm-14.pdf | Grammars and languages }} - {{ ::class:cm:cm-15.pdf | Context-free languages and parsing }} == Exercises (PDF) == - {{ ::class:cm:quiz-01.pdf | Computer organisation }} - {{ ::class:cm:quiz-02.pdf | Positional number systems }} - {{ ::class:cm:quiz-03.pdf | Unsigned integer arithmetic }} - {{ ::class:cm:quiz-04.pdf | Signed integer representation }} - {{ ::class:cm:quiz-05.pdf | Source coding and compression }} - {{ ::class:cm:quiz-06.pdf | Channel coding }} - {{ ::class:cm:quiz-07.pdf | Logic and Boolean algebra }} - {{ ::class:cm:quiz-08.pdf | Logic circuits }} - {{ ::class:cm:quiz-09.pdf | Parallel logic circuits }} - {{ ::class:cm:quiz-10.pdf | Sequential logic }} - {{ ::class:cm:quiz-11.pdf | Finite state machines }} - {{ ::class:cm:quiz-12.pdf | Regular expressions }} - {{ ::class:cm:quiz-13.pdf | Determinism }} - {{ ::class:cm:quiz-14.pdf | Grammars and languages }} - {{ ::class:cm:quiz-15.pdf | Context-free languages and parsing }} == Programs == Simple CPU simulator (week 10) * {{ https://kuas.org/~piumarta/cm/cpusim.html | in-browser (Javascript) }} * {{ ::class:cm:cpusim.c | C program }} First word printer (week 11) * {{ ::class:cm:loops.py | loops.py }} using loops * {{ ::class:cm:fsm.py | fsm.py }} state machine * {{ ::class:cm:table.py | table.py }} transition table Word counter (week 11) * {{ ::class:cm:ans-wc.py | wc.py }} transition table State machine multiplier (week 12) * {{ ::class:cm:ans-multiply-fsm.py | multiply-fsm.py }} Recursive-descent parsing (week 15) * {{ ::class:cm:parse-eg1.py | parse-eg1.py }} recognition * {{ ::class:cm:parse-eg2.py | parse-eg2.py }} with semantic value * {{ ::class:cm:parse-eg3.py | parse-eg3.py }} expressions and AST Parsing workshop (additional) * {{ ::class:cm:w15.tar.gz | 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.