1. Algorithms.

Fundamentals
a. Properties and definitions
An algorithm is a strictly defined finite sequence of well-defined statements that
provides the solution to a problem or to a specific class of problems for any acceptable
set of input values. In other words, an algorithm is a step-by-step procedure to solve a
given problem. An algorithm must satisfy the following properties:
- Input: The algorithm must have input valuesform a specified set.
- Output: The algorithm must produce the output valuesform a specified
set of input values. The output values are the solution to a problem.
- Finitness: For any input, the algorithm must terminate after a finite
number of steps.
- Definiteness: All steps of the algorithm must be precisely defined.
- Effectiveness: It must be possible to perform each step of the algorithm
correctly and in a finite amount of time. That is, its steps must be basic
enough so that, for example, someone using a pencil and a paper could
carry them out exactly, and in a finite amount of time. It is enough that
each step is definite, but it must also be feasible.
b. Methods of description
The main parts of an algorithm description are

 purpose (what is the result of running the algorithm),

 data structure (what is manipulated by the algorithm),

 technique (what steps does the algorithm perform),

 justification (proof of correctness, often reduced to hand-waving),

 analysis (speed, space, cost, ...).

Pictures are often the clearest way to explain data structures, particularly when pointers
are required. Whenever a picture is used, it should be a numbered, captioned figure. Figures
should be (nearly) comprehensible without the accompanying text. Make sure the caption
explains what the figure means. Something like ``Figure 3. Step 2 of the algorithm.'' is nearly
useless. A better caption might be ``Figure 3. Swapping out-of-order data elements pointed to
by i and j.''

Instead of flowcharts, most algorithms are now described using pseudo-code. The
pseudo-code syntax can be based on any structured language (Algol, Pascal, C, Ada, ...), but
should be readable by someone familiar only with a different language. Tests and statements
are not written in full detail, instead the intent of the statement or test is given. For example,
pseudo-code for finding the minimum of an array might look like:

min for each element of array

 if element<min then min element

Pseudo-code should be properly indented and either displayed like the example above,
or put into a figure with a figure number and caption.

c. Example: logic diagram of the Euclid algorithm for CMMDC of two numbers

2. The structure of a C program

a. Directives
Before a C program is compiled in a compiler, source code is processed by a program
called preprocessor. This process is called preprocessing. Commands used in
preprocessor are called preprocessor directives and they begin with “#” symbol.
 Below is the list of preprocessor directives that C programming language offers.

b. Main function ()
Every C-programs needs to have the main function. Each main function contains 2 parts.
A declaration part and an Execution part. The declaration part is the part where all the variables
are declared. The execution part begins with the curly brackets and ends with the curly close
bracket. Both the declaration and execution part are inside the curly braces.
int main(void)
{
int a=10;
printf(" %d", a);
return 0;
}
c. User functions
A function is a block of code that performs a specific task. C allows us to define functions
according to a specific need. These functions are known as user-defined. For example:
printf(…) is a function.
d. Execution stages
 The C program follows many steps in execution. To understand the flow of C program
well, let us see a simple program first.
#include <stdio.h>
int main(){
printf("Hello C Language");
return 0;
}
1) C program (source code) is sent to the preprocessor first. The preprocessor is
responsible to convert preprocessor directives into their respective values. The
preprocessor generates an expanded source code.
2) Expanded source code is sent to the compiler which compiles the code and
converts it into assembly code.
3) The assembly code is sent to the assembler which assembles the code and
converts it into object code. Now a simple.obj file is generated.
4) The object code is sent to linker which links it to the library such as header files.
Then it is converted into executable code. A simple.exe file is generated.
5) The executable code is sent to the loader which loads it into memory and then
it is executed. After execution, output is sent to the console.
3. Data input in C
a. Scanf () function
In C programming, scanf() is one of the commonly used function to take input from the
user. The scanf() function reads formatted input from the standard input such as keyboards.
#include <stdio.h>
int main()
{
int testInteger;
printf("Enter an integer: ");
scanf("%d", &testInteger);
printf("Number = %d",testInteger);
return 0; }

b. Format specifiers
The format specifier is used during input and output. It is a way to tell the compiler what
type of data is in a variable during taking input using scanf() or printing using printf().
Some examples are %c, %d, %f, etc.
printf():

 Character format specifier : %c

 Integer format specifier : %d, %i
 Floating-point format specifier : %f, %e or %E
 Unsigned Octal number for integer : %o (transform and prints a to octal form)
 Unsigned Hexadecimal for integer : %x, %X (transform and prints a to hex form)
 String printing : %s
 More formatting for strings:
%20s – the string is written on 20 positions, the text aligned to the right.
%-20s – the string is written on 20 positions, the text aligned to the left.
%20.5s – only the first 5 letters of the string are written on 20 positions, al. r.
%-20.5s – only the first 5 letters of the string are written on 20 positions, al. l.
scanf():

 decimal integer : %d
 Integer may be octal or in hexadecimal : %i
 Double floating-point number : %lf
 String input : %s
 Character input : %c
 An unsigned integer: %u
 Long long int: %lld
 Octal integer without leading zero: %o
 Hexadecimal integer without 0x before the number: %x
c. Alternative functions
To convert the input, there are a variety of functions that you can use:
● strtoll, to convert a string into an integer
● strtof/d/ld, to convert a string into a floating-point number
● sscanf, which is not as bad as simply using scanf, although it does
have most of the downfalls mentioned below.
● There are no good ways to parse a delimiter-separated input in plain
ANSI C. Either use strtok_r from POSIX or strtok, which is not
thread-safe. You could also roll your own thread-safe variant using
strcspn and strspn, as strtok_r doesn't involve any special OS support.
● It may be overkill, but you can use lexers and parsers (flex and bison
being the most common examples).
 d. standard input / output buffer memory control
Temporary storage area is called a buffer.
All standard input output devices are containing input output buffers.
In implementation when we are passing more than the required number of values as an
input then the rest of all values will automatically hold in the standard input buffer, this
buffer data will automatically pass to next input functionality if it exists.
flushall()
it is a predefined function which is declared in stdio.h. by using flushall we can remove
the data from standard input output buffer.
fflush()
it is a predefined function in "stdio.h" header file used to flush or clear either input or
output buffer memory.
fflush(stdin)
it is used to clear the input buffer memory. It is recommended to use before writing
scanf statement.
fflush(stdout)
it is used to clear the output buffer memory. It is recommended to use before printf
statement.
4. Display of data in C
a. The printf () function
In C programming, printf() is one of the main output functions. The function sends
formatted output to the screen. For example,
#include <stdio.h>
int main()
{
// Displays the string inside quotations
printf("C Programming");
return 0;
}
Output: C Programming
I) All valid C programs must contain the main() function. The code
execution begins from the start of the main() function.
II) The printf() is a library function to send formatted output to the
screen. The function prints the string inside quotations.
 III) To use printf() in our program, we need to include stdio.h header
file using the #include <stdio.h> statement.
IV) The return 0; statement inside the main() function is the "Exit
status" of the program. It's optional.
b. Format specifiers
printf():

 Character format specifier: %c

 Integer format specifier: %d, %i
 Floating-point format specifier: %f, %e or %E
 Unsigned Octal number for integer: %o (transform and prints a to octal form)
 Unsigned Hexadecimal for integer: %x, %X (transform and prints a to hex form)
 String printing: %s
 More formatting for strings:
%20s – the string is written on 20 positions, the text aligned to the right.
%-20s – the string is written on 20 positions, the text aligned to the left.
%20.5s – only the first 5 letters of the string are written on 20 positions, al. r.
%-20.5s – only the first 5 letters of the string are written on 20 positions, al. l.
For a better understanding, see the previous question, nr. 3, point b).
c. Alternative functions
The most common ways of reading input are:
● using fgets with a fixed size, which is what is usually suggested, and
● using fgetc, which may be useful if you're only reading a single char.
d. standard input / output buffer memory control
See question nr. 3, point d).
Practice:
1. Describe the insertion of a node in Queue
The major problem with the queue implemented using an array is, It will work for an only fixed
number of data values. That means, the amount of data must be specified at the beginning itself. Queue
using an array is not suitable when we don't know the size of data which we are going to use. A queue
data structure can be implemented using a linked list data structure. The queue which is implemented
using a linked list can work for an unlimited number of values. That means, queue using linked list can
work for the variable size of data (No need to fix the size at the beginning of the implementation). The
Queue implemented using linked list can organize as many data values as we want. In linked list
implementation of a queue, the last inserted node is always pointed by 'rear' and the first node is always
pointed by 'front'. To implement queue using linked list, we need to set the following things before
implementing actual operations.

 Step 1 - Include all the header files which are used in the program. And declare all the user
