Module 2
PROGRAMMING FUNDAMENTALS
Module Lecturer: ATHULYA
Topics
1. Algorithm & Data structures
2. Selection and control structures
3. Arrays and Strings
4. Functions
5. Files Handling
Algorithm
• The word Algorithm means ” A set of finite rules or instructions to be
followed in calculations or other problem-solving operations ”
Or” A procedure for solving a mathematical problem in a finite number
of steps that frequently involves recursive operations”.
• Itis important to keep in mind that an algorithm is not the same as
a program or code. It is the logic or plan for solving a problem
represented as a simple step-by-step description. Code is the
implementation of the algorithm in a specific programming language
(like C++ or Python), while a program is an implementation of code
that instructs a computer on how to execute an algorithm and perform a
task.
From data a point of view, following are some important
categories of algorithms
• Search- Algorithm search an item in a datastructure
• Sort-Algorithm to sort items in a certain order
• Insert-Algorithm to insert item in a datastructure
• Update -Algorithm to update an existing item in a data
structure
• Delete-Algorithm to delete an existing item from a data
structure
Characteristics of an Algorithm
• Not all procedures can be called an algorithm. An algorithm should have the
below mentioned characteristics-
• Unambiguous - algorithm should be clear and unambiguous: each of its
steps (or phases), and their input/outputs should be clear and must be lead
to only one meaning.
• Input-an algorithm should have 0 or more well defined inputs
• Output-an algorithm should have I or more well defined outputs, and
should match the desired output.
• Finiteness-algorithms must terminate after a finite number of steps.
• Feasibility-should be feasible with the available resources
• Independent - an algorithm should have step-by-step directions which
should be independent of any programming code
• Consider for example an algorithm that calculates the square of a given number.
• Input: the input data is a single-digit number (e.g., 5).
• Transformation/processing: the algorithm takes the input (number 5) and performs
the specific operation (i.e., multiplies the number by itself).
• Output: the result of the calculation is the square of the input number, which, in this case,
would be 25 (since 5 * 5 = 25).
• We could express this as an algorithm in the following way:
• Algorithm: Calculate the square of a number
1. Start.
2. Input the number (N) whose square you want to find.
3. Multiply the number (N) by itself.
4. Store the result of the multiplication in a variable (result).
5. Output the value of the variable (result), which represents the square of the input number.
6. End.
• An algorithm represents the thinking process for solving a problem in an abstract yet
precise way, rather than the answer itself.
#include <stdio.h>
int main() {
int n = 5;
int result = n * n;
printf("The square of %d is %d", n, result);
return 0;
}
Compute the average of three numbers
• Step 1:Start
• Step 2:Declare variables num1,num2,num3 and
average(num1,num2 and num3 holds the value of three
numbers)
• Step 3:Read values of num1,num2 and num3
• Step 4: Find the average using the formula : Average =
(num1+num2+num3)/3
• Step 5:Display average
• Step 6:End
#include <stdio.h>
int main() {
// Step 2: Declare variables
float num1, num2, num3, average;
// Step 3: Read values of num1, num2, and num3
printf("Enter three numbers: ");
scanf("%f %f %f", &num1, &num2, &num3);
// Step 4: Calculate average
average = (num1 + num2 + num3) / 3;
// Step 5: Display average
printf("Average of %f, %f, and %f is: %f\n", num1, num2, num3,
average);
return 0;
}
Modification
Enter 3 numbers :25
24
26
Average = 25.592
start
Read
num1,num2,
num3d
Average=
(Num1+num2+num3)/3
Display
average
End
#include <stdio.h>
int main() {
int num;
// Prompt user to enter a number
printf("Enter an integer: ");
scanf("%d", &num);
// Check if the number is even or odd
if (num % 2 == 0) {
printf("%d is even.\n", num);
} else {
printf("%d is odd.\n", num);
}
return 0;
}
#include <stdio.h> } else {
int main() { if (num2 > num3) {
// Step 2: Declare variables printf("num2 is the
largest.\n");
float num1, num2, num3;
} else {
// Step 3: Input num1, num2, and
num3 printf("num3 is the
largest.\n");
printf("Enter three numbers: ");
}
scanf("%f %f %f", &num1, &num2,
&num3); }
// Step 4: Check and display the
largest number
// Step 6: End
if (num1 > num2 && num1 >
num3) { return 0;
printf("num1 is the largest.\n"); }
Asymptotic Analysis
• The efficiency of an algorithm depends on the amount of time,
storage and other resources required to execute the algorithm. The
efficiency is measured with the help of asymptotic notations.
• An algorithm may not have the same performance for different
types of inputs. With the increase in the input size, the performance
will change.
• The study of change in performance of the algorithm with the
change in the order of the input size is defined as asymptotic
analysis.
Asymptotic Notations
• Asymptotic notations are the mathematical notations used to
describe the running time of an algorithm when the input tends
towards a particular value or a limiting value.
• For example: In bubble sort, when the input array is already sorted,
the time taken by the algorithm is linear i.e. the best case.
• But, when
the input array is in reverse condition, the algorithm takes
the maximum time (quadratic) to sort the elements i.e. the worst
case.
• When the input array is neither sorted nor in reverse order,
then it takes average time. These durations are denoted using
asymptotic notations.
• There are mainly three asymptotic notations:
• Big-O notation
• Omega notation
• Theta notation
Big-O Notation (O-notation)
• Big-O notation represents the upper bound of the running time of
an algorithm. Thus, it gives the worst-case complexity of an
algorithm.
cg(n)
f(n)=O(g(n))
Big-O gives the upper bound of a function
O(g(n)) = { f(n): there exist positive constants c and
n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
• The above expression can be described as a function f(n) belongs to
the set O(g(n)) if there exists a positive constant c such that it lies
between 0 and cg(n), for sufficiently large n.
• For any value of n, the running time of an algorithm does not cross the
time provided by O(g(n)).
• Since it gives the worst-case running time of an algorithm, it is widely
used to analyze an algorithm as we are always interested in the worst-
case scenario.
Omega Notation (Ω-notation)
• Omega notation represents the lower bound of the running time of an
algorithm. Thus, it provides the best case complexity of an algorithm.
f(n)=(g(n)n
Omega gives the lower bound of a function
• Ω(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
• The above expression can be described as a function f(n) belongs to the
set Ω(g(n)) if there exists a positive constant c such that it lies above
cg(n), for sufficiently large n.
• For any value of n, the minimum time required by the algorithm is given
by Omega Ω(g(n)).
Theta Notation (Θ-notation)
C2g(n)
f(n)=(g(n))
Theta bounds the function within constants factors
• For a function g(n), Θ(g(n)) is given by the relation:
• Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0
• such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }
• The above expression can be described as a function f(n) belongs
to the set Θ(g(n)) if there exist positive constants c1 and c2 such
that it can be sandwiched between c1g(n) and c2g(n), for
sufficiently large n.
• If a function f(n) lies anywhere in between c1g(n) and c2g(n) for
all n ≥ n0, then f(n) is said to be asymptotically tight bound.
Greedy Algorithm
•A greedy algorithm is an approach for solving a problem by
selecting the best option available at the moment. It doesn't worry
whether the current best result will bring the overall optimal result.
• The algorithm never reverses the earlier decision even if the choice
is wrong. It works in a top-down approach.
• This algorithm may not produce the best result for all the problems.
It's because it always goes for the local best choice to produce the
global best result.
Divide and Conquer Algorithm
•A divide and conquer algorithm is a strategy of solving a
large problem by
• breaking the problem into smaller sub-problems
• solving the sub-problems, and
• combining them to get the desired output.
How Divide and Conquer Algorithms Work?
• Here are the steps involved:
• Divide: Divide the given problem into sub-problems using
recursion.
• Conquer:Solve the smaller sub-problems recursively. If the
subproblem is small enough, then solve it directly.
• Combine: Combine the solutions of the sub-problems that are part
of the recursive process to solve the actual problem.
example.
Here, sort an array using the divide and conquer approach (ie. merge
sort).
Again, divide each subpart recursively into two halves until
you get individual elements.
3. Now, combine the individual elements in a sorted manner.
Here, conquer and combine steps go side by side.
• Thefollowing computer algorithms are based on divide-
and-conquer programming approach-
• Merge Sort
• Quick Sort
• Binary Search
• Strassen’s Matrix Multiplication
• Closer pair(points)
Introduction to Data Structures
• Since the invention of computers, people have been using the term
"Data" to refer to Computer Information, either transmitted or
stored. However, there is data that exists in order types as well.
• Data can be numbers or texts written on a piece of paper, in the form
of bits and bytes stored inside the memory of electronic devices, or
facts stored within a person's mind. As the world started modernizing,
this data became a significant aspect of everyone's day-to-day life, and
various implementations allowed them to store it differently.
• Data is a collection of facts and figures or a set of values or values of a
specific format that refers to a single set of item values. The data items
are then classified into sub-items, which is the group of items that are
not known as the simple primary form of the item.
Let us consider an example where an employee name can be broken down into
three sub-items: First, Middle, and Last. However, an ID assigned to an employee
will generally be considered a single item.
What is Data Structure?
• Data Structure is a branch of Computer Science. The study of data
structure allows us to understand the organization of data and the
management of the data flow in order to increase the efficiency of any
process or program.
• Data Structure is a particular way of storing and organizing data in the
memory of the computer so that these data can easily be retrieved and
efficiently utilized in the future when required. The data can be managed
in various ways, like the logical or mathematical model for a specific
organization of data is known as a data structure.
The scope of a particular data model depends on two factors:
1. First, it must be loaded enough into the structure to reflect the definite
correlation of the data with a real-world object.
[Link], the formation should be so straightforward that one can adapt to
process the data efficiently whenever necessary.
• Some examples of Data Structures are Arrays, Linked Lists, Stack, Queue,
Trees, etc. Data Structures are widely used in almost every aspect of
Computer Science, i.e., Compiler Design, Operating Systems, Graphics,
Artificial Intelligence, and many more.
• Data Structures are the main part of many Computer Science Algorithms
as they allow the programmers to manage the data in an effective way. It
plays a crucial role in improving the performance of a program or
software, as the main objective of the software is to store and retrieve the
user's data as fast as possible.
Why should we learn Data Structures?
[Link]
Structures and Algorithms are two of the key aspects of
Computer Science.
[Link] Structures allow us to organize and store data, whereas
Algorithms allow us to process that data meaningfully.
[Link] Data Structures and Algorithms will help us become
better Programmers.
[Link] will be able to write code that is more effective and reliable.
[Link] will also be able to solve problems more quickly and
efficiently.
Basic Terminologies related to Data Structures
• Data Structures are the building blocks of any software or program. Selecting the
suitable data structure for a program is an extremely challenging task for a
programmer.
• The following are some fundamental terminologies used whenever the data
structures are involved:
[Link]: We can define data as an elementary value or a collection of values. For
example, the Employee's name and ID are the data related to the Employee.
[Link] Items: A Single unit of value is known as Data Item.
[Link] Items: Data Items that have subordinate data items are known as Group
Items. For example, an employee's name can have a first, middle, and last name.
[Link] Items: Data Items that are unable to divide into sub-items are known
as Elementary Items. For example, the ID of an Employee.
[Link] and Attribute: A class of certain objects is represented by an Entity. It
consists of different Attributes. Each Attribute symbolizes the specific property of
that Entity.
Types of Data Structure
• Basically, data structures are divided into two categories:
• Linear data structure
• Non-linear data structure
non
Primitive Data Structures
[Link] Data Structures are the data structures
consisting of the numbers and the characters that come in-
built into programs.
[Link] data structures can be manipulated or operated directly
by machine-level instructions.
[Link] data types like Integer, Float, Character,
and Boolean come under the Primitive Data Structures.
[Link] data types are also called Simple data types, as they
contain characters that can't be divided further
Non-Primitive Data Structures
[Link]-Primitive Data Structures are those data structures
derived from Primitive Data Structures.
[Link] structures can't be manipulated or operated directly
by machine-level instructions.
[Link] focus of these data structures is on forming a set of data
elements that is either homogeneous (same data type)
or heterogeneous (different data types).
[Link] on the structure and arrangement of data, we can divide
these data structures into two sub-categories -
1. Linear Data Structures
2. Non-Linear Data Structures
Linear data structures
• Inlinear data structures, the elements are arranged in
sequence one after the other. Since elements are arranged in
particular order, they are easy to implement.
• However, when the complexity of the program increases,
the linear data structures might not be the best choice
because of operational complexities.
Popular linear data structures are:
• 1. Array Data Structure
• In an array, elements in memory are arranged in continuous memory.
All the elements of an array are of the same type. And, the type of
elements that can be stored in the form of arrays is determined by the
programming language.
Arrays can be classified into different types:
[Link]-Dimensional Array: An Array with only one row of data
elements is known as a One-Dimensional Array. It is stored in
ascending storage location.
[Link]-Dimensional Array: An Array consisting of multiple
rows and columns of data elements is called a Two-Dimensional
Array. It is also known as a Matrix.
[Link] Array: We can define Multidimensional
Array as an Array of Arrays. Multidimensional Arrays are not
bounded to two indices or two dimensions as they can include as
many indices are per the need.
Some Applications of Array:
[Link] can store a list of data elements belonging to the same
data type.
[Link] acts as an auxiliary storage for other data
structures.
[Link] array also helps store data elements of a binary tree of
the fixed count.
[Link] also acts as a storage of matrices.
Linked List Data Structure
• In linked list data structure, data elements are connected
through a series of nodes. And, each node contains the data
items and address to the next node.
Linked Lists can be classified into different types:
[Link] Linked List: A Singly Linked List is the most common
type of Linked List. Each node has data and a pointer field
containing an address to the next node.
[Link] Linked List: A Doubly Linked List consists of an
information field and two pointer fields. The information field
contains the data. The first pointer field contains an address of the
previous node, whereas another pointer field contains a reference
to the next node. Thus, we can go in both directions (backward as
well as forward).
[Link] Linked List: The Circular Linked List is similar to the
Singly Linked List. The only key difference is that the last node
contains the address of the first node, forming a circular loop in the
Circular Linked List.
Stack Data Structure
• In stack data structure, elements are stored in the LIFO
principle. That is, the last element stored in a stack will be
removed first.
• It works just like a pile of plates where the last plate kept on the
pile will be removed first.
Queue Data Structure
• Unlike stack, the queue data structure works in the FIFO
principle where first element stored in the queue will be
removed first.
• It works just like a queue of people in the ticket counter where
first person on the queue will get the ticket first.
Graph Data Structure
• Ingraph data structure, each node is called vertex and
each vertex is connected to other vertices through edges.
Trees Data Structure
• Similarto a graph, a tree is also a collection of vertices and
edges. However, in tree data structure, there can only be one
edge between two vertices.
