Week 1

Topic: Introduction to C Programming and Basic Concepts

S. Topics to be covered
No.
1. Identify the components of a basic C program.
2. Define what an algorithm is in the context of C programming.
3. Parts of a computer system and how they interact in the context of C programming.
4. Concept of a high-level language being translated by a compiler into a machine language
program.

An all-purpose programming language, known as C, was developed by Dennis Ritchie at the Bell Laboratories in
1972. Since then, this language is still significantly popular. The primary factor contributing to its widespread
adoption is its status as a foundational language within the realm of computer science.
The C programming language is closely linked to the UNIX operating system due to its original purpose of being
developed for the task of developing Unix. There are multiple benefits of learning to program in C. It is widely
recognized as one of the most extensively used programming languages globally. Possessing knowledge of C
facilitates the acquisition of proficiency in other widely used programming languages, like Java, Python, C++, C#,
and others, due to the same syntax. In comparison to programming languages like Java and Python, C exhibits a
high level of computational efficiency. C exhibits remarkable versatility, as it may be employed in a wide range of
1
 applications and technology. In order to compose C code, two things are required. A text editor such as Notepad is
utilized. And a compiler, such as GCC, is utilized to convert C code into a suitable programming language for
computer comprehension. There exists a wide range of text editors and compilers available for selection. For this
session we will be using Turbo C.

The C Quickstart:

To generate an initial C program:

Navigate to the editor and select the option "File > New."

Save it as firstprg.c, navigate to the "File" menu and select "Save File as".
The file named " firstprg.c" will have the lines of code as written in Program 1.

As a matter of fact, the documentation part is the initial section of the C programme. The documentation section
comprises of a series of line comments that include the program's name, creator’s name, and other pertinent
information that the programmer intends to utilise in the future. Comments may be inserted anywhere inside a
program, provided they are positioned within the delimiters /* and */ for multiple lines and // for a single line
comment. Comments are beneficial for identifying the main characteristics of the program or elucidating the
fundamental reasoning behind different program features. A sample program to print a message on the screen can
be written as:

2
 Program 1:
// Program to print Hello Everyone
#include <stdio.h>
1. int main()
2.
3. {
4. printf("Hello Everyone!");
5. return 0;
6. }

To enhance understanding, let us understand it line by line:

Line 1: The header file library # include <stdio.h> is included in line 1 to facilitate the manipulation of input and
output functions, including the printf() function mentioned in line 4. To enhance the functioning of C applications,
header files are utilized.

Line 2: An empty line. In C, white space is disregarded. However, it is used to enhance the readability of the code.
Line 3: Another inherent component of a C program is the main() function. This is referred to as a function. Any
code enclosed within curly brackets will be executed.

Line 4: The method printf() is utilized to display or print text on the screen. In this particular instance, the output
will be "Hello World!"
3
 It should be noted that every C statement must be terminated with a semicolon.
Please be advised that the body of the int main() function can alternatively be expressed as follows:

Program 2:

int main(){printf("Hello World!");return 0;}

It is important to note that the compiler does not parse white spaces. As can be seen on Program 2, even this code
works fine. Nevertheless, using many lines enhances the readability of the code.
Line 5: The main() method concludes with a return value of 0.
To ensure the proper termination of the main function, it is imperative to include the closing curly bracket at line 6.
Statements and Program:
A computer program can be defined as a collection of procedural instructions that are intended to be executed by a
computer. Within a programming language, the programming instructions are commonly referred to as statements.
The subsequent statement provides instructions to the compiler to display the text "Hello World" on the screen. For
ex
printf("Hello World!");
It is imperative to conclude the statement with a semicolon. Failing to include the semicolon (;) will result in an
error, the program will not run then.
For example printf("Hello World!") will give an error “anticipated ';' preceding ‘return'”.
Multiple statements

4
 The majority of C programs consist of several statements. The execution of the statements occurs sequentially,
following the same sequence in which they are recorded. For example
Invoke the function printf("Hello World!"); printf("Have a good day!"); and return 0;