defined functions.
  Step 2 - Define a 'Node' structure with two members data and next.
 Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
 Step 4 - Implement the main method by displaying Menu of list of operations and make suitable
function calls in the main method to perform user selected operation.

* personally, I didn’t understand anything, so I added another explanation. :) *

Insertion in the non-empty queue:

1. Allocate a new node and hold the pointer to it in a variable (basically, don’t forget to
create a variable I that will point to the new node, otherwise you may lose it in the
memory.) Return from the insert function now signaling an error if the new node cannot be
allocated.
2. Store the information in the newly created node.
3. Make the newly created node point to null (*next pointer points to NULL).
4. Make the old rear node point the newly created node (*next pointer points to the I node)
5. Actualize the rear to point to the newly created node.
2. Describe the insertion of a node in Stack
The major problem with the stack implemented using an array is, it works only for a
fixed number of data values. That means the amount of data must be specified at the beginning
of the implementation itself. Stack implemented using an array is not suitable, when we don't
know the size of data which we are going to use. To implement a stack using a linked list, we
need to set the following things before implementing actual operations.
 Step 1 - Include all the header files which are used in the program. And declare all the
user defined functions.
 Step 2 - Define a 'Node' structure with two members data and next.
 Step 3 - Define a Node pointer 'top' and set it to NULL.
 Step 4 - Implement the main method by displaying Menu with list of operations and
make suitable function calls in the main method.
* same problem here :) *

• push() − Pushing (storing) an element on the stack.

 Step 1 – Create a new node, pointing to null.

 Step 2 – Point the new node to the top node of the stack
 Step 3 – Actualize the top node to be the new node.

3. Describe the process of removal node from Stack

We explicitly handle the case when the node to be deleted is the first node, we copy the
data of the next node to head and delete the next node. The cases when a deleted node is not
the head node can be handled normally by finding the previous node and changing next to the
previous node.
*…*

 pop() − Removing (accessing) an element from the stack.

 o Step 1 − Checks if the stack is empty.

o Step 2 − If the stack is empty, produces an error and exit.

o Step 3 − If the stack is not empty, accesses the data element at which
top is pointing.
o Step 4 – Point a variable I to the node and actualize the Top to point
to the previous node.
o Step 5 – Point the *next pointer of node I to null and delete node I
from the memory.

4. Describe the process of Queue traversal.

A queue uses the Level order tree traversal:

*…*

 Traversing a queue – the queue is traversed from front to rear.

 Step 1 – Create a variable I that will point to the front node.
 Step 2 – Extract the information from the node.
 Step 3 – By using the *next pointer of the node I, make the variable I to
point to the next node, extract the information and so on, until the *next
of the node I doesn’t point to NULL.
5. Describe the process of Stack traversal.
 A stack uses the Iterative Postorder Traversal:

*…*

 Traversing a stack – this is a much more complicated process, as we don’t

have a way to verify if we reached the bottom, because the *next pointer
points to the upper next node, not down. That’s why, as in the case of a
box with books, we need to get out books before we can see thw next
element in the box. Per general, we have 2 methods of doing it,
depending on the order we need to analyze, either form top (last book) to
bottom (first book) or the other way around. Because the second way has
more logic and application in reality, that’s the one which algorithm we
are going to describe superficially:
 Step 1: get one-by-one elements out from your stack and place
them in another one. Therefore, you have stack 2 with the
reversed order of elements.
 Step 2 : Get one-by one elements from Stack 2, analyze the
information and place them back in stack 1. You-l have back the
stack 1 and you have analyzed all the “books in the box”.
6. Describe the operation of two strings comparing.
Strings can be compared either by using the string function or without using string
function.
int strcmp (const char* str1, const char* str2);
In the above syntax, two parameters are passed as strings, i.e., str1 and str2, and the return
type is int means that the strcmp() returns an integer value. The strcmp() function compares
the character of both the strings. If the first character of both the strings are same, then this
process of comparison will continue until all the characters are compared or the pointer points
to the null character '\0'.
7. Describe the operation of string length calculation.
The null character isn't counted when calculating it. To find it, we can use strlen function
of "string.h." C program to find length of a string without using strlen function, recursion.

Theory:

5. Simple data types in C

a. Numeric types

 Numerical integer types: They can store a whole number value, such as 7 or 1024. They exist in a variety of sizes, and
can either be signed or unsigned, depending on whether they support negative values or not.
 Floating-point types: They can represent real values, such as 3.14 or 0.01, with different levels of precision,
depending on which of the three floating-point types is used.

Group Type names* Notes on size / precision

signed char Same size as char. At least 8 bits.
signed short int Not smaller than char. At least 16 bits. * The names of certain integer types
can be abbreviated without
Integer types (signed) signed int Not smaller than short. At least 16 bits.
their signed and int components - only
signed long int Not smaller than int. At least 32 bits. the part not in italics is required to
signed long long int Not smaller than long. At least 64 bits. identify the type, the part in italics is
unsigned char optional. I.e., signed short int can be
unsigned short int abbreviated as signed short, short int,
or simply short; they all identify the
Integer types unsigned int
(same size as their signed counterparts) same fundamental type.
(unsigned) unsigned long int
unsigned long b. Character types
long int
float  Character types: They can
Floating-point types double Precision not less than float represent a single character,
long double Precision not less than double such as 'A' or '$'. The most
basic type is char, which is a
one-byte character. Other
types are also provided for wider characters.

Group Type names* Notes on size / precision

char Exactly one byte in size. At least 8 bits.
Character char16_t Not smaller than char. At least 16 bits.
types char32_t Not smaller than char16_t. At least 32 bits.
wchar_t Can represent the largest supported character set.

c. Variables

Variables are memory locations of predefined sizes that can store data of a certain type and are identified by name. The variable
name is an identifier (word) consisting of one or more letters and numbers, the first symbol being a letter. The variable name can
also contain the underscore symbol.
d. Variables initialization

When the variables are declared, they have an undetermined value until they are assigned a value for the first time. But it is
possible for a variable to have a specific value from the moment it is declared. This is called the initialization of the variable.
In C++, there are three ways to initialize variables. They are all equivalent and are reminiscent of the evolution of the language
over the years:
1. The first one, known as c-like initialization (because it is inherited from the C language), consists of appending an equal sign
followed by the value to which the variable is initialized:
type identifier = initial_value;
For example, to declare a variable of type int called x and initialize it to a value of zero from the same moment it is declared, we
can write:

  int x = 0;

2. A second method, known as constructor initialization (introduced by the C++ language), encloses the initial value between
parentheses (()):
type identifier (initial_value);
For example:

  int x (0);

3. Finally, a third method, known as uniform initialization, similar to the above, but using curly braces ({}) instead of parentheses
(this was introduced by the revision of the C++ standard, in 2011):
type identifier {initial_value};
For example:

  int x {0};

6. Selection statements

a. The if statement

The if keyword is used to execute a statement or block, if, and only if, a condition is fulfilled. Its syntax is:
if (condition) statement
Here, condition is the expression that is being evaluated. If this condition is true, statement is executed. If it is false, statement is
not executed (it is simply ignored), and the program continues right after the entire selection statement.
b. The operation?

The conditional operator evaluates an expression, returning one value if that expression evaluates to true, and a different one if
the expression evaluates as false. Its syntax is:
condition ? result1 : result2
If condition is true, the entire expression evaluates to result1, and otherwise to result2.

c. Switch () statement

Its purpose is to check for a value among a number of possible constant expressions. It is something similar to concatenating if-
else statements, but limited to constant expressions. Its most typical syntax is:

switch (expression)
{
case constant1:
group-of-statements-1;
break;
case constant2:
group-of-statements-2;
break;
.
default:
default-group-of-statements
}

It works in the following way: switch evaluates expression and checks if it is

equivalent to constant1; if it is, it executes group-of-statements-1 until it
finds the break statement. When it finds this break statement, the program
jumps to the end of the entire switch statement (the closing brace).

If expression was not equal to constant1, it is then checked against constant2. If it is equal to this, it executes group-of-
statements-2 until a break is found, when it jumps to the end of the switch.

