COS332 — Study Guide

Routing Algorithms & Character Encodings

This guide covers two core COS332 exam topics in depth. Part 1–3 cover routing algorithms (Dijkstra and Bellman-Ford)
with fully worked examples, visual diagrams, and exam tips. Part 4–6 cover character encodings (ASCII, EBCDIC,
Unicode, UTF-8) with conversion techniques, visual aids, and calculator instructions.

Section Topic

Part 1 Dijkstra's Algorithm — Concept, Steps, Worked Example, Exam Tips

Part 2 Bellman-Ford Algorithm — Concept, Steps, Worked Example, Count-to-Infinity

Part 3 Dijkstra vs Bellman-Ford — Side-by-Side Comparison

Part 4 Character Encodings — ASCII, EBCDIC, Unicode, UTF-8

Part 5 Conversions — By Hand and on a Calculator

Part 6 Quick Reference Tables & Exam Tips

PART 1 — Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from one source node to ALL other nodes in a weighted graph with
non-negative edge costs. It is the algorithm behind OSPF (Open Shortest Path First), the most widely used link-state
IGP.

1.1 Properties at a Glance

Property Value Practical Meaning

Algorithm type Greedy Always picks the nearest unvisited node — never revisits

Approach Centralised Needs a complete map of the network (LSDB) before it can run

Adaptability Static / non-adaptive Cannot react to changes without re-running from scratch

Negative costs? NO All link costs must be zero or positive

Used in protocol OSPF (IGP) Routers flood topology info; each runs Dijkstra locally

OSI Layer Layer 3 — Network Determines the routes used to forward IP packets

Time complexity O(V²) basic Fast for typical network sizes; O(E log V) with a heap

1.2 Key Terms

Term Definition

S (confirmed set) The set of nodes whose shortest path from the source is FINALISED. Once in S, never
updated again.

Tentative cost The best-known distance to a node so far. May still improve until the node joins S.

∞ (infinity) Initial cost for all nodes except the source. Means "not yet reachable".

Next hop The first node on the shortest path toward the destination — this is what the routing table
stores.

Round number i Round i starts when |S| = i. Round 1 always starts with just the source node in S.

1.3 Step-by-Step Method

Step Action

1. Initialise Source cost = 0. All others = ∞. S = { source }. Record next hop = source for source.

2. Update For each neighbour N of the node just added to S: candidate = cost(current node) + link_weight(to N) If
neighbours candidate < N's current tentative cost → update N's cost and next hop.

3. Select From all nodes NOT in S, find the one with the SMALLEST tentative cost. Add it to S. Its cost is now
next node FINAL.

4. Repeat Go back to Step 2, using the newly added node. Continue until S contains all nodes.

5. Read Follow the next-hop pointers from source to reconstruct any shortest path.
paths

1.4 Fully Worked Example (from COS332 Textbook)

Network topology — link costs:

Link Cost Link Cost Link Cost

A–B 1 B–D 4 C–E 1

 Link Cost Link Cost Link Cost

A–C 9 B–G 9 C–F 1

A–E 6 B–C 10 E–F 5

E–G 7

F–G 9

Figure 1: Network graph. Green edges = shortest paths found by Dijkstra. Numbers in nodes = final cost from A.

Dijkstra trace — running from source A. Each column shows the tentative cost after that round. The node in bold on
the right is added to S that round (its cost is now final).

Round & S contents A B C D E F G Node finalised

Start |S|=1 S={A} 0 ∞ ∞ ∞ ∞ ∞ ∞ — (source)

Rnd 1 A→nbrs 0 1 (A 9 ∞ 6 (A ∞ ∞ B cost=1

→B) (A→C) →E)
 Round & S contents A B C D E F G Node finalised

Rnd 2 |S|=2 0 1 9 5 (B 6 ∞ 10 (B→G) D cost=5

→D)

Rnd 3 |S|=3 0 1 9 5 6 ∞ 10 E cost=6

Rnd 4 |S|=4 E→nbrs update 0 1 7 5 6 11 10 (uncha C cost=7

C,F,G (E→C) (E→F) nged)

Rnd 5 |S|=5 C→nbrs update F 0 1 7 5 6 8 10 F cost=8

(C→F)

Rnd 6 |S|=6 F→nbrs: 0 1 7 5 6 8 10 (uncha G cost=10

G=8+9=17>10 nged)

FINAL all confirmed 0 1 7 5 6 8 10 DONE

