3. Networks, Coding, and Cryptography

Networks, Coding, and Cryptography

Introduction to Networks, Coding, and Cryptography

Modern communication systems depend on mathematics to transmit information, protect data, detect errors, and connect devices efficiently.

Every time someone sends a message, opens a website, makes an online payment, or connects to a wireless network, mathematical principles help the system function reliably and securely.

Three important areas are:

• Networks: Mathematical structures describing connections between objects.

• Coding theory: Methods for representing information and detecting or correcting errors.

• Cryptography: Techniques for protecting information from unauthorized access or modification.

These areas use combinatorics, the mathematics of counting and arranging possibilities, along with probability, logic, and algebra.

Combinatorics helps answer questions such as:

• How many different binary messages are possible?

• How many passwords can be constructed?

• How many paths connect two computers?

• How many errors can a code detect or correct?

• How likely is a random transmission error?

• How many possible encryption keys exist?

Understanding these connections provides an introduction to the mathematics underlying computer networks, digital communication, and cybersecurity.

The Role of Combinatorics in Computer Science

Combinatorics is the branch of mathematics concerned with counting, arranging, and selecting objects.

Computers work with discrete information, making combinatorial methods especially important.

Examples include counting:

• Possible binary strings.

• Password combinations.

• Network routes.

• Error patterns.

• Encryption keys.

• Arrangements of data.

• Possible outcomes of algorithms.

Two fundamental counting principles are particularly useful.

The Addition Principle

If one task can be completed in a ways and a separate, mutually exclusive task can be completed in b ways, then choosing one of the tasks can be done in:

a + b ways

Example

A computer user can select either:

• One of 4 security questions.

• One of 3 alternative verification methods.

If exactly one method is selected, there are:

4 + 3 = 7 choices

The Multiplication Principle

If a process has several stages, and each stage has a fixed number of possibilities, the total number of outcomes is found by multiplying.

Total outcomes = n₁ × n₂ × ... × nₖ

Example

A digital code contains three digits.

Each digit can be any number from 0 to 9.

There are ten possibilities for each position.

Total codes:

10 × 10 × 10

= 1,000

This principle is fundamental to coding and cryptography.

Binary Numbers and Digital Information

Computers represent information using binary digits called bits.

A bit can have one of two values:

• 0

• 1

A sequence of bits is called a binary string.

For example:

10110101

is an eight-bit binary string.

Counting Binary Strings

Each bit has two possible values.

Therefore, the number of binary strings of length n is:

Number of binary strings = 2ⁿ

Worked Examples

For 3 bits:

2³ = 8

Possible strings:

000, 001, 010, 011, 100, 101, 110, 111

For 8 bits:

2⁸ = 256

For 16 bits:

2¹⁶ = 65,536

For 32 bits:

2³² = 4,294,967,296

Interpretation

Adding one bit doubles the number of possible binary strings.

This exponential growth is important in digital storage, communication systems, and encryption.

Counting Binary Strings with Restrictions

Sometimes we want to count binary strings satisfying particular conditions.

Example: Exactly Three Ones

How many eight-bit binary strings contain exactly three 1s?

We must choose three of the eight positions to contain 1.

The remaining positions contain 0.

The number of possibilities is:

C(8,3) = 8!/(3!5!)

= (8 × 7 × 6)/(3 × 2 × 1)

= 56

There are 56 eight-bit strings containing exactly three 1s.

General Formula

The number of binary strings of length n containing exactly r ones is:

C(n,r) = n!/[r!(n − r)!]

This is an important application of combinations in coding theory.

What Is Coding Theory?

Coding theory is the mathematical study of representing information so that it can be stored or transmitted reliably.

Digital communication systems are affected by noise and interference.

For example, a transmitted bit might change:

0 → 1

or:

1 → 0

Such changes are called bit errors.

Coding theory develops methods for:

• Detecting errors.

• Correcting errors.

• Representing information efficiently.

• Improving communication reliability.

Example: Sending a Message

Suppose a computer sends:

1011

During transmission, one bit changes.