Finally, if the value of expression did not match any of the previously specified constants (there may be any number of these), the
program executes the statements included after the default: label, if it exists (since it is optional).

Break statements are needed after each group of statements for a particular label. If break is not included, all statements following
the case (including those under any other labels) are also executed, until the end of the switch block or a jump statement (such
as break) is reached.

7. Loops

a. Counter driven loops

A common type of program loop is one that is controlled by an integer that counts up from a initial value to an upper limit. Such
a loop is called a counting loop. The integer is called a loop control variable. Loops are implemented with the conditional branch,
jump, and conditional set instructions.

A loop has three parts that must be correct:

- The counter must be initialized.

- The test must end the loop on the correct count.
- The counter must be increased.

For

for (initialization; condition; increase) statement;

Like the while-loop, this loop repeats statement while condition is true. But, in addition, the for loop provides specific locations
to contain an initialization and an increase expression, executed before the loop begins the first time, and after each iteration,
respectively. Therefore, it is especially useful to use counter variables as condition.

It works in the following way:

1. initialization is executed. Generally, this declares a counter variable, and sets it to some initial value. This is executed a
single time, at the beginning of the loop.
 2. condition is checked. If it is true, the loop continues; otherwise, the loop ends, and statement is skipped, going directly
to step 5.
3. statement is executed. As usual, it can be either a single statement or a block enclosed in curly braces { }.
4. increase is executed, and the loop gets back to step 2.
5. the loop ends: execution continues by the next statement after it.

The three fields in a for-loop are optional. They can be left empty, but in all cases the semicolon signs between them are required.
For example, for (;n<10;) is a loop without initialization or increase (equivalent to a while-loop); and for (;n<10;++n) is a loop
with increase, but no initialization (maybe because the variable was already initialized before the loop). A loop with
no condition is equivalent to a loop with true as condition (i.e., an infinite loop)

b. Condition-driven loops (precondition / post-condition)

Condition-controlled loop - the loop that repeats the execution of a sequence of instructions as long as a condition remains true.
The condition is described by a Boolean or arithmetic test expression.

1. While

while (expression) statement

The while-loop simply repeats statement while expression is true. If, after any execution of statement, expression is no longer
true, the loop ends, and the program continues right after the loop. 

A thing to consider with while-loops is that the loop should end at some point, and thus the statement shall alter values checked
in the condition in some way, so as to force it to become false at some point. Otherwise, the loop will continue looping forever.

Note that the complexity of this loop is trivial for a computer, and so the whole countdown is performed instantly, without any
practical delay between elements of the count

2. Do… While

do statement while (condition);

It behaves like a while-loop, except that condition is evaluated after the execution of statement instead of before, guaranteeing at
least one execution of statement, even if condition is never fulfilled.

The do-while loop is usually preferred over a while-loop when the statement needs to be executed at least once, such as when the
condition that is checked to end of the loop is determined within the loop statement itself. 

c. Nested loops
C programming allows to use one loop inside another loop. 

The syntax for a nested for loop statement in C++ is as follows −

for ( init; condition; increment ) {

for ( init; condition; increment ) {
statement(s);
}
statement(s); // you can put more statements.
}

The syntax for a nested while loop statement in C++ is as follows −

while(condition) {
while(condition) {
statement(s);
}
statement(s); // you can put more statements.
}

The syntax for a nested do...while loop statement in C++ is as follows −

do {
statement(s); // you can put more statements.
do {
statement(s);
} while( condition );

} while( condition );

d. Break and continue statements

1. Break

The break statement has the following two usages in C++ −

 When the break statement is encountered inside a loop, the loop is immediately terminated and program control
resumes at the next statement following the loop.

 It can be used to terminate a case in the switch statement (covered in the next chapter).

If you are using nested loops (i.e., one loop inside another loop), the break statement will stop the execution of the innermost
loop and start executing the next line of code after the block.
The syntax of a break statement in C++ is − break;

2.Continue

The continue instruction causes the program to skip the rest of the loop in the present iteration as if the end of the statement block
would have been reached, causing it to jump to the following iteration.
8. User functions in C

a. Description / declaration

A function declaration tells the compiler about a function's name, return type, and parameters. A function definition provides
the actual body of the function.

Defining a Function
The general form of a C++ function definition is as follows −

return_type function_name( parameter list ) {

body of the function
}
A C++ function definition consists of a function header and a function body. Here are all the parts of a function −

 Return Type − A function may return a value. The return_type is the data type of the value the function returns.
Some functions perform the desired operations without returning a value. In this case, the return_type is the
keyword void.

 Function Name − This is the actual name of the function. The function name and the parameter list together constitute
the function signature.

 Parameters − A parameter is like a placeholder. When a function is invoked, you pass a value to the parameter. This
value is referred to as actual parameter or argument. The parameter list refers to the type, order, and number of the
parameters of a function. Parameters are optional; that is, a function may contain no parameters.

 Function Body − The function body contains a collection of statements that define what the function does.
Function Declarations
A function declaration tells the compiler about a function name and how to call the function. The actual body of the function
can be defined separately.

A function declaration has the following parts −

return_type function_name( parameter list );

For the above defined function max(), following is the function declaration −

int max(int num1, int num2);

Parameter names are not important in function declaration only their type is required, so following is also valid declaration −

int max(int, int);

Function declaration is required when you define a function in one source file and you call that function in another file. In such
case, you should declare the function at the top of the file calling the function.

b. Function parameters

 Parameters − A parameter is like a placeholder. When a function is invoked, you pass a value to the parameter. This
value is referred to as actual parameter or argument. The parameter list refers to the type, order, and number of the
parameters of a function. Parameters are optional; that is, a function may contain no parameters.
c. Local variables

A variable defined inside a function (defined inside function body between braces) is called a local variable or automatic
variable.

Its scope is only limited to the function where it is defined. In simple terms, local variable exists and can be accessed only inside
a function.

The life of a local variable ends (It is destroyed) when the function exits.

d. Returning results

When you write a user-defined function, you get to determine whether your function will return a value back to the caller or not.
To return a value back to the caller, two things are needed.

First, your function has to indicate what type of value will be returned. This is done by setting the function’s return type, which
is the type that is defined before the function’s name. In the example above, function getValueFromUser has a return type
of void, and function main has a return type of int. Note that this doesn’t determine what specific value is returned -- only the
type of the value.

Second, inside the function that will return a value, we use a return statement to indicate the specific value being returned to the
caller. The specific value returned from a function is called the return value. When the return statement is executed, the return
value is copied from the function back to the caller. This process is called return by value.

Practice:

8. Describe the operation of two strings concatenation.

With +operator

#include <bits/stdc++.h>

using namespace std;

int main()

{
string s1,s2; //two string

cin>>s1>>s2;

string result = s1 + s2; //direct concat using + operator

cout<<result;

return 0;

1. Take two strings

2. Use “+” operator

Without +operator:

START

Step 1 -> Take two string as str1 and str2.

Step 2 -> Move to the last position of first string let it be i.

Step 3 -> Now Loop over second string with j = 0

Assign the character str1[i] = str2[j]

Increment i and j and repeat till the last element of j.

End Loop

Step 3 -> Print str1.

STOP

#include <iostream>

using namespace std;

int main()

char str1[100] = "hello ", str2[] = "world!";

int i, j;

for (i = 0; str1[i] != '\0'; ++i);

for (j = 0; str2[j] != '\0'; ++j, ++i) {

str1[i] = str2[j];

str1[i] = '\0';

cout<<"After Concatenation Of Two String: ";

cout<<str1;

return 0;

9. Describe the operation of searching string S into string Q.

The idea is to run a loop from start to end and for every index in the given string check whether the sub-string can be formed
from that index. This can be done by running a nested loop traversing the given string and in that loop run another loop checking
for sub-string from every index.

For example, consider there to be a string of length N and a substring of length M. Then run a nested loop, where the outer loop
runs from 0 to (N-M) and the inner loop from 0 to M. For very index check if the sub-string traversed by the inner loop is the
given sub-string or not.

#include <bits/stdc++.h>
using namespace std;

// Returns true if s1 is substring of s2

int isSubstring(string s1, string s2)

int M = s1.length();

int N = s2.length();

/* A loop to slide pat[] one by one */

for (int i = 0; i <= N - M; i++) {

int j;

/* For current index i, check for

pattern match */

for (j = 0; j < M; j++)

if (s2[i + j] != s1[j])

break;

if (j == M)

return i;

return -1;

/* Driver code */

int main()

string s1 = "for";

string s2 = "geeksforgeeks";

int res = isSubstring(s1, s2);

if (res == -1)

cout << "Not present";

else

cout << "Present at index " << res;

return 0;

}
10. Describe the operation of two strings comparing.

11. Describe the operation of copying a part of the string S into string Q (given length, and

start position).

12. Describe the operation of removing a part of the string (given length, and start position)
13. Describe the operation of insertion of the string S into string Q (in a given position)

Without using any pre-defined method

Approach:
1. Get the Strings and the index.
2. Create a new String
3. Traverse the string till the specified index and copy this into the new String.
4. Copy the String to be inserted into this new String
5. Copy the remaining characters of the first string into the new String
6. Return/Print the new String

14. Describe the operation of conversion from integer to a string

Theory:

9. Structures in C

a. struct type variables description / declaration

 A structure variable can either be declared with structure declaration or as a separate
declaration like basic types.
// A variable declaration with structure declaration.

struct Point

int x, y;

} p1; // The variable p1 is declared with 'Point'

Or

// A variable declaration like basic data types

struct Point

int x, y;

};