Final shortest paths from A:

Dest Cost Full Path Key insight

B 1 A→B Direct link — cheapest possible

D 5 A→B→D Via B (cost 1+4=5)

E 6 A→E Direct link cheaper than via B

C 7 A→B→D→E→C NOT via direct A–C (cost 9)! Indirect is cheaper.

F 8 A→B→D→E→C→F Reaches F via C at cost 7+1=8

G 10 A→B→D→E→G Via E (6+7=13 < 10)? No: A→E→G=6+7=13, A→B→D→E→G

also 13... check: A→B(1)→D(5)→E? No, D–E not listed. Re-check:
A→E=6, E→G=7 → 13. A→B=1,B→G=9 → 10. So via B→G=10
wins.

1.5 Dijkstra Exam Tips

TRICK — Round number rule: Round i STARTS with |S| = i. Round 1 = source only. "Node added in round 3→4"
means the node finalised when |S| becomes 4.
TRICK — Never update S members: Once a node joins S, its cost is PERMANENT. Never lower it again, even if
you find a shorter-looking path.
TRICK — Only update if strictly less: New candidate cost must be LESS THAN current tentative cost. Equal costs
→ no update (keep existing next hop).
TRICK — Direct links are not always cheapest: A–C = 9 directly, but A→B→D→E→C = 7. Always compare ALL
paths, not just direct links.
TRICK — Initial cost in round 1: "Initial cost to C during round 1" = ONLY the direct link cost (9), not any indirect
path. Indirect paths are discovered in later rounds.
TRICK — What "reachable" means: "During which round does E become reachable?" = the round when E is
ADDED TO S (not when it first gets a tentative cost).
TRICK — Ties: If two unvisited nodes have equal tentative cost, you can pick either. The final answer is still
correct.
PART 2 — Bellman-Ford Algorithm
Bellman-Ford computes shortest paths in a distributed fashion — each router only needs its neighbours' routing tables.
It underpins RIP (Routing Information Protocol).

2.1 Properties at a Glance

Property Value Practical Meaning

Algorithm type Dynamic Iteratively improves estimates by combining local + neighbour

programming knowledge

Approach Distributed Each router shares its table with direct neighbours only — no global
map needed

Adaptability Adaptive Automatically reacts when routing tables change due to topology shifts

Negative costs? YES (with limits) Handles negative link costs but NOT negative-weight cycles

Used in protocol RIP (IGP) Each router periodically broadcasts its full table to neighbours

OSI Layer Layer 3 — Network Builds the distributed routing tables that guide packet forwarding

Main weakness Count to infinity When a link fails, costs can slowly spiral upward — converges very
slowly

2.2 The Core Formula

For router D wanting to reach destination X:

D(X) = min over all neighbours n of: [ cost(D, n) + D_n(X) ]

Plain English: "My cheapest route to X is through whichever neighbour can reach X at the lowest combined cost —
neighbour link cost PLUS their own cost to X."

2.3 Step-by-Step Method

Step Action

1. Initialise Each router creates a table: distance to itself = 0, all others = ∞.

2. Share Routers periodically send their FULL routing table to ALL direct neighbours.
tables

3. Update on When D receives a table from neighbour N, for each destination X: candidate = cost(D→N) +
receipt N's_cost(X) If candidate < D's current cost to X → UPDATE: set D's cost=candidate, next hop=N

4. Repeat Keep exchanging and updating. After enough rounds, all tables converge to correct values.

5. Watch for If a cost keeps increasing indefinitely after a failure → count-to-infinity problem (see 2.5).
loops

2.4 Fully Worked Example — 2022 Exam Paper

Three routers C, D, E. Routing tables at time t■ (given). We must find what D's table looks like after receiving updates
from C (at t■) and E (at t■).

Initial routing tables at t■:

Node C Node D Node E

Dest Cost Next Dest Cost Next Dest Cost Next

A 10 B A 20 E A 15 F

A 2 B C 3 C D 4 D
 D 3 D E 4 E F 5 F

G 8 E G 5 F