The receiver obtains:

1001

Without additional information, the receiver may not know that an error occurred.

An error-detecting code adds extra information that can help identify problems.

Error Detection Using Parity Bits

A parity bit is an additional bit used to detect certain transmission errors.

Two common systems are:

• Even parity.

• Odd parity.

Even Parity

With even parity, the total number of 1s in the transmitted message, including the parity bit, must be even.

Example

Original data:

1011

There are three 1s.

Since three is odd, add a parity bit of 1.

Transmitted message:

10111

The total number of 1s is four, which is even.

Detecting an Error

Suppose the receiver obtains:

10011

This contains three 1s.

Because the total is odd, the receiver detects a parity error.

Important Limitation

A single parity bit detects any odd number of bit flips.

However, an even number of bit flips may go undetected.

For example, if two bits change, the total parity may remain correct.

Parity bits can detect certain errors but cannot generally identify which bit is incorrect.

Error Correction Through Repetition Codes

One simple error-correcting method is to repeat each bit.

For example:

0 → 000

1 → 111

A message containing:

101

would be encoded as:

111 000 111

Correcting a Single Error

Suppose:

111

is transmitted, but the receiver obtains:

101

Two bits are 1, and one bit is 0.

Using majority voting, the receiver interprets the message as:

111

representing the original bit 1.

Why This Works

The three-bit repetition code can correct one bit error in each three-bit block.

However, if two bits in the same block are corrupted, majority voting produces the wrong result.

Disadvantage

Repetition increases the number of transmitted bits.

Sending one information bit requires three transmitted bits.

The code rate is:

Code rate = Information bits / Transmitted bits

For this repetition code:

Code rate = 1/3

This means only one-third of the transmitted bits represent original information.

Hamming Distance

The Hamming distance between two binary strings of equal length is the number of positions in which they differ.

Example

Compare:

101101

100111

Position by position:

There are two differences.

Hamming distance = 2

Why Hamming Distance Matters

Hamming distance helps determine how many errors a code can detect or correct.

If the minimum Hamming distance between valid codewords is d:

• The code can detect up to d − 1 bit errors.

• The code can correct up to floor[(d − 1)/2] bit errors.

Here, floor means rounding down to the nearest integer.

Example

A code has minimum Hamming distance:

d = 3

It can detect up to:

3 − 1 = 2 errors

It can correct up to:

floor[(3 − 1)/2] = 1 error

These guarantees assume the received message is affected by no more than the stated number of errors.

Counting Possible Error Patterns

Combinatorics can be used to calculate how many error patterns are possible.

Suppose a transmitted message contains eight bits.

Exactly One Error

There are eight positions where the error could occur.

Number of patterns:

C(8,1) = 8

Exactly Two Errors

Choose two positions from eight:

C(8,2) = 8!/(2!6!)

= 28

Exactly Three Errors

C(8,3) = 8!/(3!5!)

= 56

General Formula

For an n-bit message with exactly r bit flips:

Number of error patterns = C(n,r)

This counting principle is important when designing error-correcting codes.

Probability of Transmission Errors

Suppose each transmitted bit has an independent probability p of being corrupted.

For a message containing n bits, the number of errors follows a binomial distribution under these assumptions.

X ~ B(n,p)

The probability of exactly r errors is:

P(X = r) = C(n,r) × pʳ × (1 − p)^(n−r)

Worked Example

An eight-bit message is transmitted.

Each bit has a 1% probability of being corrupted.

Find the probability that exactly one bit is corrupted.

Given:

n = 8

p = 0.01

r = 1

Substitute:

P(X = 1) = C(8,1) × 0.01 × 0.99⁷

= 8 × 0.01 × 0.99⁷

P(X = 1) ≈ 0.0746

There is approximately a 7.46% probability of exactly one bit error.

Probability of No Errors

P(X = 0) = 0.99⁸

≈ 0.9227

Therefore, the probability of at least one error is:

P(X ≥ 1) = 1 − 0.99⁸

≈ 0.0773