int main()

struct Point p1; // The variable p1 is declared like a normal

variable

Note: In C++, the struct keyword is optional before in declaration of a variable. In C, it is

mandatory.

Structure members cannot be initialized with declaration. For example the following C
program fails in compilation.
struct Point

int x = 0; // COMPILER ERROR: cannot initialize members here

int y = 0; // COMPILER ERROR: cannot initialize members here

};

The reason for above error is simple, when a datatype is declared, no

memory is allocated for it. Memory is allocated only when variables are
created.

b. Arrays of structures

Like other primitive data types, we can create an array of structures.

 An array of structres in C can be defined as the collection of multiple structures variables
where each variable contains information about different entities. The array
of structures in C are used to store information about multiple entities of different data
types. The array of structures is also known as the collection of structures.

struct Point
{
   int x, y;
};
  
int main()
{
   // Create an array of structures
   struct Point arr[10];
}

c. Accessing structure fields

Structure members are accessed using dot (.) operator.

struct Point
{
   int x, y;
};
  
int main()
{
   struct Point P1;

P1.x=20; //Accessing member x of point P1

P1.y=30; //Accessing member y of point P1

d. Use in dynamically allocated lists

 Like primitive types, we can have pointer to a structure. If we have a pointer to
structure, members are accessed using arrow ( -> ) operator.
struct Point
{
   int x, y;
};
  
int main()
{
   struct Point p1 = {1, 2};
  
   // p2 is a pointer to structure p1
   struct Point *p2 = &p1;
  
   // Accessing structure members using structure pointer
   printf("%d %d", p2->x, p2->y);
   return 0;
}

A linked list is an ordered collection of nodes, each of which contains some data,
connected using pointers. Each node is actually a struct variable, which contains an ID,
the additional data of the object and a pointer variable that points to the next node. For
example, the next structure is defined for a list of cars in a car lot.
struct carType
{
int vehicleID;
char make[20];
char model[20];
int year;
int mileage;
double cost;
Car *next; // ptr to next car in list
};
See more on point 12.

10. Dynamic memory allocation in C. Linear data structures: queue

a. Properties of the data structure – queue

Queue is a FIFO (First-In, First-Out) list, a list-like structure that provides restricted
access to its elements: elements may only be inserted at the back and removed from the
front. Similarly to stacks, queues are less flexible than lists.

b. The structure of the queue elements

Enqueue: insert elements into queue at the back.

Dequeue: remove elements from the front.

Out <- |First element||Queue| |Last element| <- In

c. operations on queue

Last (new)
First
element
element

Insertion in the empty-queue:

1. Allocate a new node and hold the pointer to it in a variable. Return from the insert
function now signaling an error if the new node cannot be allocated.

2. Store the information in the newly created node.

3. Make the newly created node point to null.

4. Make rear and front point to the newly created node.

Insertion in the non-empty queue:

1. Allocate a new node and hold the pointer to it in a variable. Return from the insert
function now signaling an error if the new node cannot be allocated.
2. Store the information in the newly created node.
3. Make the newly created node point to null.
4. Make the old rear node point the newly created node.
5. Make rear point to the newly created node.

Full and Empty Operations:

Checking for an empty queue checks to see if either the front or the rear points to null.
Checking for a full queue should always return false.

Delete an element:
 1. If the queue is empty, return a flag indicating that removal could not be performed.

2. Save the pointer to the current front node.

3. Make front point to the next node.

4. If the queue is now empty, the rear must be set to null.

5. Save the information in the old front node.

6. Free the old front node.

7. Return the information that was in the front node.

d. Examples of use in algorithms (Lee algorithm)

The Lee algorithm is one possible solution for maze routing problems. It always gives an
optimal solution, if one exists, but is slow and requires large memory for dense layout.

Understanding how it works

The algorithm is a breadth-first based algorithm that uses queues to store the steps. It

usually uses the following steps:

1. Choose a starting point and add it to the queue.

2. Add the valid neighboring cells to the queue.

3. Remove the position you are on from the queue and continue to the next element.

4. Repeat steps 2 and 3 until the queue is empty.

One key concept to understand is that breadth-first searches go wide, while depth-

first searches go deep.

Using the example of a maze solving algorithm, a depth-first approach will try every
possible path one by one until it either reaches a dead end or the finish and returns the
result. However, the path it returns might not be the most efficient, but simply the first
complete path to the finish that the algorithm was able to find.

A breadth-first search will instead go out to each open space adjacent to the starting
point, then look for other possible open spaces. It will keep doing this, going out layer by
layer and trying each possible path in tandem, until it finds the finish point. Since you're
trying each path at the same time, you can be sure that the first complete path from
start to finish is also the shortest.

C++ has the queue already implemented in the <queue> library, but if you are using
something else you are welcome to implement your own version of queue.

C++ code:

int dl[] = {-1, 0, 1, 0}; // these arrays will help you travel in the 4 directions more easily
int dc[] = {0, 1, 0, -1};

queue<int> X, Y; // the queues used to get the positions in the matrix

X.push(start_x); //initialize the queues with the start position

 Y.push(start_y);

void lee()
{
int x, y, xx, yy;
while(!X.empty()) // while there are still positions in the queue
{
x = X.front(); // set the current position
y = Y.front();
for(int i = 0; i < 4; i++)
{
xx = x + dl[i]; // travel in an adiacent cell from the current position
yy = y + dc[i];
if('position is valid') //here you should insert whatever conditions should apply for
your position (xx, yy)
{
X.push(xx); // add the position to the queue
Y.push(yy);
mat[xx][yy] = -1; // you usually mark that you have been to this position in the
matrix
}

X.pop(); // eliminate the first position, as you have no more use for it
Y.pop();
}
}

11. Dynamic memory allocation in C. Linear data structures: stack

a. Properties of the stack data structure

Stack is a LIFO (Last-In, First-Out) list, a list-like structure in which elements may be
inserted or removed from only one end (last-in, first-out). Stacks are less flexible than
lists, but are easier to implement, and more efficient (for those operations they can do).

Given a stack, the accessible element of the stack is called the top element.

Elements are not said to be inserted; they are pushed onto the stack.

When an element (the last one) is removed, an element is said to be popped from the
stack.
b. Stack structure

c. Stack operations

 push() − Pushing (storing) an element on the stack.

o Step 1 – Create a new node, pointing to null.
o Step 2 – Point the new node to the top node of the stack
o Step 3 – Actualize the top node to be the new node.
 pop() − Removing (accessing) an element from the stack.
o Step 1 − Checks if the stack is empty.
o Step 2 − If the stack is empty, produces an error and exit.
o Step 3 − If the stack is not empty, accesses the data element at which top is
pointing.
o Step 4 – Point a variable I to the node and actualize the Top to point to the
previous node.
o Step 5 – Point the *next pointer of node I to null and delete node I from the
memory.
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full.
 isEmpty() − check if stack is empty.

d. Examples of use in algorithms (addition of long numbers)

Given two numbers N1 and N2 represented by two stacks, such that their most
significant digits are present at the bottom of the stack, the task is to calculate and
return the sum of the two numbers in the form of a stack.

1. Create a new stack, res to store the sum of the two stacks.

2. Initialize variables rem and sum to store the carry generated and the sum of top
elements respectively.

3. Keep popping the top elements of both the stacks and push the sum % 10 to res and
update rem as sum/10.
 4. Repeat the above step until the stacks are empty. If rem is greater than 0,
insert rem into the stack.

5. Reverse the res stack so that the most significant digit present at the bottom of
the res stack.

Example:

Input:  N1={5, 8, 7, 4}, N2={2, 1, 3} 

Output:  {6, 0, 8, 7}
Explanation:
Step 1: Popped element from N1(=  4) +   Popped element from N2(= 3) = {7} and rem=0.
Step 2: Popped element from N1(= 7) +   Popped element from N2(= 1) = {7, 8} and
rem=0.
Step 3: Popped element from N1(= 8) +   Popped element from N2(= 2) = {7, 8, 0} and
rem=1.
Step 4: Popped element from N1(= 5) = {7, 8, 0, 6}
On reverse the stack, the desired arrangement {6,0,8,7} is obtained.

Input: N1={6,4,9,5,7}, N2={213} 

Output:{6, 5, 0, 0, 5}

12. Dynamic memory allocation in C. Linear data structures: lists

a. The structure of dynamically allocated lists

A linked list is an ordered collection of nodes, each of which contains some data,
connected using pointers.

Each node points to the next node in the list.

The first node in the list is called the head.

The last node in the list is called the tail.

A linked list can only be accessed sequentially. To find the 5th element, for instance, you
must start from the head and follow the links through four other nodes.

b. List properties, list types

 Ordered List:

 Every node has an ID. When adding a new node in the list, we need to find firstly the
idea of the next node from the one we want to add and do the operation. This way
the list remains ordered.
 When deleting the node, you search it by it’s ID and then extract it from the least,
before destroying it, otherwise you may lose half of the list.

Unordered List:

 Doesn’t differ any much from what a queue or a stack is. The nodes are added either
to the front or to the back of the list.
 When deleted, you can either erase the first node, the last one or find the one with
the information you want to delete from the list, extract it and erase it from the
memory.

Properties:

Each element in the list points to the next element. That’s how they hold together.
Imagine a bunch of children, which have names and are holding with the left hand the
right shoulder of the next child. The information are their names, the pointer to the next
child are their left hand. If you break one of the connections, you lose al the nodes (kids)
after the broken connection. For example, if you have the list “ABCDEFG” and you break
the connection between “C” and “D”, you lose the sublist “DEFG”.

c. List operations

Adding a node between 2 nodes:

 Step 1: Create the new node, pointing to null, and insert the information in it.
 Step 2: Find in the list the node A before which you want to add the new node, and
the node B, which is after A. Generate an error if you don’t find the points.
 Step 3: Point the *next pointer of your new node to B.
 Step 4: Point the *next pointer of A to your new node.

Adding a node at the top of the list:

 Step 1: Create the new node, pointing to null, and insert the information in it.
 Step 2: Point the *next pointer of your new node to the top node.
 Step 3: Actualize the top node, which is your new variable.
Adding a node at the bottom of the list:
 Step 1: Create the new node, pointing to null, and insert the information in it.
 Step 2: Find the bottom node, knowing that it’s pointer *next points to null.
 Step 3: Point the *next pointer of the bottom node to your new node.
Erasing a node between 2 nodes:
 Step 1: Find in the list the node before the one with the information you want to
erase. If you can’t find it, generate an error message.
 Step 2: Point the *next pointer of the node to the *next pointer of the next node of
the one you want to delete.
 Step 3: Point the *next pointer of the node you want to delete to null.
 Step 4: Erase the node from the memory.

Deleting a node at the top of the list:

  Step 1: Actualize the TOP node, which is the next node of the one you want to
delete.
 Step 2: Point the *next pointer of the node you want to delete to null. Erase the
node from memory.
Deleting a node at the bottom of the list:
 Step 1: Find the bottom node, knowing that it’s pointer *next points to null.
 Step 2: Point the *next pointer of the previous node to null. Erase your node from
the memory.

d. Examples of use in algorithms (searching in unordered strings)

Couldn’t find anything on the internet. But, the operation is simple. Read the elements
of the string, transform them to nodes and add to the list in ordered form (only if the
order of the character in the string does not actually matter, otherwise, just add the
nodes to the top), search through the list by ID and that’s all.

Practice:

15. Describe the operation of conversion from string to integer

int stringTointeger(string str)

{
    int temp = 0;
    for (int i = 0; i < str.length(); i++) {
  
        // Since ASCII value of character from '0'
        // to '9' are contiguous. So if we subtract
        // '0' from ASCII value of a digit, we get 
        // the integer value of the digit.
temp = temp * 10 + (str[i] - '0');
// ASCII of number x – ASCII of 0 = number x
    }
    return temp;
}

16. GCD (Greatest Common Divisor) between 2 numbers. Euclid’s algorithm

Pseudo Code of the Algorithm-

Step 1: Let a, b be the two numbers

Step 2: a mod b = R

Step 3: Let a = b and b = R

Step 4: Repeat Steps 2 and 3 until a mod b is 0

Step 5: GCD = b

Step 6: Finish

function gcd(a, b) {
var R;
while ((a % b) > 0) {
R = a % b;
 a = b;
b = R;
}
return b;
}
17. Algorithm for checking whether a number is prime or composite

 Step 1: If 0,1 or 2, they are prime.

 Step 2: Iterative, from 2 to n/2, if n mod i == 0, then it’s not prime. Stop.

if (n == 0 || n == 1 || n == 2) {
isPrime = false;
}
else {
for (i = 2; i <= n / 2; ++i) {
if (n % i == 0) {
isPrime = false;
break;
}
}
}
if (isPrime)
cout << n << " is a prime number";
else
cout << n << " is not a prime number";

18. Algorithm for generating the first N prime numbers ???

19. Babylonian algorithm for extracting the square root

1. Select a precision level e (for example, 0.00001).

2. Initiate x=N and y=1.
3. While |x-y|/|x| > e, repeat x=(x+y)/2, y=N/x.
4. The result is x.

float sqRoot(float N) {

   float x = N, y = 1;              //initial guess as number and 1

   float precision = 0.000001;           //the result is correct

upto 0.000001

   while(abs(x - y)/abs(x) > precision) {

      x = (x + y)/2;
       y = N/x;

   }

   return x;

20. Algorithm for decomposition of a number into separate digits

Let d be the digit and N the number. d = N mod 10. N = N div 10. Write d, repeat until N=0.
while (number > 0)
{
int digit = number % 10;
number /= 10;
//print digit
}

21. Conversion of integer numbers in base 10 to another base

1. X is the number in base 10, b is the new base, i=0 and S is an empty string. While x>0
repeat steps 2 and 3;
2. R is the reminder of X/b. Add to S the (R+’0’).
3. Increase i by one, divide X by b.
4. Result is 0. Iterative, form the last element of S down to the first one, multiply the result
to 10 and add the number from string to it. That’s the answer.
int From10toB (int number, int b)

int i=0, x=number, rem=0;

String S;

while (x>0) {

rem=x % b;

S[i]=rem + ’0’;

i++;

x \= b;

};

int result=0;

for (int j=S.length(); j>0; j--) result=result * 10 + (S[i] –‘0’);

return result;

Theory
13. Dynamic memory allocation in C. Functions for dynamic memory allocation:
 a. calloc ()
b. malloc ()
c. realloc ()
d. free ()
Dynamic Memory Allocation is manual allocation and freeing of memory
according to your programming needs. Dynamic memory is managed and served with
pointers that point to the newly allocated memory space in an area which we call the
heap.
a) C malloc()
The name malloc stands for "memory allocation". It is a function which is used to
allocate a block of memory dynamically. It reserves memory space of specified size and
returns the null pointer pointing to the memory location. The pointer returned is usually
of type void. It means that we can assign C malloc() function to any pointer
Syntax of malloc()
ptr = (cast-type*) malloc(byte-size).
Here, ptr is pointer of cast-type.
The malloc() function returns a pointer to an area of memory with size of byte size. If
the space is insufficient, allocation fails and returns NULL pointer.

b) C Calloc()
The C calloc() function stands for contiguous allocation. This function is used to allocate
multiple blocks of memory. It is a dynamic memory allocation function which is used to
allocate the memory to complex data structures such as arrays and structures.
Malloc() function is used to allocate a single block of memory space while the calloc() in C
is used to allocate multiple blocks of memory space. Each block allocated by the calloc()
function is of the same size and also calloc() sets all bytes to zero.
Syntax of calloc()
ptr = (cast-type*) calloc (n, element-size);

d) C free()
Dynamically allocated memory created with either calloc() or malloc() doesn't get freed
on its own. We must explicitly use free() to release the space.
Syntax of free()
free(ptr);
This statement frees the space allocated in the memory pointed by ptr.

