FIT1008 Notes PDF

Preview

Summary

all lecture notes compiled...

Description

FIT1008 Notes Table of Contents Week 1.....................................................................................................................................................3 Lecture 1...............................................................................................................................................................3 Integer Representation.........................................................................................................................................3 MIPS.....................................................................................................................................................................4 Von Neumann architecture.........................................................................................................................................................4 Machine code..............................................................................................................................................................................4 Words..........................................................................................................................................................................................4 Why is assembly needed?...........................................................................................................................................................4 RISC..............................................................................................................................................................................................4 CISC..............................................................................................................................................................................................5 MIPS.............................................................................................................................................................................................5 MIPS Instruction Execution.........................................................................................................................................................6 MIPS Memory..............................................................................................................................................................................7 Assembler directives...................................................................................................................................................................9 Instruction Set Basics................................................................................................................................................................10 Unconditional Jumps and call, plus instruction formats...........................................................................................................13 MIPS Instruction Format...........................................................................................................................................................14 Conditional control transfer instructions..................................................................................................................................15

Week 2...................................................................................................................................................15 MIPS Loops.........................................................................................................................................................15

Week 3...................................................................................................................................................16 MIPS Local Variables...........................................................................................................................................16 Need for memory diagrams......................................................................................................................................................16 Memory Diagrams.....................................................................................................................................................................16 Properties of local variables......................................................................................................................................................17 System stack and the stack pointer...........................................................................................................................................17 Frame Pointer and Memory Diagrams......................................................................................................................................17 Example:....................................................................................................................................................................................18

MIPS Functions...................................................................................................................................................18 Properties of Functions.............................................................................................................................................................18 Functions Calling Convention....................................................................................................................................................18 Example Function Call - Caller...................................................................................................................................................19 Example Function Call – Callee..................................................................................................................................................19 Function Returning - Callee.......................................................................................................................................................20 Function Returning – Caller.......................................................................................................................................................21

MIPS Recursion...................................................................................................................................................21 Recursion Example – Caller.......................................................................................................................................................22 Recursion Example – Callee.......................................................................................................................................................22 Non-Linear Recursion................................................................................................................................................................23

Week 4...................................................................................................................................................23 Sorting, invariants, stability and incrementality..................................................................................................23 Bubble Sort................................................................................................................................................................................23 Optimising bubble sort..............................................................................................................................................................24 Incremental Sorting algorithms.................................................................................................................................................24 Stability......................................................................................................................................................................................25 Selection Sort............................................................................................................................................................................25 Insertion Sort.............................................................................................................................................................................25

Asymptotic Time Complexity (Big O Notation)....................................................................................................26

Running Time.............................................................................................................................................................................26 Computational Time Complexity...............................................................................................................................................26 Big O Time Complexity..............................................................................................................................................................27 How to compute Big O?............................................................................................................................................................27 Common Big O efficiency classes..............................................................................................................................................27 Best/Worst/Average case complexity.......................................................................................................................................27

Exceptions and Assertions...................................................................................................................................28 Preconditions and Postcondition..............................................................................................................................................28 Exceptions.................................................................................................................................................................................28 Exception Handling....................................................................................................................................................................28 Exception handling in Python....................................................................................................................................................28 Raising exceptions in Python.....................................................................................................................................................28 Assertions..................................................................................................................................................................................29 Assertions v Exceptions.............................................................................................................................................................29

Week 5...................................................................................................................................................29 OOP and Unit Testing – Encapsulation!...............................................................................................................29 Defining Classes.........................................................................................................................................................................29 Instantiating and using classes..................................................................................................................................................29 Inheritance................................................................................................................................................................................30 Unit Testing................................................................................................................................................................................30

Namespaces, Scoping, and Mutability.................................................................................................................30 Variables again...........................................................................................................................................................................30 Namespaces..............................................................................................................................................................................30 Binding a name..........................................................................................................................................................................31 Scoping......................................................................................................................................................................................31 Scoping Rules.............................................................................................................................................................................31