There is approximately a 7.73% probability that at least one bit is corrupted.

Introduction to Cryptography

Cryptography is the study of techniques used to protect information.

Cryptographic systems can provide:

• Confidentiality.

• Data integrity.

• Authentication.

• Verification of digital information.

Encryption transforms readable information into a form that cannot easily be understood without the appropriate key.

Important Terms

Plaintext: The original readable information.

Ciphertext: The encrypted information.

Encryption: The process of transforming plaintext into ciphertext.

Decryption: The process of recovering plaintext from ciphertext.

Key: Information used by an encryption or decryption algorithm.

Combinatorics and Password Security

Combinatorics helps calculate the number of possible passwords.

Suppose a password contains six characters.

Each character can be one of 26 lowercase English letters.

If repetition is allowed:

Number of passwords = 26⁶

= 308,915,776

There are more than 308 million possible passwords.

Including Numbers

Suppose each character can be:

• One of 26 lowercase letters.

• One of 10 digits.

There are:

26 + 10 = 36 possible characters.

For six characters:

36⁶ = 2,176,782,336

There are approximately 2.18 billion possible passwords.

Increasing Password Length

If the character set contains 36 symbols:

The number of possibilities increases exponentially with password length.

Important Limitation

These calculations assume every permitted password is possible.

Real users often choose predictable passwords, so attackers may not need to test every combination.

Password security also depends on factors such as password uniqueness, rate limiting, secure storage, and authentication methods.

Key Spaces in Cryptography

A key space is the set of all possible encryption keys.

If a key contains n independent binary digits, the number of possible keys is:

2ⁿ

Examples

A larger key space generally makes exhaustive key searching more difficult.

However, key length alone does not guarantee security.

The security of an encryption system also depends on the algorithm, implementation, key generation, and protection of the key.

Simple Substitution Ciphers

A substitution cipher replaces symbols with other symbols according to a rule.

One familiar example is the Caesar cipher.

Caesar Cipher

Each letter is shifted by a fixed number of positions in the alphabet.

For a shift of 3:

A → D

B → E

C → F

For example:

CAT → FDW

Mathematical Representation

Assign numbers to letters:

A = 0, B = 1, ..., Z = 25

Encryption can be represented as:

E(x) = (x + k) mod 26

where:

• x is the numerical value of the original letter.

• k is the shift.

• mod 26 means taking the remainder after division by 26.

Example

Encrypt the letter Y using a shift of 5.

Y = 24

E(24) = (24 + 5) mod 26

= 29 mod 26

= 3

3 corresponds to D.

Therefore:

Y → D

Limitations

The Caesar cipher has only 26 possible shifts, including the zero shift.

It is not secure for modern communication.

Its value is educational because it introduces modular arithmetic and encryption.

Permutations and Substitution Ciphers

Suppose a cipher replaces each of the 26 English letters with a unique letter.

How many possible substitution arrangements exist?

The first letter has 26 choices.

The second has 25 choices.

The third has 24 choices.

This continues until one choice remains.

Total arrangements:

26!

≈ 4.03 × 10²⁶

This is an enormous number.

However, simple substitution ciphers remain vulnerable to methods such as frequency analysis.

Why Frequency Analysis Works

Languages have characteristic letter frequencies.

For example, some letters appear more frequently than others in English text.

A substitution cipher preserves many statistical patterns in the original message.

An attacker can use these patterns to help identify the substitutions.

This demonstrates that a large number of possible keys does not automatically guarantee strong encryption.

Networks and Graph Theory

A network consists of objects connected by relationships.

Mathematically, many networks can be represented using graphs.

A graph contains:

• Vertices (nodes): Objects in the network.

• Edges: Connections between the objects.

Examples include:

• Computers connected by communication links.

• Cities connected by roads.

• People connected through social relationships.

• Airports connected by flights.

• Websites connected by hyperlinks.

Simple Network Diagram

Interpreting the Network

Each vertex may represent a computer.

Each edge may represent a communication connection.

A path between two vertices represents a possible route for information to travel.