c) C realloc()
Using the C realloc() function, we can add more memory size to already allocated
memory. It expands the current block while leaving the original content as it is. Realloc() in
C stands for reallocation of memory.
Realloc() can also be used to reduce the size of the previously allocated memory.
Syntax of realloc()
ptr = realloc(ptr, newsize);
Here, ptr is reallocated with size of newsize.

14. Recursion in C:
a. The notion of recursive approach
b. The structure of the recursive function
d. Example. Recursive fibonacci numbers calculation / analysis

a) The process in which a function calls itself directly or indirectly is called recursion
and the corresponding function is called a recursive function. Using recursive
algorithm, certain problems can be solved quite easily. Recursion cannot be applied to
all the problems, but it is more useful for the tasks that can be defined in terms of
similar subtasks. For example, recursion may be applied to sorting, searching, and
traversal problems.
b) The recursive functions should be used very carefully because, when a function
called by itself it enters into the infinite loop. And when a function enters into the
infinite loop, the function execution never gets completed. We should define the
condition to exit from the function call so that the recursive function gets terminated.
When a function is called by itself, the first call remains under execution till the last call
gets invoked. Every time when a function call is invoked, the function returns the
execution control to the previous function call.
Example: Sum of Natural Numbers Using Recursion

#include <stdio.h>
int sum(int n);