They will be executed in the same sequence they are written. Before starting with the building of programs a very
integral part of programming is to be discussed that is algorithm. An algorithm is a defined collection of rules that
must be adhered to while resolving a specifically defined problem. It is an organized sequence of instructions
executed in a specific order to solve a problem or accomplish a task. An algorithm contains a logical component,
which defines the knowledge to be employed in problem-solving, and a control component, which establishes the
problem-solving principles via which that information is applied. The logical component of an algorithm establishes
its meaning, while the control component solely impacts its efficiency.

It gives Procedural guidelines for addressing a problem or executing a specific task. Within the field of computer
science, algorithms serve a broad spectrum of functions, encompassing basic mathematical operations as well as
complex data processing.

Key characteristics of the algorithm

Inputs: Algorithms need inputs that are quantifiable and may be expressed as numerical values or data.
Output: The algorithm is expected to generate some output. It may arise as a result of a problem or as a solution
specifically developed to effectively address it.

Clarity: Algorithms must be carefully specified, employing unequivocal instructions that a computer or other system
5
 can unambiguously execute.

Finiteness: The method necessitates a finite number of steps. Terminal exit refers to the termination of a program
following the execution of a specific amount of commands.

It is imperative that the algorithm possesses validity. Essentially, the algorithm should be capable of efficiently
generating a solution to the problem it is intended to address within a reasonable timeframe.
Effectiveness refers to the ability of an algorithm to efficiently generate a solution to the problem it is intended to
address within a given timeframe.

Generality: An algorithm must possess high generality, indicating its ability to be used to a broad spectrum of issues
rather than being limited to a single problem.

Having provided an algorithm for a problem and assuming it to be correct, is not feasible. A crucial task is to
ascertain the number of resources, such as time or space, that the algorithm will need. A problem-solving algorithm
that takes a year to complete is hardly practical. Similarly, a method that requires thousands of gigabytes of primary
memory finds little or no utility on most computers. Moreover, highly proficient programmers who possess the
ability to build efficient code are more in demand. This is because comprehending the performance of an algorithm
might enable the software to go beyond its originally planned usability.

The performance of an algorithm is measured on two parameters. Time and space. For comprehending the time
complexity suppose there is piece of code

6
 Program 3: Algorithm 1:
int main()
1. Start (main function)
{
2. Print Hello!
printf("Hello!”);
return 0; 3. Return (back to main function)
}

The output of this code will be hello printed on screen once.

Another piece of code which uses a loop (a concept which we will discuss in upcoming sessions) prints hello say 10
times.

Program 4: Algorithm 2:
int main()
1. Start (main function)
{
int x; 2. Input the number of times Hello has to
printf("Enter the value of x: "); be printed in variable x.
scanf(“%d”,&x);
for(int i=0;i<x;i++) 3. Start a loop to print it x times
{ 4. Print Hello!
printf("Hello!");
} 5. Return (back to main function)
return 0;
}

7
 Now comparing the 2 codes. Code 1 prints hello 1 time and code 2 prints it 10 times or say x times.
where x is the number entered by the user and then stops the execution.
Executing the code using a C compiler will result in the following statement: "The code is executed in 0.5 seconds."
Contrary to often held beliefs, this phenomenon is not a matter of time complexity. It might also happen that when
the same code gets executed 1000 times the message you get is "The code is executed in 0.2 seconds." So, the factual
time required by the code to get executed is machine dependent. It depends upon the processor being used and it
also considers network load if your machine is on a Local Area Network or a Wide Area Network.
Specifically, time-based complexity refers to the duration needed for an algorithm or program to complete its
execution.

Time complexity refers to how the number of operations required by an algorithm scales with the size of the input
data, usually expressed in big O notation. It's a theoretical measure and doesn't reflect the actual time an algorithm
takes to execute, which can vary based on many factors such as the speed of the processor, the programming
language used, and system architecture. Time complexity provides a way to predict the rate at which runtime will
increase as the input grows, helping to assess the efficiency of an algorithm in a hardware-independent manner.let
us take one more example for better understanding. Suppose there is only one copy of a reference book in the library
and in a class of 100 students one student has got that issued. So if the order is denoted by Big Oh (O) the complexity
of finding this book will be O(n) if the librarian is searching for it asking each student individually where n=100 in
this example. It will be O(n2) if he asks one student and on the students refusal asks him about the remaining 99

8
 students. It will be O(log n) if he divides the class into two groups of fifty students each and them enquires from
each group. Then further divides into two halves and keep on enquiring till he finds the book.

Similar to this in an algorithm also it is not the actual time of code execution. It is actually how many times each
statement executes. So as per our previous example if Hello is printed only once then complexity is O(1). And if its
printed 10 times the time complexity will be O(10). But in both the cases the auxillary space that is occupied is O(1).

And if the code modified to

Program 5: Algorithm 3:
#include <stdio.h>
a. Include header/library files
#include <math.h>
void main() 1. Start (main function)
{
2. Take number of times Hello has to be printed (here
int i, no = 10; no=10)
for (i = 2; i < = no; i=pow(i,2)) {
printf("Hello !"); 3. Start a loop that runs 10 to the power 2
} 4. Print Hello!
}
5. Return

The time complexity of this algorithm is O(log(log n)), and it requires O(1) auxiliary space. To determine the time
complexity, consider the following: on a single 32-bit processor that performs sequential execution, each arithmetic
and logical operation, as well as assignment operations and return statements, take 1 unit of time. Therefore, a basic

9
 Program 6:

#include <stdio.h>
int main()
{

int a = 15, b = 20, c ;

c = a+b;
return c;

operation such as adding two numbers would consume 2 units of time—1 unit for the arithmetic operation and
another unit for the return statement.

The total cost to complete sum is = 1 + 1 = 2. Hence, Time Complexity (TC) = O(2) which is equivalent to O(1),
since 2 is a constant value. And the auxiliary space occupied is O(1).

Another program, which adds two matrices together, the complexity of the matrix will be

Matrix of size n*n =>TC= x.n2 + y.n + z

Since TC is in order of n2, hence Time Complexity = O(n2). Here the code is:

10
 Program 7:

#include <stdio.h>
int main()
{
int x = 3, y = 3, sum;
int i,j;
int matrix[3][3] =
{
{ 11, 12, 13 }, { 14, 15, 16 }, { 17, 18, 19 }
};
for (i = 0; i < x; i++)
{
for (j = 0; j < y; j++)
{
sum = sum + matrix[i][j];
}
}
printf ("%d", sum);
return 0;
}
Output : 135

11
 Time Complexity: O(i*j)

The software repeatedly traverses all the values in the two-dimensional array by employing two nested for loops. In
each cycle of the outer loop, which runs i times, the inner loop completes j iterations. Hence, the program's temporal
complexity is O(i*j).

The auxiliary space is O(i*j).

The program allocates a predetermined quantity of auxiliary storage to hold the two-dimensional array and a small
number of integer variables. The space needed for the two-dimensional array is ‘ij’ integers. Furthermore, the
program uses only one integer variable that holds the total of the elements. Hence, the program's auxiliary space
complexity can be expressed as O(ij + 1), which can be simplified to O(i*j).
This program has an O(ij) time complexity and an O(ij) auxiliary space complexity, to sum up.

Based on the examples provided, it is clear that the execution time is affected by the type of operations performed
on the inputs.

Space complexity of Algorithms:

It is necessary to have memory to store temporary data or the final result while the program is being executed in
order to solve problems through a computer. Algorithm space complexity is the memory requirements of an
algorithm to solve a specific problem.

12
 It is possible to quantify the amount of space that an algorithm requires in order to run as a function of the length of
the input by referring to the space complexity of the method. Just to give you an example: Consider a scenario in
which you need to determine the frequency of array elements. As for now let us understand that an array is a group
of data elements stored in continuous memory locations. And when we talk about arrays in C programming
environment, they are homogeneous data types that is elements of same type.
The quantity of memory that is required for an algorithm to get completed is indicated by the term – space
complexity.
We need to concentrate on two aspects in order to make an estimate of the memory requirement:
(1) A fixed portion: it is one that does not change regardless of the size of the input. Instructions (code), constants,
variables, and other types of data are stored in its memory.

(2) A component that is variable: its value is determined by the size of the input. It contains memory for the recursion
stack, variables that are referenced, and other things.

For example

13
 Algorithm 4: Perform arithmetic addition of two numbers

ADD TwoNum(A, B)
1. Start
2. Input two variables A and B
3. C= A+B
4. Output value C
5. Return

For this algorithm apart from the two numbers which have to be added an extra space is required to store the final
result. Since space complexity for this particular algorithm is constant, consequently S(n) = O(1).
If an algorithm is written for an array where the frequency of an element being found n number of times is to be
written then the pseudo code for the algorithm becomes like in Algorithm 5:

14
 Algorithm 5:
1. Start
2. Declare array frequ[n], arr[n]
3. Repeat step 4 for i=0 to i=n times
4. Input arr[n] values
5. Repeat step 6 for i=0 to i=n times
6. Increment frequ[arr[i]]
7. End

The method utilizes two arrays each of length N—one to store the array values and the other to track their
frequencies—along with a single variable i. Consequently, the total space used is calculated as N * c + N * c + 1 *
c = 2N * c + c, where c denotes the space occupied by each element. Therefore, the space complexity can be
described as O(N).
Furthermore, it is important to distinguish between space complexity and auxiliary space. Space complexity accounts
for the total space used by the algorithm, including the input. In contrast, auxiliary space refers to the extra space,
beyond the input, that the algorithm requires to execute. In Algorithm 5 the space that is utilized by the frequ[] array
counts as the auxiliary space because it is not a component of the input that was provided. Therefore, the total
auxiliary space is n(c+c), which is merely O(N).
15
 Time- Space Tradeoff

In the field of computer science, the Space-Time tradeoff provides a method for using problem-solving techniques
to handle the following problems:
1. Solving problems in a shorter amount of time and using large amount of memory space, or
2. Within a relatively small memory space but by devoting more time to the process.

The algorithm that is considered to be the most effective is the one that not only helps to solve a problem but also
calls for less space in memory and takes less time to generate the output. On the other hand, in general, it is not
always possible to accomplish both of these conditions at the same time.
Consider the following scenario: a directory of records has fields for names, social security numbers, and a great
deal of other information. Discovering the record that corresponds to a specific name can be accomplished in a very
effective manner by first sorting the file alphabetically and then performing a binary search. Alternatively, let's say
that the only information we are provided with is the social security number of a person. After then, we are required
to do a linear search for the record, which is a process that is exceedingly time-consuming and expensive when
dealing with a very big number of records. Having a second file that is arranged sequentially according to the social
security number is one approach that can be taken to address this issue. However, this would result in a doubling of
the space that is necessary for the storage of the data. An alternative approach is to arrange the primary file in
numerical order based on social security numbers. Additionally, establish an auxiliary array consisting of two
16
 columns. The first column should include an alphabetised list of the names, while the second column should include
pointers that indicate the locations of the matching records in the primary file. The additional space, which consists
of only two columns, is small for the quantity of additional information that it delivers, which is why this is one of
the ways that the problem that is utilized frequently can be solved.

Through the usage of a space-time trade-off, we would be able to use more memory and solve the problem more
rapidly if our problem is consuming a significant amount of time but not requiring a lot of memory. If, on the other
hand, it is possible to solve it in a very short amount of time but requires more memory than we have, we could try
to spend more time addressing the problem in the memory that we have available.

Compiler
When a program is written, initially the computer is not able to read or understand it as it is. In order to actually run
a program it has to first pass through a compiler. A compiler is a special program which converts a high-level
programming language, known as a source language, for human programmers into a functionally comparable low-
level language, known as the target language or assembly language or machine code, needed by a computer.

17
 Source Target
Compiler
Program Program

After this the program is readable by the computer. There are two versions of a program.
The one that is written with a filename and .c extension but it is non-readable by computer, and the other generated
by a compiler in the format that is computer readable.
The compiler is a complex machine that fills the gap between human-readable code and computer-readable code.
An IDE, is used to write a code that is Integrated Development Environment. Here the whole process is hidden from
the user. When the user clicks the run button, the work is saved, and the program is built, and it runs automatically.

Source Code vs. Machine Code

At a low level, CPU or the computers processors perform small operations. They can read and write to memory, and
they can do mathematical operations on the numbers they are holding. Although now the modern processors do
other things too, but still not much. When an executable program is generated by the compiler, it is a list of
instructions for the processor to follow, written in binary language that is in 0’s and 1’s.
The instructions can be like read bytes from memory, add or subtract them, write bytes to memory, or goto this
particular statement etc. A program which is written in binary language is called machine code, and it can be read
18
 by the computer. CPU only read programs that are written in binary instructions because the processor has circuitry
in it to execute these instructions, and a specific circuitry gets connected when it receives its corresponding
instruction. The binary values 1 and 0 in the instruction induce the opening or closing of particular transistors,
therefore establishing the appropriate circuitry connections to carry out the given command. Executable programs
look like a bunch of o’s and 1’s.
For a programmer to do coding, binary codes are difficult to remember. Rather in a good program a programmer
uses variables, loops, statements, functions etc. thus a programmer is working with higher-level constructs which
are English like statements thus making it easier for the programmer to think and understand.
A program, expressed in a readable form, is called source code. It is a version of a program that a human understands,
and write code in. The compiler thus takes this source code, and translates it into a machine code that is computer-
readable.

Translating Source Code to Machine Code

Take a sample program of 2 variables x and y of type integer. Assign them values 10 and 20 respectively.

19
 Program 8:
void main()
{
int x=10;
int y=20;
}

For the computer, it is a meaningless sequence of characters. Passing this source code into the compiler, the compiler
first divides the text into individual “tokens”. It is like understanding the words of a sentence. The tokens are then
organized into a hierarchical structure known as a parse tree, which is just like understanding what the “grammar”
of this program. Then, the compiler records context about the program, including the variables and functions
declared in the program. This is the information that a computer must maintain a record of in various sections of the
programs. In this example, the only required context is the specific variables x and y, together with the main function.
Finally, it is necessary to systematically explore the tree structure and find machine code that can efficiently perform
the same function as this specific source code. Nevertheless, compilers do not proceed directly from the parse tree
to the machine code, as there exist several intermediate stages.
The machine instructions are expressed as binary code. Given their difficulty in being read and interpreted, coding
can be done in assembly code too, which is a more easily understandable form of the machine code. Program 9 is
an assembly language code of the given C program 8.

20
 Program 9:

section .data
; No global data to define

section .bss
; No uninitialized data to define

section .text
global _start ; Entry point

_start:
; Stack frame setup (if necessary)
; In this simple case, we won't set up a stack frame

; Initialize the values of x and y

mov eax, 10 ; Load 10 into the register (x = 10)
mov ebx, 20 ; Load 20 into the register (y = 20)

; Program exit
mov eax, 60 ; syscall number for exit (Linux)
xor edi, edi ; status 0
syscall ; make the system call to exit

The C code in Program 8 defines the main function with two local variables x and y, and assigns them the values 10
and 20, respectively. These variables are stored in memory during program execution, but assembly deals directly

21
 with registers and memory locations. The Section .data and .bss are used for global data. Where .data holds
initialized global variables and .bss holds uninitialized global variables. But in this case, there are no global variables,
so both sections are empty.
The next Section that is .text is where the actual instructions or code is present. It contains the program logic and
is the most important part of the assembly program. The label global _start is used to define the entry point of the
program. It tells the operating system where to begin executing the code.
The Core Assembly Instructions:
In Program 9 which is equivalent to Program 8’s C code, declares two integer variables x and y. In assembly,
variables are held in registers, which are small storage locations inside the CPU that are used for fast access.
mov eax, 10
• This instruction moves the value 10 into the register eax. The register eax is commonly used to store general-
purpose values in x86 assembly. Here, we use it to represent the variable x.
mov ebx, 20
• Similarly, this instruction moves the value 20 into the register ebx, which we are using to represent the variable
y.
After assigning values to x and y, the program needs to terminate.

Exit System Call:

mov eax, 60
If the program is running on Linux (on x86-64 architecture), the system call number for exit is 60. This line loads
22
 that number into the eax register, signaling the kernel to exit the program.
xor edi, edi
This instruction sets the edi register to 0 (using the XOR operation). In the Linux exit system call, edi is used to pass
the exit status, and 0 indicates a successful exit.
syscall
This is the system call instruction, which tells the operating system to execute the system call (in this case, to
terminate the program). The system call will use the values stored in eax (for the syscall number) and edi (for the
exit status).

References :
1. Kernighan, B. W., & Ritchie, D. M. (2002). The C programming language.
2. Balagurusamy, E. (2016). Programming In Ansi C.
3. e-Content of Manipal University Jaipur.
4. AI tools for language corrections.

23