Counting Edges in a Complete Network

A complete graph is a graph in which every pair of distinct vertices is connected by an edge.

Suppose a network contains n computers.

Every computer is directly connected to every other computer.

How many connections are required?

The number of edges is:

E = n(n − 1)/2

Why Divide by Two?

Each connection joins two computers.

Counting connections from each computer counts every edge twice.

Therefore, we divide by 2.

Worked Example

A complete network contains six computers.

E = 6(6 − 1)/2

= 6 × 5/2

E = 15

Fifteen connections are required.

Connection to Combinations

Each edge corresponds to choosing two distinct vertices.

Therefore:

E = C(n,2)

This demonstrates how graph theory and combinatorics are connected.

Directed and Undirected Networks

Undirected Networks

An undirected edge represents a connection that works in both directions.

For example:

A — B

may represent a two-way communication link.

Directed Networks

A directed edge represents a connection with a specified direction.

For example:

A → B

indicates a connection from A to B.

Directed networks are useful for representing:

• One-way roads.

• Webpage links.

• Information flow.

• Dependencies between tasks.

• Certain communication systems.

Counting Possible Directed Connections

For n vertices, if every ordered pair of distinct vertices can be connected:

Maximum directed edges = n(n − 1)

For five vertices:

5 × 4 = 20

This assumes no self-loops and at most one directed edge for each ordered pair.

Paths Through Networks

A path is a sequence of connected vertices.

Paths are important because information must travel through networks.

Example

Suppose a message can travel from A to D using:

A → B → D

or:

A → C → D

There are two possible routes.

If an additional route exists:

A → B → C → D

there are three routes.

Counting Paths

The number of possible paths depends on the network structure.

In some problems, the multiplication principle can be used.

Worked Example

A communication system has:

• 3 possible first-stage routes.

• 4 possible second-stage routes.

• 2 possible third-stage routes.

If every combination of choices produces a distinct valid route:

Total routes = 3 × 4 × 2

= 24

There are 24 possible routes.

Shortest-Path Problems

Many network problems involve finding the shortest or least expensive route between two vertices.

Edges may have weights representing:

• Distance.

• Time.

• Cost.

• Energy consumption.

• Communication delay.

A weighted graph is a graph in which edges have numerical values.

Example

Suppose the network has the following connections:

Find the shortest route from A to D.

Possible routes include:

A → B → D

Distance = 4 + 6 = 10 km

A → C → D

Distance = 7 + 3 = 10 km

A → B → C → D

Distance = 4 + 2 + 3 = 9 km

Shortest route = A → B → C → D

Total distance = 9 km

For larger networks, algorithms such as Dijkstra's algorithm can find shortest paths efficiently when edge weights are non-negative.

Probability in Computer Networks

Computer networks experience uncertain events such as:

• Transmission errors.

• Equipment failures.

• Packet loss.

• Communication delays.

• Temporary connection interruptions.

Probability helps engineers estimate the reliability of these systems.

Example: Independent Connection Failures

Suppose a network connection has a 2% probability of failing during a particular period.

Then:

P(connection works) = 0.98

If three independent connections must all work for communication to succeed:

P(all work) = 0.98³

≈ 0.9412

There is approximately a 94.12% probability that all three connections work.

The probability of at least one failure is:

P(at least one fails) = 1 − 0.98³

≈ 0.0588

There is approximately a 5.88% probability of at least one connection failure.

Network Redundancy

Redundancy means providing additional components or pathways so that a system can continue functioning if one part fails.

Suppose two independent network links connect the same devices.

Each link has a 10% probability of failing.

Communication fails only if both links fail.

Probability Both Links Fail

P(both fail) = 0.10 × 0.10

= 0.01

Probability Communication Remains Available

P(at least one works) = 1 − 0.01

= 0.99

The network has a 99% probability of remaining connected during the specified period.

Interpretation

Redundant connections can improve reliability.

However, the independence assumption is important.

If both links can fail because of the same power outage or physical damage, the actual reliability may be lower.

