CS10003:

Programming & Data Structures

Spring 2021

Dept. of Computer Science & Engineering

1
 Course Materials
 Slides available at http://cse.iitkgp.ac.in/pds/current
 More materials available at http://cse.iitkgp.ac.in/pds

Books:
1. Programming with C
Byron Gottfried
2. The C Programming Language
Brian W Kernighan, Dennis M Ritchie
3. Data Structures
S. Lipschutz, Schaum’s Outline Series
 Teachers and Class Timings
 Section 11, 12
 Monday (3-4:55 pm), Tuesday (3-3:55 pm)
 Teacher: Prof. Sandip Chakraborty (SC)
 Section 13, 14
 Monday (3-4:55 pm), Tuesday (3-3:55 pm)
 Teacher: Prof. Shamik Sural (SS)
 Section 15, 16
 Monday (3-4:55 pm), Tuesday (3-3:55 pm)
 Teacher: Prof. Soumya Kanti Ghosh(SKG)
 Section 17, 18
 Wednesday (10-10:55 am), Thursday (9-9:55 am), Friday (11-11:55 am)
 Teacher: Prof. Bivas Mitra (BM)
 Section 19, 20
 Wednesday (10-10:55 am), Thursday (9-9:55 am), Friday (11-11:55 am)
 Teacher: Prof. Rajib Mall (RM)
3
Introduction

4
Basic Components of a Computer
Input Output
Central
Devices: Devices:
Processing
Keyboard, Monitor,
Unit (CPU)
mouse,… printer,…

Main
Memory (RAM)

Disk

5
Programming and Software
Computer needs to be programmed to do tasks…
Programming: Writing instructions in a language that
can be understood by the computer --- so that it can
perform a desired task.
Program: A sequence of instructions to do a task ---
computer processes these instructions
sequentially one after the other
Software: Commercial programs. 6
 Three steps in writing programs…

Step 1: Write the program in a high-level

language (in your case, C)

Step 2: Compile the program using a C compiler

Step 3: Run the program (the computer executes it)

 Binary Representation
 Numbers are represented inside computers in the
base-2 system (Binary Numbers)
 Only two symbols/digits 0 and 1 Example:1011
 Positional weights of digits: 20, 21, 22,…from right to left for integers

 Decimal number system we use is base-10

 10 digits, from 0 to 9, Positional weights 100, 101, 102,…from right to
left for integers
 Example: 723 = 3x100 + 2x101 + 7x102
Dec Binary Binary Numbers
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9
 Binary Numbers
Dec Binary
Binary to Decimal Conversion
0 0
1 1 101011  1x25 + 0x24 + 1x23 + 0x22 + 1x21 + 1x20 =
2 10 43
3 11 (101011)2 = (43)10
4 100
111001  1x25 + 1x24 + 1x23 + 0x22 + 0x21 + 1x20 =
5 101 57
6 110 (111001)2 = (57)10
7 111 10100  1x24 + 0x23 + 1x22 + 0x21 + 0x20 = 20
8 1000 (10100)2 = (20)10
10
 Bits and Bytes
 Bit – a single 1 or 0
 Byte – 8 consecutive bits
 2 bytes = 16 bits
 4 bytes = 32 bits
 Max. integer that can represented
 in 1 byte = 255 (=11111111)
 In 4 bytes = 4294967295 (= 32 1’s)
 No. of integers that can be represented in
1 byte = 256 (the integers 0, 1, 2, 3,….255)
11
Fundamentals of C

12
First C program – print on screen
#include <stdio.h> Output
int main() Hello, World!
{
printf ("Hello, World! \n") ;
return 0;
}

13
 Parts of Our First C Program: Hello World
Header

Comments are good

#include <stdio.h>

/* This program prints “Hello World” */

main( ) means “start here”

main()
{
printf(“Hello World!\n”);
}

Library command
Brackets define code blocks
 A Simple C program
When you run the program
#include <stdio.h> Enter x and y
int main()
{
int x, y, sum, max; Output after you type 15 and 20
printf(“ Enter x and y\n”);
15 20
scanf(“%d%d”, &x, &y);
sum = x + y;
Sum = 35
if (x > y) max = x; Larger = 20
else max = y;
printf (“Sum = %d\n”, sum);
printf (“Larger = %d\n”, max);
return 0;
}
15
 int main(){
Structure of a C program …
}

 A collection of functions (we will see those later) int f1(){

…
}
 Exactly one special function named main must be
