Scribd
Upload
9 views

AMT-2a. Functions in Computer Science

Uploaded by

Manish kumawat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views

AMT-2a. Functions in Computer Science

Uploaded by

Manish kumawat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Functions in Computer Science and Discrete

Mathematics

1 Introduction
In discrete mathematics, functions play a crucial role in various aspects of com-
puter science. A function in discrete math is a mapping from a set of inputs
(called the domain) to a set of possible outputs (called the codomain). Func-
tions are essential because they formalize the relationships between data, which
is key for algorithms, computation, and problem-solving in computer science.

2 Important Functions in Computer Science


2.1 Boolean Functions
ˆ Definition: A Boolean function is a function that maps input values from
{0, 1} to an output of either 0 or 1.

ˆ Importance: Boolean functions are fundamental in designing digital cir-


cuits, computer logic, and truth tables. Each logical operation (AND, OR,
NOT, etc.) is represented as a Boolean function.
ˆ Example:
f (x, y) = x ∧ y
returns true if both x and y are true.

2.2 Hash Functions


ˆ Definition: A hash function maps data of arbitrary size to fixed-size
values (called hash codes or hash values).
ˆ Importance: Hash functions are crucial in data storage, retrieval, and
security. They are used in hash tables for fast lookups and cryptographic
applications.
ˆ Example: Hash functions in hash tables map keys to indices in an array
for efficient data retrieval.

1
2.3 Growth of Functions (Asymptotic Notation)
ˆ Definition: Functions that describe how the running time of an algorithm
grows as the input size increases. Common notations include Big O (O),
Big Omega (Ω), and Big Theta (Θ).
ˆ Importance: These functions are used to categorize algorithms based on
their efficiency and scalability.
ˆ Example: Bubble sort has O(n2 ) time complexity, and binary search has
O(log n).

2.4 Injective, Surjective, and Bijective Functions


ˆ Definition:
– Injective (One-to-One): A function where each element in the
domain maps to a unique element in the codomain.
– Surjective (Onto): A function where every element in the codomain
has a corresponding element in the domain.
– Bijective: A function that is both injective and surjective (i.e., a
one-to-one correspondence).
ˆ Importance: These functions are key in ensuring data integrity, invert-
ibility, and database design.
ˆ Example: Bijective functions are essential for reversible algorithms and
cryptographic systems.

2.5 Recursive Functions


ˆ Definition: A function that calls itself in its definition, typically with a
base case and a recursive step.
ˆ Importance: Recursive functions are fundamental in divide-and-conquer
algorithms like quicksort and mergesort, as well as in problem-solving.
ˆ Example: The factorial function:
f (n) = n × f (n − 1), f (0) = 1

2.6 Floor and Ceiling Functions


ˆ Definition: The floor function maps a real number to the greatest integer
less than or equal to it, while the ceiling function maps it to the smallest
integer greater than or equal to it.
ˆ Importance: These functions are used in rounding operations, memory
allocation, and discrete calculations.
ˆ Example:
floor(4.7) = 4, ceiling(4.7) = 5

2
2.7 Characteristic Functions
ˆ Definition: A characteristic function of a set A returns 1 if the element
belongs to A, and 0 otherwise.

ˆ Importance: These functions are used in set theory, database queries,


and decision-making algorithms.
ˆ Example: For a set A = {1, 3, 5}, the characteristic function χA (x) is 1
if x ∈ A and 0 if x ∈
/ A.

2.8 Identity Function


ˆ Definition: A function that returns its input unchanged.

ˆ Importance: Identity functions are used in recursive algorithms, func-


tional programming, and modeling.
ˆ Example: f (x) = x.

2.9 Modular Arithmetic Functions


ˆ Definition: Functions that return the remainder of a division operation,
commonly written as a mod m.
ˆ Importance: These functions are essential in cryptography, number the-
ory, and hashing algorithms.

ˆ Example:
f (a, m) = a mod m, f (17, 5) = 2

2.10 Exponential and Logarithmic Functions


ˆ Definition:

– An exponential function grows by constant multiplicative factors.


– A logarithmic function is the inverse of the exponential function.
ˆ Importance: These functions are crucial in algorithm complexity, such
as in exponential time complexity or logarithmic search algorithms.

ˆ Example:
2n (exponential), log2 n (logarithmic)

3
3 Summary
Functions in discrete mathematics are the foundation for various applications
in computer science. They provide the basis for data structures, algorithms,
logic design, cryptography, complexity analysis, and much more. Understand-
ing functions and their properties allows computer scientists to design efficient
algorithms and systems for a wide range of computational tasks.

You might also like