Reliability of Series and Parallel Networks

Two common reliability structures are series systems and parallel systems.

Series System

In a series system, every component must work.

If component reliabilities are independent:

R_series = R₁ × R₂ × ... × Rₙ

Example

Three components have reliabilities:

0.95, 0.90, and 0.98

Overall reliability:

R = 0.95 × 0.90 × 0.98

R = 0.8379

The system has an 83.79% probability of functioning.

Parallel System

In a parallel system, at least one component must work.

If failures are independent:

R_parallel = 1 − (1 − R₁)(1 − R₂)...(1 − Rₙ)

Example

Two independent components each have reliability 0.90.

R = 1 − (0.10 × 0.10)

R = 0.99

The system has a 99% probability of functioning.

This shows how probability and network structure can be combined to improve system design.

Probability and Randomized Algorithms

Some computer algorithms use random choices as part of their operation.

These are called randomized algorithms.

Randomness may help an algorithm:

• Select samples.

• Explore possible solutions.

• Avoid predictable behaviour.

• Estimate numerical quantities.

• Distribute workloads.

Example: Random Sampling

Suppose a computer must estimate the average value of a very large dataset.

Instead of processing every value, it may randomly select a sample.

The sample mean can provide an estimate of the population mean.

Larger representative samples generally produce more stable estimates.

Monte Carlo Algorithms

Monte Carlo algorithms use random sampling to estimate quantities or solve problems approximately.

For example, random points can be used to estimate the value of π.

Las Vegas Algorithms

Las Vegas algorithms use randomness but, when they return a result, that result is correct.

Their running time may vary.

This differs from Monte Carlo algorithms, which may return an approximate or occasionally incorrect result depending on the algorithm.

Counting Possible Network Configurations

Combinatorics can also be used to count possible network structures.

Suppose a simple undirected network contains four labelled vertices.

There are:

C(4,2) = 6

possible edges.

Each edge can either:

• Be present.

• Be absent.

Therefore, the total number of possible simple undirected graphs is:

2⁶ = 64

General Formula

For n labelled vertices, the number of possible edges is:

C(n,2) = n(n − 1)/2

Therefore:

Number of possible simple undirected graphs = 2^[n(n − 1)/2]

This assumes no self-loops and at most one edge between any pair of vertices.

Example

For five labelled vertices:

Possible edges:

5 × 4/2 = 10

Possible graphs:

2¹⁰

= 1,024

The number of possible network structures increases rapidly as the number of vertices increases.

Practical Application: Secure Communication

When someone sends information over the internet, several mathematical systems work together.

Coding Theory

Error-detecting and error-correcting codes help identify or repair corrupted information.

Cryptography

Encryption protects the confidentiality of transmitted information.

Authentication and integrity mechanisms help detect unauthorized modification or impersonation.

Network Theory

Routing algorithms determine how information travels between devices.

Probability

Probability models estimate transmission errors, connection failures, and system reliability.

Combinatorics

Counting principles help determine codeword possibilities, key spaces, and network configurations.

These mathematical ideas work together to support reliable and secure digital communication.

Practical Application: QR Codes

QR codes store information using patterns of dark and light modules.

The information is represented digitally.

Error-correction techniques allow many QR codes to remain readable even when some parts are damaged or obscured.

QR codes use Reed–Solomon error correction, a more advanced coding method based on finite-field mathematics.

Combinatorics and algebra help explain how additional information can be used to detect and correct errors.

Practical Application: Data Storage

Digital storage devices must preserve information despite possible errors.

Errors may arise from:

• Electrical interference.

• Physical damage.

• Ageing components.

• Manufacturing defects.

• Read and write failures.

Error-correcting codes add redundancy so that certain errors can be detected or corrected.

The design of these systems involves balancing:

• Storage capacity.

• Reliability.

• Processing speed.

• Error-correction capability.

More redundancy can improve reliability, but it also requires additional storage space.

Evaluating Mathematical Models

Mathematical models used in networks, coding, and cryptography depend on assumptions.

Important Questions

Are errors independent?