Week 6...................................................................................................................................................31 ADTs and Stacks..................................................................................................................................................31 Data Types.................................................................................................................................................................................31 Abstract Data types...................................................................................................................................................................31 Data Structures..........................................................................................................................................................................32 Clarification between data types and data structures..............................................................................................................32 Stack ADT...................................................................................................................................................................................32 Implementing stacks with arrays...............................................................................................................................................33

Week 7...................................................................................................................................................34 Linked Nodes.......................................................................................................................................................34

Week 8...................................................................................................................................................34 Iterators..............................................................................................................................................................34

Week 11.................................................................................................................................................34 Binary Tree Traversal.................................................................................................................................................................34

Expression Trees..................................................................................................................................................35

Week 12.................................................................................................................................................36 Priority Queues...................................................................................................................................................36 Heaps..................................................................................................................................................................36 Heap Sort (in place).............................................................................................................................................36

Week 1 Lecture 1 Integer Representation Nothing special about decimal – same as any other base. Ratio between numbers in different columns is multiples of the base i.e. 60 = 10 * 06 in decimal. Larger bases give smaller representation of numbers than smaller bases, but require more complex symbols. Range of unsigned integers we can represent with n bits is 0 - (2^n)-1 Binary to hex

Hex to binary

Signed integers - Gonna have to store sign in one of our n bits - Three different representations o Signed magnitude representation  Most significant bit stores the sign i.e. leftmost  0 = pos, 1 = neg  Rest of string stores abs of num  Range of signed integers is –(2^n-1 - 1), …, 2^n-1 -1  Means we have both +0 and -0 – not efficient  Addition is fiddly – have to look at signs o Two complement representation  Aim: makes arithmetic easier  For N bits, -M is represented as 2N – M  For example, with N=4







 -1 is represented as 24 −1=16 −1=15 =1111  -8 is represented as 24 −8=16 −8=8=1000 But be careful, M must be within range:  Half of the numbers are positive and half are negative. For example, with 4 bits, 0000 to 0111 are positive and 1000 to 1111 are negative  So, M must be within −2N −1 , … , 2N −1−1

 Two’s complement to decimal  Give MSB (most significant bit) a negative weight e.g. if using 8 bits then MSB has positional value −27 not +27  101011 to decimal: 5 3 1 0 o 1∗(−2 )+ 1∗2 +1∗2 +1∗2 =−21 Negating in two’s complement is easy  NOT + 1 i.e. flip all bits then add 1

MIPS Von Neumann architecture - Consists of o Memory  Stores both data and instructions o Cpu  Arithmetic/Logic unit (ALU) does calculations  Registers store temporary results  Control decides what to do next o Input/output  Duh Machine code - Cpu runs machine code – 1’s and 0’s - Each cpu type usually requires a different machine language Words - Chunk of bits used to store a basic unit of data in a computer - MIPS is 32 bit (or 4 byte), some CPU’s use 64 bit Why is assembly needed? - Machine code is too hard for humans - Assembly supports variables and line comments and is human readable, but is easy converted into machine language - Usually a 1 to 1 relationship between assembly instructions and machine language instructions RISC Reduced Instruction Set Computer

- All instructions are the same length - Of similar complexity - Mostly able to be able to run in the same time - Easily decoded by hardware - Easier to build, cheaper, consumes less power - Currently very common CISC Complex Instruction Set Computer - Instructions vary in length and complexity - Decoding requires hardware-embedded code - Can be very fast for graphics MIPS - RISC chip - Regaining popularity - Made in 80’s - Runs code with fetch-decode-execute

-

-

-

-

32 general purpose register o Fast but expensive memory o Physically located on the cpu chip o Each stores one word ALU o Performs computations on register and integer values (not main memory) o Integer and bitwise arithmetic (including comparisons) Several special purpose registers o PC (program counter) o HI, LO (multiplication/division results) o IR (instruction register) o MAR/MRR/MWR (Memory address/read/write register) General Purpose registers o Prefixed with $ in assembly, so $0 to $31 o Also given names on usage conventions

o o o o o

Names are hardcoded Names increase usability, so we will use them Can theoretically be used in any way Conventions assign certain uses to certain GPRs CONVENTION GOOD

o - Special Purpose registers o Multiplying two 32 bit numbers might require 64 bits to fit o HI contains the high 32, LO contains the low...