int main() {
int number, result;

printf("Enter a positive integer: ");

scanf("%d", &number);

result = sum(number);

printf("sum = %d", result);

return 0;
 }

int sum(int n) {
if (n != 0)
// sum() function calls itself
return n + sum(n-1);
else
return n;
}

Output

Enter a positive integer:3

sum = 6

Initially, the  sum()  is called from the  main()  function with  number  passed as an argument.
Suppose, the value of  n  inside  sum()  is 3 initially. During the next function call, 2 is passed
to the  sum()  function. This process continues until  n  is equal to 0.
When  n  is equal to 0, the  if  condition fails and the  else  part is executed returning the sum
of integers ultimately to the  main()  function.
c) Fibonacci series is a series of numbers formed by the addition of the preceding two
numbers in the series. The first two terms are zero and one respectively. The terms after
this are generated by simply adding the previous two terms.
The base case for finding factorial
fibonacci(0) = 0
fibonacci(1) = 1
General case for finding factorial
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Algorithm:- fibonacci(n)

if (n<=1)
then return n
else
return fibonacci(n-1) + fibonacci(n-2)

Program that finds first N numbers in Fibonacci series:

#include<stdio.h>
int fibonacci(int n)
{
if(n<=0)
return n; //base case
else //general case
return fibonacci(n-1)+fibonacci(n-2);
}
int main()
{
int num;
printf("How many numbers of Fibonacci
series you want to print: ");
scanf("%d",&num);
printf("Fibonacci series:\n");
for(int i=0; i<num; i++)
{
printf("%d\t",fibonacci(i));
}
return 0;
}
 15. Pointers in C.
a. pointer data type
b. Addressing operation &
c. Pointers and arrays
d. Pointers and dynamic memory allocation

a) A pointer is a variable that stores the address of another variable. Unlike other
variables that hold values of a certain type, pointer holds the address of a variable. For
example, an integer variable holds (or you can say stores) an integer value, however an
integer pointer holds the address of an integer variable.
The general form of a pointer variable declaration is:
type *var-name;

Here, type is the pointer's base type; it must be a valid C data type and var-name is the
name of the pointer variable. When asterisk (*) is used in this manner in a definition, it
indicates that the variable being defined is a pointer. The asterisk notation used to
declare pointer variables does not distribute to all variable names in a declaration. Each
pointer must be declared with the * prefixed to the name.
Pointers should be initialized when they’re defined, or they can be assigned a value. A
pointer may be initialized to NULL, 0 or an address. A pointer with the value NULL
points to nothing. NULL is a symbolic constant defined in the <stdio.h>.
Initializing a pointer to 0 is equivalent to initializing a pointer to NULL, but NULL is
preferred. When 0 is assigned, it’s first converted to a pointer of the appropriate type.
The value 0 is the only integer value that can be assigned directly to a pointer variable.

A normal variable ‘var’ has a memory address of

1001 and holds a value 50.
A pointer variable has its own address 2047 but
stores 1001, which is the address of the variable
‘var’.

b) The &, or address operator, is a unary operator that returns the address of its operand.
After declaration of a pointer variable, we need to initialize the pointer with the valid
memory address; to get the memory address of a variable Address Of" (&) Operator is
used.

c) The interaction of pointers and arrays can be confusing but here are two fundamental
statements about it:
1) A variable declared as an array of some type acts as a pointer to that type. When used
by itself, it points to the first element of the array.
2) A pointer can be indexed like an array name.
The first case often is seen to occur when an array is passed as an argument to a
function. The function declares the parameter as a pointer, but the actual argument may
be the name of an array.
The second case often occurs when accessing dynamically allocated memory.
Pointers and array names can pretty much be used interchangeably; however, there are
exceptions. You cannot assign a new pointer value to an array name. The array name
will always point to the first element of the array.
It is also valid for a function to return a pointer to one of the array elements from an
array passed as an argument to a function. A function should never return a pointer to a
local variable, even though the compiler will probably not complain. When declaring
parameters to functions, declaring an array variable without a size is equivalent to
declaring a pointer. Often this is done to emphasize the fact that the pointer variable will
be used in a manner equivalent to an array.

d) Whenever we define a variable in C, the compiler automatically allocates the correct

amount of memory based on the data type that is declared.
However, it is frequently desirable to be able to dynamically allocate storage while a
program is running, e.g. if you want to change the value of, or concatenate to a string, or
if you have a program that is designed to read in a set of data from a file into an array in
memory. To allocate memory in C, there are three options:
1) define the array to contain the maximum possible number of elements at compile
time
2) use a variable-length array to dimension the size of the array at runtime (available
in the C99 standard)
3) allocate the array dynamically using the memory allocation routines available in
the C language
 Allocating memory dynamically allows you to create pointers at runtime that are just
large enough to hold the amount of data required for the task, and free it when no longer
needed - ideal from an efficiency perspective.
16. Pointers in C.
a. pointer data type
b. Pointers in structures
c. Pointers to arrays (2D arrays as linear structure)
d. Pointers in functions

a) (1) Void Pointer:

A void pointer is a pointer that has no associated data type with it. A void pointer can hold address
of any type and can be typcasted to any type.

int a = 10;
char b = 'x';
void *p = &a; // void pointer holds address of int 'a'
p = &b; // void pointer holds address of char 'b'
A void pointer does not have any data type associated with it.It can store address of any type of
variable.

(2) Dangling Pointer:

If any pointer is pointing to the memory address of any variable but after some time that variable
has deleted from the memory location while pointer is still pointing such memory location then such
pointer is called as Dangling pointer.

(3) NULL Pointer:

 Literal meaning of NULL pointer is a pointer which is pointing to nothing.

 NULL pointer points the base address of segment.

 In case, if you don’t have address to be assigned to pointer then you can simply use
NULL.
  Pointer which is initialized with NULL value is considered as NULL pointer.

(4) Near pointer :

 A pointer variable which can handle only one segment of 1MB data. It is called near
pointer

 Near pointer will handles only 1 segment i.e data segment only

 The size of the near pointer is “2” bytes.

(5) Far pointer :

 Which pointer variable can handle any segment of 1MB data, it is called far pointer.

 The size of the far pointer is 4 bytes.

(6) Wild Pointer or Bad pointer :

 Unintialized pointer variable or which pointer not initialized with any variable
address. It is called wild pointer

 Wild pointer is also called Bad pointer, because without assigning any variable
address , it points to the memory location.

b) Here's how you can create pointers to structs.

struct name {
member1;
member2;
.
.
};

int main()
{
 struct name *ptr, Harry;
}

Here,  ptr  is a pointer to  struct .

To access members of structure using the structure variable, we used the dot . operator.
But when we have a pointer of structure type, we use arrow -> to access structure
members.
#include <stdio.h>

struct my_structure {

char name[20];

int number;

int rank;

};

int main()

struct my_structure variable = {"StudyTonight", 35, 1};