present. Program always starts from there. int f1(){
…
}
 Until we study functions in detail, this is the only function
your programs will have for now
 Each function has statements for variable declarations,
assignment, condition check, looping etc.
 Statements are executed one by one in order
16
 Anatomy
#include <stdio.h> main function of a C
int main()
program
Declaration statement
{
int x, y, sum, max;
Input statement
scanf(“%d%d”, &x, &y);
sum = x + y; Assignment statements
if (x > y)
max = x;
else Control statement
max = y;
printf (“Sum = %d\n”, sum);
Output statement
printf (“Larger = %d\n”, max);
return 0;
Return statement
}
17
Writing a C program
 You have to first understand what different statements do --- to
decide which ones you should use and in what order to solve
your problem
 There is a fixed format (“syntax”) for writing each statement and
other things. Need to remember the syntax …
 Do not question at the moment why you have to type exactly like this,
you just have to or it is not a C program!!
 Compiler will give error if your typed program does not match
required C syntax

 There are other rules to follow 18

Things you might need in a C program (we will look at
all these one by one)
 Variables
 Constants
 Expressions (Arithmetic, Logical, Assignment)
 Statements (Declaration, Assignment, Control (Conditional/Branching,
Looping)
 Arrays
 Functions
 Structures
 Pointers

19
 The C Character Set
 The C language alphabet ! # % ^ & * ( )
 Uppercase letters ‘A’ to ‘Z’ - _ + = ~ [ ] \
 Lowercase letters ‘a’ to ‘z’
| ; : ‘ “ { } ,
 Digits ‘0’ to ‘9’
 Certain special characters: . < > / ?
whitespace characters (space, tab, …)
A C program should not contain any other characters

20
 Variables
 Very important concept in programming
 It is an entity that has a value and is known to the program by
its name a=b+c;
 Can store any temporary result while executing a program
 Can have only one value assigned to it at any given time
during the execution of the program
 Variables are stored in memory
 The value of a variable can be changed during the execution of
the program
21
 Memory

Contd. 000
001
 Variables are stored in memory
 Memory is a list of consecutive storage locations, each
having a unique address
 A variable is like a bin
 The content of the bin is the value of the variable
 The variable name is used to refer to the value of the
variable
 A variable is mapped to a location of the memory, called
its address 111
22
Example #include <stdio.h> 000
int main( ) 001

{
int x;
int y;
x=1;
y=3;
printf("x = %d, y= %d\n", x, y);
return 0;
}

111
23
Variables in Memory
Instruction executed Memory location allocated
to a variable X
X = 10
T
i X = 20 10
m
e
X = X +1

X = X*5
24
Variables in Memory
Instruction executed Memory location allocated
to a variable X
X = 10
T
i X = 20 20
m
e
X = X +1

X = X*5
25
Variables in Memory
Instruction executed Memory location allocated
to a variable X
X = 10
T
i X = 20 21
m
e
X = X +1

X = X*5
26
Variables in Memory
Instruction executed
Memory location allocated
to a variable X
X = 10
T
i X = 20 105
m
e
X = X +1

X = X*5
27
Variables (contd.)

X = 20
X
Y=15 20

X = Y+3 ? Y

Y=X/6

28
Variables (contd.)

X = 20
X
Y=15 20

X = Y+3 15 Y

Y=X/6

29
Variables (contd.)

X = 20
X
Y=15 18

X = Y+3 15 Y

Y=X/6

30
Variables (contd.)

X = 20
X
Y=15 18

X = Y+3 3 Y

Y=X/6

31
 Data Types
 Each variable has a type, indicates what type of values
the variable can hold…
 Four common numeric data types in C
 int - can store integers (size usually 4 bytes)
 float - can store single-precision floating point numbers
(size usually 4 bytes)
 double - can store double-precision floating
point numbers (size usually 8 bytes)
 char - can store a character (size 1 byte)
32
 #include <stdio.h>

Contd. int main( )

{
 First rule of variable use: Must declare a int x;
int y;
variable (specify its type and name) before x=1;
using it anywhere in your program y=3;
return 0;
}
 All variable declarations should ideally be at the beginning
of the main() or other functions
 There are exceptions, we will see later
 A value can also be assigned to a variable at
the time the variable is declared.
int speed = 30;
char flag = ‘y’; 33
 Data types
 Three common data are typically types used:
 Integer :: can store only whole numbers
Examples: 25, -56, 1, 0
 Floating-point :: can store numbers with fractional
values.
Examples: 3.14159, 5.0, -12345.345
 Character :: can store a character
Examples: ‘A’, ‘a’, ‘*’, ‘3’, ‘ ’, ‘+’
C Data Types

Character data types

Variable Names
 Sequence of letters and digits
 First character must either be a letter or ‘_’
 No special characters other than ‘_’
 No blank in between
 Names are case-sensitive (max and Max are two
different names)
 Examples of valid names:
 i rank1 MAX max Min class_rank
 Examples of invalid names:
 a’s fact rec 2sqroot class,rank a&b 36
 More Valid and Invalid Identifiers
 Valid identifiers  Invalid identifiers
X 10abc
abc
my-name
simple_interest
“hello”
a123
LIST simple interest
stud_name (area)
Empl_1 %rate
Empl_2
avg_empl_salary
 C Keywords
 Used by the C language, cannot be used as variable
names
 Examples:
 int,float, char, double, main, if else, for, while. do, struct,
union, typedef, enum, void, return, signed, unsigned, case,
break, sizeof,….
 There are others, see textbook…
Example 1: Add Two Numbers
#include <stdio.h>
int main()
{
int x, y, sum; Three int type variables declared
scanf(“%d%d”,&x,&y);
sum = x + y;
Values
printf( “%d plus %d is %d\n”, x, y, sum );
assigned
return 0;
}

39
 Example 2
#include <stdio.h>
int main()
{
float x, y; Assigns an initial value to d2,
can be changed later
int d1, d2 = 10;
scanf(“%f%f%d”,&x, &y, &d1);
printf( “%f plus %f is %f\n”, x, y, x+y);
printf( “%d minus %d is %d\n”, d1, d2, d1-d2);
return 0;
} 40
 Read-only Variables ( Constants)
 Variables whose values can be initialized during
declaration, but cannot be changed after that
 Declared by putting the const keyword in front of
the declaration
 Storage allocated just like any variable
 Used for variables whose values need
not be changed
 Prevents accidental change of the value
41
int main() {
const int LIMIT = 10;
Incorrect: Limit changed
int n;
scanf(“%d”, &n); int main() {
const int Limit = 10;
if (n > LIMIT)
int n;
printf(“Out of
limit”);
scanf(“%d”, &n);
Limit = Limit + n;
return 0;
printf(“New limit is %d”,
}
Limit);
Correct return 0;
} 42
 Constants
 Integer constants
 Consists of a sequence of digits, with possibly a plus or a
minus sign before it
 Embedded spaces, commas and non-digit characters are not
permitted between digits
 Floating point constants
 Two different notations: e means “10 to the power of”
 Decimal notation: 25.0, 0.0034, .84, -2.234
 Exponential (scientific) notation
3.45e23, 0.123e-12, 123e2 43
 Character constants
Contd.
 Contains a single character enclosed within a pair of single
quote marks.
 Examples :: ‘2’, ‘+’, ‘Z’
 Some special backslash characters
‘\n’ new line
‘\t’ horizontal tab
‘\’’ single quote
‘\”’ double quote
‘\\’ backslash
‘\0’ null 44
 char – 1 byte Typical Size of Data Types
 int – 4 bytes
 float – 4 bytes
 double – 8 bytes

 “Typical”, because some of them vary depending on

machine/OS type
 Never use the values (1, 4, 8) directly,
use the sizeof() operator given
 sizeof(char) will give 1, sizeof(int) will give 4 and
so on your PC/Laptop 45
 Input: scanf function
 Performs input from keyboard
 It requires a format string and a list of variables into which
the value received from the keyboard will be stored
 format string = individual groups of characters (usually ‘%’
sign, followed by a conversion character), with one character
group for each variable in the list

int a, b; Variable list (note the &

before a variable name)
float c;
scanf(“%d%d%f”, &a, &b, &c);
Format string
46
 Commonly used conversion characters
c for char type variable
d for int type variable
f for float type variable
lf for double type variable

 Examples
scanf ("%d", &size) ;
scanf ("%c", &nextchar) ;
scanf ("%f", &length) ;
scanf (“%d%d”, &a, &b);

47
 scanf ("%d", &size) ; Examples Explained
 Reads one integer from keyboard into an int type variable named
size
 scanf ("%c", &nextchar) ;
 Reads one character from keyboard into a char type variable named
nextchar
 scanf ("%f", &length) ;
 Reads one floating point (real) number from keyboard into a float
type variable named length
 scanf (“%d%d”, &a, &b);
 Reads two integers from keyboard, the first one in an int
type variable named a and the second one in an int type
variable named b 48
 Important:
 scanfwill wait for you to type the input from the
keyboard
 Youmust type the same number of inputs as the
number of %’s in the format string
 Example: if you have scanf(“%d%d”,…), then
you must type two integers (in same line or
different lines), or scanf will just wait and the next
statement will not be executed
49
 Reading a single character
 A single character can be read using scanf with %c
 It can also be read using the getchar() function

char c;
c = getchar();
 Program waits at the getchar() line until
a character is typed, and then reads it
and stores it in c.
50
 Output: printf function
 Performs output to the standard output device (usually defined
to be the screen)
 It requires a format string in which we can specify:
 The text to be printed out
 Specifications on how to print the values
printf ("The number is %d\n", num);
 The format specification %d causes the value listed after the format
string to be embedded in the output as a decimal number in place of
%d
 Output will appear as: The number is 125
51
Contd.
 General syntax:
printf (format string, arg1, arg2, …, argn);
 format string refers to a string containing formatting
information and data types of the arguments to be output
 the arguments arg1, arg2, … represent list of
variables/expressions whose values are to be printed
 The conversion characters are the same as
in scanf
52
 Examples:
printf (“Average of %d and %d is %f”, a, b, avg);
printf (“Hello \nGood \nMorning \n”);
printf(“%3d %3d %5d”, a, b, a*b+2);
printf(“%7.2f %5.1f”, x, y);
 Many more format options are available for both printf
and scanf
 Read from the book
 Practice them in your computer!
53
 More Examples
(Explain the outputs to test if you understood format strings etc.)

54
More print
Output
Hello, World! Hello
#include <stdio.h> World!
int main()
{
printf ("Hello, World! ") ;
printf ("Hello \n World! \n") ;
return 0;
}
55
 Some more print Output
Hello, World!
#include <stdio.h> Hello
int main() World!
Hell
{
o World!
printf ("Hello, World! \n") ;
printf ("Hello \n World! \n") ;
printf ("Hell\no \t World! \n") ;
return 0;
}
56
 Enter values for f1 and f2:
Some more print 23.5 14.326
#include <stdio.h> Enter values for x1 and x2:
int main() Output 54 7
{
f1 = 23.500000, f2 = 14.33
float f1, f2;
int x1, x2;
x1 = 54, x2 = 7
printf(“Enter values for f1 and f2: \n”); Can you explain why 14.326 got printed
as 14.33?
scanf(“%f%f”, &f1, &f2);
printf(“Enter values for x1 and x2: \n”);
scanf(“%d%d”, &x1, &x2);
printf(“f1 = %f, f2 = %5.2f\n”, f1, f2);
printf(“x1 = %d, x2 = %10d\n”, x1, x2);
return 0;
}
57
 Some more print Output
ab
#include <stdio.h> ab
int main()
{
char c1, c2;
scanf(“%c%c”, &c1, &c2);
printf(“%c%c”, c1, c2);
return 0;
}
58
What about this? Output
ab
#include <stdio.h> a
int main() Can you explain why only ‘a’ was
printed this time, even though it is the
{ same program as in the last slide?
Note the difference from the last slide
char c1, c2; carefully. Also note that two characters
were read this time also, or scanf
would have waited
scanf(“%c%c”, &c1, &c2);
printf(“%c%c”, c1, c2);
return 0;
}
59
 Write C programs to:
Practice Problems
1. Read two integers and two floating point numbers, each in a separate scanf()
statement (so 4 scanf’s) and print them with separate printf statements (4
printf’s) with some nice message
2. Repeat 1, but now read all of them in a single scanf statement and print them
in a single printf statement
3. Repeat 1 and 2 with other data types like double and char
4. Repeat 1 and 2, but now print all real numbers with only 3 digits after the
decimal point
5. Read 4 integers in a single scanf statement, and print them (using a single
printf statement) in separate lines such that the last digit of each integer is
exactly 10 spaces away from the beginning of the line it is printed in (the 9
spaces before will be occupied by blanks or other digits of the integer).
Remember that different integers can have different number of digits
6. Repeat 5, but now the first integer of each integer should be exactly 8 spaces
away from the beginning of the line it is printed in. 60