Transmission errors may occur in bursts rather than independently.

Are all outcomes equally likely?

Passwords and network failures may have highly unequal probabilities.

Are all connections equally reliable?

Some network links may be more vulnerable than others.

Does the model include shared failures?

Several components may fail because of a single event.

Are the mathematical methods appropriate?

A simple model may not capture all the details of a real system.

Is the security model realistic?

A large key space is not sufficient if the encryption algorithm or implementation is vulnerable.

Evaluating these assumptions is essential for interpreting mathematical results correctly.

Common Mistakes

Confusing permutations and combinations

Permutations consider order, while combinations do not.

Forgetting that repetition may be allowed

Password calculations depend on whether characters can repeat.

Assuming all passwords are equally likely

Human-generated passwords are often predictable.

Believing a large key space guarantees security

Security also depends on algorithms, implementations, and key management.

Confusing error detection with error correction

Detecting an error does not necessarily identify how to repair it.

Assuming parity bits detect every error

A single parity bit cannot detect every possible pattern of bit flips.

Calculating Hamming distance incorrectly

Only positions containing different symbols should be counted.

Assuming network failures are independent

Shared causes can produce simultaneous failures.

Confusing series and parallel reliability

Series systems require every component to work, while parallel systems require at least one functioning component.

Double-counting network edges

In an undirected network, each connection should be counted only once.

Assuming the shortest path is always the fastest

Distance, travel time, and communication delay may be different edge weights.

Ignoring the assumptions of probability models

A mathematically correct calculation can produce an unrealistic prediction if the assumptions are inappropriate.

Key Terms

• Combinatorics: The mathematical study of counting, arranging, and selecting objects.

• Addition Principle: A counting rule for mutually exclusive alternatives.

• Multiplication Principle: A counting rule for processes involving successive choices.

• Permutation: An arrangement in which order matters.

• Combination: A selection in which order does not matter.

• Binary Digit (Bit): A digit with value 0 or 1.

• Binary String: A sequence of binary digits.

• Coding Theory: The mathematical study of representing information for efficient and reliable storage or transmission.

• Codeword: A valid encoded sequence of symbols.

• Error Detection: Identifying whether transmitted or stored information has been corrupted.

• Error Correction: Recovering the original information from certain corrupted messages.

• Parity Bit: An additional bit used to check the parity of a binary message.

• Even Parity: A coding rule requiring an even total number of 1s.

• Repetition Code: An error-correcting code that repeats information symbols.

• Code Rate: The ratio of original information symbols to total transmitted symbols.

• Hamming Distance: The number of positions in which two equal-length strings differ.

• Minimum Distance: The smallest Hamming distance between distinct valid codewords.

• Bit Error Rate: The proportion or probability of transmitted bits that are received incorrectly.

• Cryptography: The study of techniques for protecting information.

• Encryption: Transforming readable information into ciphertext.

• Decryption: Recovering plaintext from ciphertext.

• Plaintext: Information before encryption.

• Ciphertext: Encrypted information.

• Encryption Key: Information used by an encryption algorithm.

• Key Space: The set of all possible encryption keys.

• Substitution Cipher: A cipher that replaces symbols according to a substitution rule.

• Caesar Cipher: A substitution cipher based on shifting letters through the alphabet.

• Modular Arithmetic: Arithmetic involving remainders after division by a fixed number.

• Frequency Analysis: A method of analysing symbol frequencies to investigate encrypted messages.

• Network: A collection of objects connected by relationships.

• Graph: A mathematical structure consisting of vertices and edges.

• Vertex: A node representing an object in a network.

• Edge: A connection between two vertices.

• Directed Graph: A graph whose edges have directions.

• Undirected Graph: A graph whose edges have no direction.

• Weighted Graph: A graph whose edges have numerical values.

• Complete Graph: A graph in which every pair of distinct vertices is connected.

• Path: A sequence of connected vertices.

• Shortest Path: A route between vertices with the smallest total weight.

• Network Reliability: The probability that a network performs its required function.