struct my_structure *ptr;

ptr = &variable;

printf("NAME: %s\n", ptr->name);

printf("NUMBER: %d\n", ptr->number);

printf("RANK: %d", ptr->rank);

return 0;

c) int arr[3][4] = {
{11,22,33,44},
 {55,66,77,88},
{11,66,77,44}
};
The above 2-D array can be visualized as following:

The following figure shows how a 2-D array is stored in the memory:

A 2-D array is actually a 1-D array in which each element is itself a 1-D array. So arr is an
array of 3 elements where each element is a 1-D array of 4 integers.
In the above example, the type or base type of arr is a pointer to an array of 4 integers.
Since pointer arithmetic is performed relative to the base size of the pointer. In the case
of arr, if arr points to address 2000 then arr + 1 points to address 2016 (i.e 2000 + 4*4).
We know that the name of the array is a constant pointer that points to the 0th element of
the array. In the case of a 2-D array, 0th element is a 1-D array. So the name of the array in
case of a 2-D array represents a pointer to the 0th 1-D array. Therefore in this case arr is a
pointer to an array of 4 elements. If the address of the 0th 1-D is 2000, then according to
pointer arithmetic (arr + 1) will represent the address 2016, similarly (arr + 2) will
represent the address 2032.
From the above discussion, we can conclude that:
arr points to 0th 1-D array.
(arr + 1) points to 1st 1-D array.
(arr + 2) points to 2nd 1-D array.

d) It is possible to declare a pointer pointing to a function which can then be used as an

argument in another function. A pointer to a function is declared as follows:
type (*pointer-name)(parameter);

Here is an example :
int (*sum)(); //legal declaration of pointer to function

int *sum(); //This is not a declaration of pointer to

function

A function pointer can point to a specific function when it is assigned the name of that
function:
int sum(int, int);

int (*s)(int, int);

s = sum;

Here s is a pointer to a function sum. Now sum can be called using function

pointer s along with providing the required argument values:
s (10, 20);

Example of Pointer to Function:

#include <stdio.h>

int sum(int x, int y)

return x+y;

int main( )

int (*fp)(int, int);

 fp = sum;

int s = fp(10, 15);

printf("Sum is %d", s);

return 0;}

17. Operations in C.
a. Arithmetic operations
b. Relational operations
c. Logical operations
d. Priority of operations
a) Basic arithmetic operations include addition, subtraction, multiplication and
subtraction. They are performed on numerical data types like int, float and double.
Operator Description
+ Adds two operands.

- Subtracts second operand from the first.

* Multiplies both operands.

/ Divides numerator by de-numerator.

% Modulus Operator and remainder of after an integer division.

++ Increment operator increases the integer value by one.

-- Decrement operator decreases the integer value by one.

The operators +, - and * computes addition, subtraction, and multiplication respectively.

In normal calculation, for instance, 9/4 = 2.25. However, in a program the output is 2.
It is because both the variables are integers. Hence, the output is also an integer. The
compiler neglects the term after the decimal point and shows answer 2 instead of 2.25.
The modulo operator % computes the remainder. When, for example, 9 is divided by 4,
the remainder is 1. The % operator can only be used with integers.
Increment ++ increases the value by 1 whereas decrement -- decreases the value by 1.
These two operators are unary operators, meaning they only operate on a single
operand.

b) Relational operators are used to compare values of two expressions. Relational

operators are binary operators because they require two operands to operate. An
expression which contains the relational operators is called relational expression. If the
relation is true then the result of the relational expression is 1, if the relation is false then
the result of the relational expression is 0.
Operator Description
> Greater than.

>= Greater than or equal to.

< Smaller than.

<= Smaller than or equal to.

== Equal to.

!= Not equal to.

The precedence of <, <=, > and >= operators are same and they associate from left to
right. However, the precedence of == and != is lower than other relational operators and
they associate from left to right. The precedence of relational operators is lower than the
arithmetic operators.

c) Logical operators are used to evaluate two or more conditions. In General, Logical
operators are used to combine relational expressions, but they are not limited to just
relational expression you can use any kind of expression even constants. If the result of
the logical operator is true then 1 is returned otherwise 0 is returned.
 Operator Description

&& Called Logical AND operator. If both the operands are non-zero,
then the condition becomes true.
|| Called Logical OR Operator. If any of the two operands is
non-zero, then the condition becomes true.
! Called Logical NOT Operator. It is used to reverse the logical
state of its operand. If a condition is true, then Logical NOT
operator will make it false.

d)
Precedenc Operator Description Associativity
e
1 ++ -- Suffix/postfix increment and decrement
() Function call
[] Array subscripting
. Structure and union member access Left-to-right
-> Structure and union member access through
pointer
(type) {list} Compound literal
2 ++ -- Suffix/postfix increment and decrement
+- Unary plus and minus
! ~ Logical NOT and bitwise NOT
(type) Cast
* Indirection (dereference) Right-to-left
& Address-of
sizeof Size-of
_Alignof Alignment requirement

3 */% Multiplication, division, and remainder

4 +- Addition and subtraction
5 << >> Bitwise left shift and right shift
6 < <= For relational operators < and ≤ respectively
> >= For relational operators > and ≥ respectively
7 == != For relational = and ≠ respectively Left-to-right
8 & Bitwise AND
9 ^ Bitwise XOR (exclusive or)
10 | Bitwise OR (inclusive or)
11 && Logical AND
12 || Logical OR
13 ?: Ternary conditional
14 = Simple assignment
+= -= Assignment by sum and difference Right-to-left
*= /= %= Assignment by product, quotient, and
<<= >>= remainder
&= ^= |= Assignment by bitwise left shift and right shift
Assignment by bitwise AND, XOR, and OR
15 , Comma Left-to-right

Practice
22. Conversion of integer numbers in base b to base 10
Input number is given as string and output is an integer.

Input: str = "1100", base = 2

Output: 12

Input: str = "11A", base = 16

Output: 282

Input: str = "123", base = 8

Output: 83
We can always use the below formula to convert from any base to decimal:
"str" is input number as a string
"base" is the base of the input number.

Decimal Equivalent is,

1*str[len-1] + base*str[len-2] + (base) 2*str[len-3] + ...

23. Determining the element of maximal value (of minimal value) in the array
1) Let maxE and minE be the variable to store the minimum and maximum element of
the array.
2) Initialise minE as INT_MAX and maxE as INT_MIN.
3) Traverse the given array arr[].
4) If the current element is smaller than minE, then update the minE as current element.
5) If the current element is greater than maxE, then update the maxE as current element.
6) Repeat the above two steps for the element in the array.

24. Counting elements of the same value (of a given value)

1) Input size and elements in array from user. Store it in some variable, say size and arr.
2) Initialize another variable count with 0 to store duplicate count.
3) To count total duplicate elements in given array we need two loops. Run an outer
loop loop from 0 to size. Loop structure must look like for(i=0; i<size; i++). This loop is
used to select each element of array and check next subsequent elements for duplicates
elements using another nested loop.
4) Run another inner loop to find first duplicate of current array element. Run an inner
loop from i + 1 to size, the loop structure should look like for(j=i+1; j<size; j++). Now,
why run a loop from i + 1. Because we need to search for duplicate elements in next
subsequent elements, from current element.
5) Inside inner loop check for duplicate element. If duplicate element is found then
increment duplicate count. Which is if(arr[i] == arr[j]) then, count++. Also terminate
inner loop if duplicate element is found.

25. Counting max / min elements in one array traversal

To find the maximum value, you initialize a placeholder called max with the value of the
first element in the array. Then you go through the array element by element. If any
element is greater than max you replace max with that element. Here is the pseudocode:
SET Max to array[0]
FOR i = 1 to array length - 1
IF array[i] > Max THEN
SET Max to array[i]
ENDIF
ENDFOR
PRINT Max

In the same way we proceed to find the min elements.

26. Shifting the elements in an array by 1 position to the left.

1) Store the array size into the variable n.
2) Read the entered array and store the elements in the array a[].
3) Read the k value, which represents how many numbers of times left rotate the given
array (in our case k = 1).
4) Rotate the array to left for k times as follows, for loop iterates from i=0 to i<k
a) Assign starting element to temp.
b) Inner for loop iterates from j=0 to j<n-1
move a[j+1] to a[j].Repeat until j<n-1.
c) Assign temp to a[n-1]. Here we are assigning the first element to the last index.
Repeat these three steps until i<k.
4) After all iterations of i, print the array which is left rotated.