Derived link costs: D↔C = 3 (C's table shows D at cost 3 next hop D — so D is directly connected to C at cost 3). D↔E = 4
(D's table shows E at cost 4 next hop E).

EVENT at t■: Node C sends its routing table to Node D.

Apply the formula for every destination in C's table:

Dest X D's current cost Via C: cost(D,C) + C's Better? Action on D's table
to X cost(X)

A 20 (next hop E) 3 + 10 = 13 YES 13 < 20 UPDATE: A | cost 13 | next hop C

B (not in ∞ 3 + 2 = 5 ...BUT wait: C lists A N/A No B entry in C — cannot learn B

D) twice, not B

D (self) 0 3+3=6 NO 6 > 0 No change

Answers after t■ (exam sub-questions a and b):

Sub- Question Answer Working

Q

(a) Entry for A after C's table A | cost 13 | next hop C cost(D,C)+C's A = 3+10 = 13 < 20 ✓

(b) Entry for B after C's table No entry — B is unreachable C has no route to B; D cannot learn
B from C

EVENT at t■: Node E sends its routing table to Node D.

Apply the formula for every destination in E's table:

Dest X D's current cost to Via E: cost(D,E) + E's Better? Action on D's table
X cost(X)

A 13 (updated at t■) 4 + 15 = 19 NO 19 > 13 No change — keep 13 via C

D (self) 0 4+4=8 NO 8 > 0 No change

F (not in ∞ 4+5=9 YES 9 < ∞ ADD: F | cost 9 | next hop E

D)

G 8 (next hop E) 4+5=9 NO 9 > 8 No change — keep G at cost 8 via

E

Answers after t■ (exam sub-questions c and d):

Sub- Question Answer Working

Q

(c) Entry for F after E's table F | cost 9 | next hop E D had no F; 4+5=9 — new entry
added

(d) Entry for G after E's table G | cost 8 | next hop E 4+5=9 is NOT less than 8 — no
(unchanged) update

2.5 Count-to-Infinity Problem

This is Bellman-Ford's famous weakness. It occurs when a link fails and routers mistakenly believe they can still reach a
destination via each other — creating a routing loop.
 Figure 2: Count-to-Infinity — when A–B fails, B and C loop each other, costs escalate until hitting the maximum (16 in RIP).

Round B's cost to A C's cost to A What is actually happening

Before cost=1 via A cost=2 via B Correct. A–B link works fine.
failure

A–B link ∞ (link down) cost=2 via B B knows A is gone. C does NOT know yet.
fails! (STALE — old info)

B reads C's cost=3 via C cost=2 via B (still B thinks: C says A=2, so I'll go C at 1+2=3. LOOP!
table stale)

C reads B's cost=3 via C cost=4 via B C updates: B says A=3, so 1+3=4. Both looping!
table

...continues cost=5 via C cost=6 via B Costs keep climbing: 5→7→9... until max (16=∞ in RIP)
...

Solutions to count-to-infinity: (1) Split horizon — do not advertise a route back toward the neighbour you learned it from. (2)
Poison reverse — advertise the route back but with infinite cost. (3) Maximum hop count — RIP uses 16 as infinity; any cost ≥
16 = unreachable.

2.6 Bellman-Ford Exam Tips

TRICK — The formula: cost(self→neighbour) + neighbour's cost to destination. Apply it for EVERY row in the
received table.
TRICK — Only update if strictly less: New cost must be STRICTLY LESS THAN current cost. Equal costs → no
update.
TRICK — No route = cannot learn: If the sending router's table has no entry for destination X, you CANNOT learn
about X from that exchange.
TRICK — Next hop identity: The next hop is ALWAYS the neighbour who sent you the table — not the ultimate
destination. "Received from C → next hop = C".
TRICK — Self-cost is always 0: A router's cost to itself = 0. Seeing it in a neighbour's table: cost(D,C) + C's cost
to C = 3+0 = 3 = the link cost.
TRICK — Count-to-infinity trigger: Only occurs on LINK FAILURE — not during normal convergence. Know the
difference.
TRICK — RIP max hop count: RIP sets 16 = infinity. Any route with cost ≥ 16 is treated as unreachable, bounding
the count-to-infinity problem.
PART 3 — Dijkstra vs Bellman-Ford: Side-by-Side
Feature Dijkstra's Algorithm Bellman-Ford Algorithm

Algorithm type Greedy — picks minimum each round Dynamic programming — iterates edges

Information needed Full network map (LSDB — all links) Only direct neighbours' routing tables

Centralised or distributed? Centralised (full map → run locally) Distributed (each node ↔ neighbours)

Handles negative link costs? NO — all costs must be ≥ 0 YES — but not negative-weight cycles

Speed of convergence Fast — O(V²) or O(E log V) Slower — O(VE) worst case

Reacts to link failure? Only after topology update + re-run Adapts via updates (risk: count-to-∞)

Used in which protocol? OSPF (link-state protocol) RIP (distance-vector protocol)

Routing info exchanged LSAs (full topology advertisements) Distance vectors (just routing tables)

Scales well? Yes — OSPF uses areas to limit scope Poor — table size grows with network

Memory requirement High — needs full LSDB in RAM Low — only neighbour tables needed

Main weakness Needs full topology; complex flooding Count-to-infinity on link failure

OSI layer Layer 3 (Network) Layer 3 (Network)

Memory Aid: Dijkstra = Determined (needs full map, one-shot greedy). Bellman-Ford = Back-and-forth (distributed, adaptive,
keeps updating neighbours).
PART 4 — Character Encodings: ASCII, EBCDIC, Unicode, UTF-8
From the COS332 textbook (Prof MS Olivier): "While most computers use some superset of ASCII to encode characters, not all
do... If two computers use different character encoding schemes they will obviously not be able to communicate directly with one
another." — Character encoding is a Presentation Layer (OSI Layer 6) concern.

4.1 ASCII — American Standard Code for Information Interchange

Developed in 1963. Uses 7 bits → 128 characters (code points 0–127). The foundation that all modern encodings are
built upon. Everything from 0–31 is a non-printable control character; 32–127 are printable.

Figure 3: ASCII character map. Top row shows each character; bottom shows its decimal code. Colour-coded: green=uppercase,
pink=lowercase, blue=digits, orange=punctuation.

Character / Group Decimal Hex Quick Memory Trick

NUL (null) 0 0x00 First character — nothing

TAB 9 0x09 Tab = 9 (like Tab key is often 9 spaces)

 Character / Group Decimal Hex Quick Memory Trick

LF (line feed / newline) 10 0x0A Unix newline — 10 is easy to remember

CR (carriage return) 13 0x0D Windows uses CR+LF (13+10) for newlines

ESC (escape) 27 0x1B Used in ANSI escape codes for terminal control

Space 32 0x20 First printable character. 32 = 0x20 (clean hex)

Digit '0' 48 0x30 '0'=48. Add digit value: '5'=53. Subtract 48 to get number.

Uppercase A 65 0x41 A=65. B=66. Z=90. Formula: 64 + position (A=1st)

Lowercase a 97 0x61 a=97. b=98. z=122. Formula: 96 + position

Case difference 32 0x20 lowercase = uppercase + 32. 'A'(65)+32='a'(97)

DEL (delete) 127 0x7F Last ASCII character. All 7 bits = 1111111

4.2 EBCDIC — Extended Binary Coded Decimal Interchange Code

IBM's 8-bit encoding for mainframe computers, created in 1964. Uses a completely different layout from ASCII — letters
are NOT contiguous (there are gaps between I–J and R–S in the alphabet). From the textbook: 'A computer using
EBCDIC represents uppercase A with 193, B with 194...'

Char ASCII dec EBCDIC dec EBCDIC Char ASCII dec EBCDIC dec EBCDIC
hex hex

A 65 193 0xC1 a 97 129 0x81

B 66 194 0xC2 b 98 130 0x82

C 67 195 0xC3 z 122 169 0xA9

I 73 201 0xC9 0 48 240 0xF0

J 74 209 0xD1 9 57 249 0xF9

R 82 217 0xD9 Space 32 64 0x40

S 83 226 0xE2 GET 71 199 0xC7

(G)

Z 90 233 0xE9 GET (E) 69 197 0xC5

Textbook example: GET in ASCII = [71, 69, 84]. GET in EBCDIC = [199, 197, 227]. There is NO formula — you must
use a lookup table. Note the I–J gap: I=0xC9 (201) but J=0xD1 (209) — eight values are skipped!

4.3 Unicode — The Universal Character Standard

Unicode assigns a unique code point to every character in every human writing system — over 149,000 characters as of
Unicode 15. Written as U+XXXX (hex). Unicode is the CHARACTER SET (assigns numbers); UTF-8/16/32 are the
ENCODINGS (store those numbers as bytes).
 Figure 4: Unicode is divided into 17 planes. The Basic Multilingual Plane (U+0000–U+FFFF) contains most everyday characters.

Term Meaning and Example

Code point The unique number for a character. Written U+XXXX. Example: U+0041 = Latin
capital A

BMP (Basic Multilingual Plane) Plane 0: U+0000–U+FFFF. All common scripts. Fits in 16 bits.

Supplementary planes Planes 1–16: U+10000–U+10FFFF. Emoji, historic scripts, rare ideographs.

Code unit The basic storage element of an encoding. UTF-8 uses 8-bit units; UTF-16 uses
16-bit units.

Surrogate pair UTF-16 mechanism for supplementary chars: two 16-bit code units (0xD800–0xDFFF
range).

BOM (Byte Order Mark) U+FEFF at file start — signals encoding type and byte order. UTF-8 BOM = EF BB
BF.

Unicode ≠ UTF-8 Unicode = the standard assigning numbers. UTF-8 = one way to store those numbers
as bytes.

4.4 UTF-8 — The Internet's Dominant Encoding

UTF-8 encodes Unicode code points into 1–4 bytes. It is backward compatible with ASCII for the first 128 characters
(U+0000–U+007F). Over 98% of web pages use UTF-8 as of 2024.
Figure 5: UTF-8 byte structure. Orange bits are fixed markers identifying the byte type. Green bits carry the actual code point data.
1-byte range is identical to ASCII.

Code Point Range Decimal Range Bytes 1st Byte Pattern Remaining Bytes

U+0000 – U+007F 0 – 127 1 0xxxxxxx (0–127) — none —

U+0080 – U+07FF 128 – 2047 2 110xxxxx (192–223) 10xxxxxx (128–191)

U+0800 – U+FFFF 2048 – 65535 3 1110xxxx (224–239) 10xxxxxx (128–191)

U+10000 – U+10FFFF 65536 – 1114111 4 11110xxx (240–247) 10xxxxxx (128–191)

Rule Description

1-byte = ASCII If the first (and only) byte starts with 0 → single-byte character, identical to ASCII.

Count leading 1s The number of leading 1-bits in the first byte tells you the total byte count. 110... = 2, 1110... =
3, 11110... = 4.

Continuation bytes Every continuation byte (bytes 2, 3, 4) ALWAYS starts with 10xxxxxx (values 128–191).

Self-synchronising You can always find the start of a character: look for any byte that does NOT start with 10.

No byte-order issue Unlike UTF-16, UTF-8 has no byte-order ambiguity — no BOM needed for identification.

Property UTF-8 UTF-16 UTF-32

Min bytes/char 1 2 4

Max bytes/char 4 4 4
Property UTF-8 UTF-16 UTF-32

ASCII compatible? YES — first 128 identical No — uses ≥ 2 bytes always No

Byte order issues? None — byte order YES — needs BOM (LE/BE) YES — needs BOM
irrelevant

Variable width? Yes (1–4 bytes) Yes (2 or 4 bytes) No — always 4 bytes

Best used for Web, files, APIs, email Windows/Java/JS internals Specialised — very
memory heavy

Internet dominance >98% of web pages (2024) Rare on web Extremely rare
PART 5 — Conversions: By Hand and on a Calculator
5.1 Decimal ↔ Hexadecimal — The Foundation
Conversion Method Worked Example

Decimal → Hex Divide by 16 repeatedly. Remainders (bottom to 65 ÷ 16 = 4 rem 1 4 ÷ 16 = 0 rem 4 Read

top) = hex digits. 0–9 stay as digits; 10=A, 11=B, upward: 41 → 0x41 ✓
12=C, 13=D, 14=E, 15=F.

Hex → Decimal Multiply each digit by its power of 16 (right to left: 0x41: (4 × 16¹) + (1 × 16■) = 64 + 1 = 65 ✓
16■, 16¹, 16²...) Then add all products.

Decimal → Binary Divide by 2 repeatedly. Remainders (bottom to 65 → 0x41 → 0100 0001 Verify: 64+1 = 65 ✓
top) = binary. OR: convert to hex first, then each
hex digit → 4 bits.

Binary → Decimal Multiply each bit by its power of 2 (right to left). 01000001: 2■+2■ = 64+1 = 65 ✓
Add all non-zero terms.

5.2 ASCII Conversion Shortcuts — No Table Needed

For letters and digits you do NOT need to memorise the full table — just remember these formulas:

Character type Formula Examples

Uppercase A–Z ASCII = 64 + alphabetical position A=64+1=65, M=64+13=77, Z=64+26=90

Lowercase a–z ASCII = 96 + alphabetical position a=96+1=97, m=96+13=109, z=96+26=122

Digit '0'–'9' ASCII = 48 + digit value '0'=48, '5'=53, '9'=57

Uppercase → Lowercase lowercase = uppercase + 32 'A'(65) + 32 = 'a'(97)

Lowercase → Uppercase uppercase = lowercase − 32 'z'(122) − 32 = 'Z'(90)

Char → Hex Get decimal first, then ÷16 'A'=65 → 65=4×16+1 → 0x41

Hex → Char Convert hex to decimal, use formula 0x61 = 6×16+1 = 97 = 'a'
above

5.3 UTF-8 Encoding — Step-by-Step Worked Examples

Example 1: Encode 'R' (U+0052, decimal 82)

Step Working Result

1. Find code R = ASCII 82 = U+0052 82 decimal

point

2. Check range 82 ≤ 127 → 1-byte UTF-8 range (U+0000–U+007F) 1 byte needed

3. Apply pattern 1-byte: 0xxxxxxx → fill 7 bits with 82 in binary 0 1010010

4. Final byte 01010010 = 0x52 UTF-8: 0x52 (identical to ASCII ✓)

Example 2: Encode '£' (U+00A3, decimal 163)

Step Working Result

1. Code point £ = U+00A3 = 163 decimal 163

2. Binary of 163 163 = 128+32+2+1 = 10100011 10100011 (8 bits)

3. Range check 128–2047 → 2 bytes, pattern: 110xxxxx 10xxxxxx 11 payload bits needed
 Step Working Result

4. Pad to 11 bits 163 = 10100011 → pad left: 000 10100011 00010100011

5. Split into First 5 bits: 00010 | Last 6 bits: 100011 00010 | 100011
groups

6. Fill pattern 110[00010] 10[100011] 11000010 10100011

7. Convert to hex 11000010 = 0xC2, 10100011 = 0xA3 UTF-8 bytes: C2 A3

8. Verify 0xC2 starts 110 ✓ 0xA3 starts 10 ✓ Valid UTF-8 sequence ✓

Example 3: DECODE UTF-8 bytes C3 B6 back to a character

Step Working Result

1. Convert to C3 = 11000011, B6 = 10110110 Two bytes

binary

2. Identify C3 starts with 110 → 2-byte sequence Extract payload from both
sequence bytes

3. Extract 110[00011] → take: 00011 10[110110] → take: 110110 00011 and 110110
payload bits

4. Combine Concatenate: 00011 110110 00011110110 (11 bits)

5. Convert to 00011110110 = 16+8+4+2 = 246... recalc: 11110110b? No: 246 decimal

decimal 00011110110: 2■+2■+2■+2■+2²+2¹ = 128+64+32+16+4+2 = 246

6. To Unicode 246 decimal = U+00F6 U+00F6

7. Character U+00F6 = ö (o with umlaut — German/Scandinavian) ö✓

5.4 Using a Casio Scientific Calculator

Most Casio fx-82, fx-991, and similar models have a BASE-N mode for number base conversions. This is essential for
converting between decimal, hex, and binary quickly in an exam.

Action How to do it (Casio fx-82/fx-991 series) What you see

Enter BASE-N Press MODE → select BASE (option 3, 4, or 5 depending DEC HEX BIN OCT labels appear
mode on model)

Set to Decimal Press the DEC softkey (F2 or similar) DEC indicator lights up
input

Decimal → Hex Type decimal number → press HEX softkey Result shown in hexadecimal

Decimal → Binary Type decimal number → press BIN softkey Result shown in binary

Hex → Decimal Press HEX mode → type hex digits (A–F available) → Decimal result shown
press DEC

Hex → Binary Press HEX mode → type hex → press BIN Binary result — use this for UTF-8
patterns!

fx-991EX Press MENU → option 5 (Base-N) → use softkeys to Cleaner display with more digits
CLASSWIZ switch bases

ASCII values No built-in function — MUST memorise key anchor A=65, a=97, 0=48, Space=32
points

Exam workflow for UTF-8: 1. Find decimal code point. 2. Use calculator BIN mode to get binary. 3. Apply UTF-8 pattern
manually (split bits, add markers). 4. Use calculator HEX mode to verify your byte values.
PART 6 — Quick Reference Tables & Exam Tips
6.1 Essential ASCII Values — Memorise These Anchors
Char Dec Hex Char Dec Hex Char Dec Hex

NUL 0 00 Space 32 20 '0' 48 30

TAB 9 09 '!' 33 21 '1' 49 31

LF 10 0A '@' 64 40 '9' 57 39

CR 13 0D 'A' 65 41 'a' 97 61

ESC 27 1B 'Z' 90 5A 'z' 122 7A

DEL 127 7F '[' 91 5B '\' 92 5C

6.2 UTF-8 Byte Pattern Quick Reference

Code Point Dec Range Bytes Byte Pattern How to Identify

U+0000–U+007F 0–127 1 0xxxxxxx First bit = 0 → single byte,

same as ASCII

U+0080–U+07FF 128–2047 2 110xxxxx 10xxxxxx Starts 110... → 2-byte

sequence

U+0800–U+FFFF 2048–65535 3 1110xxxx 10xxxxxx 10xxxxxx Starts 1110... → 3-byte

sequence

U+10000–U+10FFF 65536+ 4 11110xxx 10xxxxxx 10xxxxxx Starts 11110... → 4-byte

F 10xxxxxx

Continuation byte 128–191 — 10xxxxxx Starts 10... → continuation

(never first byte)

6.3 Encoding Systems Comparison

Encoding Year Bits Max chars Key facts

ASCII 1963 7 128 Foundation of modern encodings. Only English + punctuation.

EBCDIC 1964 8 256 IBM mainframes only. Letters NOT contiguous — no formula.

ISO 8859-1 1987 8 256 Western Europe. Extends ASCII with accented chars.

Unicode 1991 Up to 1.1M+ Universal standard — all human writing systems.

21

UTF-8 1992 8–32 1.1M+ Internet standard. ASCII-compatible. Variable width.

UTF-16 1996 16–32 1.1M+ Windows/Java internals. Surrogate pairs for Plane 1+.

UTF-32 1996 32 1.1M+ Fixed width, simple — but 4× memory vs UTF-8 for ASCII.

6.4 Dijkstra Quick Trace Template

Use this template in any exam. Replace A–G with your actual nodes. Start with source cost=0, all others ∞. Add one
node per row.

Round S contains Node just added Cost Updates made to tentative costs

1 {source} source 0 Set all direct neighbours

 Round S contains Node just added Cost Updates made to tentative costs

2 {source, X} ??? ??? Check all X's unvisited neighbours

3 {source, X, Y} ??? ??? Check all Y's unvisited neighbours

... ... ... ... ...

n {all nodes} last node ??? Done — all shortest paths found

6.5 Top 10 Exam Traps

# Topic The Trap The Correct Answer

1 Dijkstra Confusion about which round adds which Round i STARTS with |S|=i. Node added "from
rounds node round 3 to 4" is finalised at round 4.

2 Dijkstra initial "Initial cost to C during round 1" includes Round 1 initial cost = DIRECT link only. Indirect
cost indirect paths paths discovered in later rounds.

3 Dijkstra vs Saying Dijkstra is distributed or BF is Dijkstra = centralised (needs full map). BF =

Bellman centralised distributed (only neighbour tables).

4 BF next hop Setting next hop to the final destination Next hop = the NEIGHBOUR who sent you the
table. Always.

5 BF update rule Updating when new cost equals current Only update if STRICTLY LESS THAN. Equal cost
cost → no change.

6 ASCII '0' Thinking digit 0 has ASCII value 0 '0' = 48, NOT 0. Digits 0–9 = ASCII 48–57.

7 Unicode vs Using them interchangeably Unicode = character set (assigns numbers). UTF-8
UTF-8 = encoding (stores bytes).

8 UTF-8 1-byte Not knowing where single-byte ends Exactly U+0000–U+007F (0–127). Same as
range ASCII. U+0080 needs 2 bytes.

9 EBCDIC Trying to calculate EBCDIC from ASCII Impossible — EBCDIC has no formula. Letters are
formula arithmetically NOT contiguous. Use lookup table.

10 HTTP 406 Confusing character encoding rejection Encoding mismatch (Accept-Charset failure) →
with 404 406 Not Acceptable. 404 = resource not found.

Textbook Reference (Prof MS Olivier, COS332): GET in ASCII = [71, 69, 84]. GET in EBCDIC = [199, 197, 227]. GET in
Fieldata = [12, 10, 25]. HTTP 406 = server cannot encode response in any of the client's requested character encodings. Dijkstra
characteristics: greedy, static/non-adaptive, centralised. Bellman-Ford characteristics: distributed, adaptive. Problem:
Count-to-infinity.