• Redundancy: Additional components or connections included to improve reliability.

• Series System: A system that works only when every required component works.

• Parallel System: A system that works when at least one of several alternative components works.

• Randomized Algorithm: An algorithm that uses random choices during execution.

• Monte Carlo Algorithm: A randomized algorithm that produces estimates or results with a specified probability of error.

• Las Vegas Algorithm: A randomized algorithm that always returns a correct result when it terminates, although its running time may vary.

Key Takeaways

• Combinatorics plays an important role in coding theory, cryptography, and computer networks.

• The multiplication principle can be used to count binary strings, passwords, and possible routes.

• A binary string of length n has 2ⁿ possible values.

• Combinations can count binary strings containing a specified number of ones.

• Coding theory develops methods for detecting and correcting errors in digital information.

• Parity bits can detect odd numbers of bit flips but cannot detect every possible error pattern.

• Repetition codes use redundancy to correct certain errors.

• Hamming distance measures the number of differing positions between equal-length strings.

• A code's minimum Hamming distance determines its guaranteed error-detection and correction capabilities.

• Binomial probability can model independent bit errors.

• Cryptography uses mathematical methods to protect digital information.

• Password and encryption key spaces can be counted using combinatorial principles.

• Longer passwords and larger key spaces generally increase the number of possibilities an attacker must consider.

• A large key space alone does not guarantee cryptographic security.

• Networks can be represented using graphs consisting of vertices and edges.

• A complete undirected graph with n vertices has n(n − 1)/2 edges.

• Weighted graphs can model distances, costs, and communication delays.

• Shortest-path algorithms help identify efficient routes through networks.

• Probability can estimate the reliability of network components and communication links.

• Redundancy can improve network reliability by providing alternative paths or components.

• Randomized algorithms use probability to solve or approximate computational problems.

• Coding theory, cryptography, network theory, and probability work together in modern communication systems.

Check Your Understanding

Recall and Understanding

1. Explain how combinatorics is used in coding theory and cryptography.

2. Define a bit and a binary string.

3. Explain the purpose of parity bits in error detection.

4. Define Hamming distance and explain why it is useful.

5. Describe the difference between a directed graph and an undirected graph.

Application

6. How many different binary strings of length 10 are possible?

7. How many eight-bit binary strings contain exactly four ones?

8. A password contains seven characters, each selected from 26 lowercase letters and 10 digits. If repetition is allowed, how many passwords are possible?

9. Calculate the Hamming distance between 10110110 and 10011100.

10. A complete undirected network contains eight computers. How many direct connections are required?

Analysis and Challenge

11. A 12-bit message is transmitted, and each bit has an independent 2% probability of error. Calculate the probability that exactly two bits are corrupted.

12. A communication system uses three independent links in series, each with 95% reliability. Calculate the overall reliability. Then determine the reliability if the three links instead form a parallel system where any one functioning link is sufficient.

13. A substitution cipher uses a permutation of the 26-letter English alphabet. Explain why the large number of possible substitutions does not guarantee strong encryption.

14. A network contains five labelled vertices. Calculate the number of possible simple undirected graphs. Explain the counting principle used.

15. Design a small network containing at least five vertices and seven edges. Assign weights to the edges, identify the shortest path between two selected vertices, and explain how the network could be made more reliable.

Final Summary

Networks, coding theory, and cryptography demonstrate how combinatorics and probability are applied in modern computer science.

Combinatorics provides methods for counting possible messages, passwords, encryption keys, error patterns, and network configurations.

Coding theory uses mathematical redundancy to detect and correct errors in digital communication.

Cryptography uses counting principles, modular arithmetic, and other mathematical structures to protect information.

Graph theory provides a framework for representing networks and analysing connections, paths, and routes.

Probability helps estimate transmission errors, component failures, and overall network reliability.

Together, these mathematical ideas support secure communication, reliable data storage, efficient routing, and modern digital technology.

The central principle is that counting possible outcomes, analysing probabilities, and understanding mathematical structures allow us to design more reliable and secure information systems.