27. Shifting the elements from an array by 1 position to the right.

1) Read the array size and store the size into the variable n.
2) Read the entered elements and store the elements in the array a[] as
scanf(“%d”,&a[i]) using for loop.
3) Read the k value which represents how many times right rotate the array (in our case
k = 1).
4) Right, rotate the array up to k times as follows
for loop iterates from i=0 to i<k
a) Store the last element into the variable temp.
b) Inner for loop iterates from j=n-1 to j>0
move the a[j-1] to a[j],repeat until j>0.
c) Initialize the temp value to a[0].
Repeat these three steps until i<k.
5) After completion of the 4th step, we will get the right rotated array.

28. Shifting the elements from an array by k positions to the right

1) Read the array size and store the size into the variable n.
2) Read the entered elements and store the elements in the array a[] as
scanf(“%d”,&a[i]) using for loop.
3) Read the k value which represents how many times right rotate the array.
4) Right, rotate the array up to k times as follows
for loop iterates from i=0 to i<k
a) Store the last element into the variable temp.
b) Inner for loop iterates from j=n-1 to j>0
move the a[j-1] to a[j],repeat until j>0.
c) Initialize the temp value to a[0].
Repeat these three steps until i<k.
5) After completion of the 4th step, we will get the right rotated array.

Bit operations in C

1) Logical bit operations

1=true 0=false
a. & and
if a=0 , b=0 , a&b=0 because a=b but a is false
if a=1 , b=0 , a&b=0 because a<>b
if a=0 , b=1 , a&b=0 because a<>b
if a=1 , b=1 , a&b=1 because a=b

b. | or
If a=0 , b=0 , a|b=0 because above are false
If a=1 , b=0 , a|b=1 because a is true
If a=0 , b=1 , a|b=1 because b is true
If a=1 , b=1 , a|b=1 because above are true
c. ^ exclusive or , it means just 1 should be true
If a=0 , b=0 , a^b=0 because above are false
If a=1 , b=0 , a|b=1 because just one is true
If a=0 , b=1 , a|b=1 because just one is true
If a=1 , b=1 , a|b=0 because above are true
d. ~ complement, all 0 becomes 1 and 1 becomes 0
A=00111001
~A=11000110
Take a=10 , 10/2=5 r=0
5/2=2 r=1
2/2=1 r=0
1/2=0 r=1
 A=01010
~A=10101
~a=-11
2) Bit movement operations
<< , >> shift operators , it moves all bits to the left or right and in empty cells put 0
A=60
a=00111100
a>>2 = 00001111=15
a<<2 = 11110000=240
3) Setting the value of bit k , it set the bit with number k to be equal with 1.
Lets take a=56
a=111000
if a has 6 bit => 0<=k<6
because we start to count with 0 from the right and k should be smaller then number of bits
let set the 2-nd bit 2 1 0
111000
if k=2 a=111100
if k=4 a=111000 because 4th bit has already set
4) Fast calculation 2k
The most efficient is the example with bit transformation
For example :
A124
124 -> (01111100)2
Now we take 2position of bit if this bit is equal with 1 and sum them .
(01111100)2 ->26+25+24+23+22
A124=A2^6 * A2^5 *A2^4 *A2^3 *A2^2

TEXT FILES

1) The structure of a text file

A text file is an array of chars that has at the end marker \0 , that means the end of array , also
called end marker
2) Accessing files from C programs
We can do this using ,

fopen( “name of file with extension .txt” , “ a variable “)

it can create or open an existing file with name you write in box

fclose(“name of file with extension .txt” , “ a variable “)

it closing a file

getc , fprintf and fscanf works similarly like scanf and printf but with files
3) Riding data from a text file
fscanf(….
4) Writing data in a text file
fprintf(….

Array data type

 1) The notion of array
An array is a data structure that contains a group of elements. Typically these elements are
all of the same data type, such as an integer or string. Arrays are commonly used in
computer programs to organize data so that a related set of values can be easily sorted or
searched. Arrays can be unidimensional bidimensional and so on till k dimensional
2) Operations or linear arrays
They are similar with operations that you can do with variables with same data type
For int : + , - , * , / , % , pow

3) Multidimensional arrays
Arrays can be unidimensional bidimensional and so on till k dimensional
a[ ]
a[ ] [ ]
…
4) Memory allocation models for arrays
For each element of array is allocated standard memory for its data type
For example
Integer 4 bite
Char 1 bite
Double 8 bite

Representation of numbers in the memory of digital devices

1) Representation of unsigned integers

Unsigned integers can represent zero and positive integers, but not negative integers. The value
of an unsigned integer is interpreted as "the magnitude of its underlying binary pattern".

2) Representation of signed integers

In sign-magnitude representation: The most-significant bit is the sign bit, with value of
0 representing positive integer and 1 representing negative integer. The remaining n-1 bits
represents the magnitude of the integer.
3) Direct, inverse, complementary code
Direct code is just a bit sequence
In front of each bit sequence is 0 or 1 , 0 means that number is positive , 1 that it is negative
Inverse code  the symbol bit is unchanged, and the remaining bits are reversed , only for
negative bit sequence . The positive do not change their structure
Example :
[1]=[00000001](direct code )
[00000001](inverse code)
[-1]=[10000001](direct code )
[11111110](inverse code )
Complementary code the symbol bit is unchanged, and the remaining bits are reversed , and
added 1 to the last bit , only for negative bit sequence . The positive do not change their
structure
[1]=[00000001](direct code )
[00000001](inverse code)
[-1]=[10000001](direct code )
[11111110](inverse code )
[11111110]+[00000001]=[11111111]( complementary code )

Information and data

1) Information is organized or classified data, which has some meaningful values for the receiver.
Information is the processed data on which decisions and actions are based
2) Digitalization of information
Digitization is the process of converting information into a digital. The result is the
representation of an object, image, sound, documents or signal by generating a series of
numbers that describe a discrete set of points or samples. The result is called digitalization of
information or, more specifically, a digital image , for the object, and digital form, for the signal.
In modern practice, the digitized data is in the form of binary numbers (binary code , 0 and 1
sequences ), which facilitate processing by digital computers and other operations, but, strictly
speaking, digitizing simply means the conversion of analog source material into a numerical
format; the decimal or any other number system that can be used instead.
3) Data is bit sequences that was or need to be processed by computer .
4) Binary codes A binary code represents text, computer processor instructions, or any other data
using a two-symbol system. The two-symbol system used is often "0" and "1" from
the binary number system. The binary code assigns a pattern of binary digits, also known as bits,
to each character, instruction, etc.

Practice:
Problem 29

Shifting the elements from an array by k positions to the left.

Int m ; //variabila ajutatoare

Int n; // numarul de elemente in array

for(int i=0;i<k;i++)

for(int j=0;j<n;j++) if (j==0){ m=a[j] ; a[j]=a[j+1];} else if (j==n-1) a[j]=m; else a[j]=a[j+1];
 problem 30

bubble sort

int m;

for(int i=0;i<n-1;i++)

for(int j=0;j<n-1;j++) if (a[j]>a[j+1){m=a[j] ; a[j] = a[j+1] ; a[j+1]=m;}

problem 31

selection sort

int m , n, k , z;

m=0;

for (int i=0;i<k;i++)

for(int j=0;j<n;j++) if (a[j] >a[m])m=j;

z=a[n+1];

a[n+1]=a[m];

a[m]=z;

m=0;

n--;

Problem 32

Insertion sort

Int m;

for (int i=1;i<n;i++)

for(int j=0; j<i,i++) if(a[j] > a[i])

m=a[i];

for (int k=i ; k>j; k--) a[k]=a[k-1];

a[j]=m;

break ; }

problem 33

Determining the longest sequence of numbers equal to each other from an array
 int m=0, k =0, j=0;

for (int i=0;i<n;i++) if (a[i]==j)k++;

else

{ j=a[i];

If (m<k)m=k;

K=0;

Problem 34

Determining the longest sequence of increasing numbers from an array

int m=0, k =0, j=0;

for (int i=1;i<n;i++) if (a[i]==j+1){k++;j++;}

else

{ j=a[i];

If (m<k)m=k;

K=0;

Problem 35

The number of “hills” from an array (The element A[i] is called “hill” if it’s bigger than

A[i-1] and A[i+1])

Int m=0;

For (int i=1;i<n-1;i++) if (a[i]>a[i-1] && a[i]>a[i+1])m++;