Data Structures with Object Oriented Programming Language

      Functions    Abstract Data Types  Class   Arrays   Pointers    Structures   Linked List   Stacks     Queues  Trees     Sorting Techniques      DST Practicals   Mini Projects

2.5.6.Detailed Syllabus as per 5th revised curriculum of A level

(i) Object Oriented Concepts

Object Oriented Programming- a new paradigm, Abstraction, forms of Abstraction, OOP concepts- Classes, Objects, Polymorphism, Data Encapsulation, Data Hiding, Inheritance,

(ii)Basics of C++, Classes and Objects

Features of C++, Tokens, keywords, Data types, Operators, Manipulators, Console input, output, Control statements (conditional and loops), Functions, Classes, Instantiation, Destructor, constructor, Polymorphism - Operator Overloading, Function Overloading, Inheritance-Single, Multiple, Multilevel, Pointers

(iii) Analysis of Algorithm

Introduction to algorithm design and Data structures, Comparison of Algorithms, Complexity in terms of space and time, Calculation of O- notation. Abstract Data type and its implementation with a Rational number example

(iv) Searching and Sorting

Searching- Linear and Binary Search, Sorting- Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Comparison of various searching and sorting techniques in terms of time complexity

(v) Elementary Data Structures: Arrays, Linked Lists

Representation of arrays-single and multidimensional, Address calculation using row major ordering, Various operations on arrays, Linked Lists-Singly Linked List, Double linked List, Circular Linked List- traversing, deleting, inserting, searching, counting, reversing, printing of nodes.

(vi) Stacks and Queues

Stack ADT, Implementation of stack using array and linked list, Application of Stack- Evaluation of postfix/prefix expression, Queue ADT, Implementation of queue using Array and Linked List

(vii) Trees

Definition and notations, Binary Search Trees Implementation. Traversals using stacks and recursion - In-order, post-order, pre-order techniques, Threaded binary tree, B-trees with implementation of 2-3 trees.

(viii) Graphs

Definition and notations, Components of Graphs, Types of Graphs, Graph Implementation using Adjacency Matrix and Adjacency List algorithms and programs, Graph Traversal Methods: Depth First Search and Breadth First Search.

 21-02-23

1 Installation and configuration of codeblocks (GCC compiler)

2. Concepts discussed as below: (PPT: Intro to C++ till slide no 20)

Algorithm
Programming languages - High level / low level
Introduction to C++, Variables, constants, naming rules, Declaring variables, assigning values
Case Sensitive, Single line comment / multi line comment.
Data type: int, char, float
Practicals: Basic introduction to the codeblock IDE interface

EX001: WAP to print tabular output with three data rows
SNO         Name                Date of birth
1
2
3

EX002: WAP to input radius of a circle and print circumference and area of circle


Operators in C++: Operators in C++ can be classified into 6 types:

  1. Arithmetic Operators
  2. Assignment Operators
  3. Relational Operators
  4. Logical Operators
  5. Bitwise Operators
  6. Other Operators

1. C++ Arithmetic Operators
Arithmetic operators are used to perform arithmetic operations on variables and data. For example,

a + b;
Here, the + operator is used to add two variables a and b. Similarly there are various other arithmetic operators in C++.

Operator Operation
+ Addition
- Subtraction
* Multiplication
/ Division
% Modulo Operation (Remainder after division)

Increment and Decrement Operators
C++ also provides increment and decrement operators: ++ and -- respectively.

++ increases the value of the operand by 1
-- decreases it by 1

2. C++ Assignment Operators
In C++, assignment operators are used to assign values to variables. For example,

// assign 5 to a
a = 5;
Here, we have assigned a value of 5 to the variable a.

Operator               Example Equivalent to
=                            a = b; a = b;
+=                            a += b; a = a + b;
-=                    a -= b; a = a - b;
*=                            a *= b; a = a * b;
/=                    a /= b; a = a / b;
%=                            a %= b; a = a % b;

3. C++ Relational Operators
A relational operator is used to check the relationship between two operands. For example,

// checks if a is greater than b
a > b;
Here, > is a relational operator. It checks if a is greater than b or not.

If the relation is true, it returns 1 whereas if the relation is false, it returns 0.

Operator Meaning Example
== Is Equal To 3 == 5 gives us false
!= Not Equal To 3 != 5 gives us true
> Greater Than 3 > 5 gives us false
< Less Than 3 < 5 gives us true
>= Greater Than or Equal To 3 >= 5 give us false
<= Less Than or Equal To 3 <= 5 gives us true

4. C++ Logical Operators
Logical operators are used to check whether an expression is true or false. If the expression is true, it returns 1 whereas if the expression is false, it returns 0.

Operator Example Meaning
&& expression1 && expression2 Logical AND.
True only if all the operands are true.
|| expression1 || expression2 Logical OR.
True if at least one of the operands is true.
! !expression Logical NOT.
True only if the operand is false.

5. C++ Bitwise Operators
In C++, bitwise operators are used to perform operations on individual bits. They can only be used alongside char and int data types.

Operator Description
& Binary AND
| Binary OR
^ Binary XOR
~ Binary One's Complement
<< Binary Shift Left
>> Binary Shift Right

6. Other C++ Operators
Here's a list of some other common operators available in C++. 

Operator  Description                                              Example
sizeof  returns the size of data type                         sizeof(int); // 4
?:          returns value based on the condition       string result = (5 > 0) ? "even" : "odd"; // "even"
&          represents memory address of the operand &num; // address of num
.          accesses members of class objects         s1.marks = 92;
->          used with pointers to access the class     ptr->marks = 92;
<<          prints the output value                               cout << 5;
>>          gets the input value                              cin >> num;

Flow Control: 
In computer programming, we use the if...else statement to run one block of code under certain conditions and another block of code under different conditions.

For example, assigning grades (A, B, C) based on marks obtained by a student.

if the percentage is above 90, assign grade A
if the percentage is above 75, assign grade B
if the percentage is above 65, assign grade C
There are three forms of if...else statements in C++.

if statement
if...else statement
if...else if...else statement

Example: 
// Program to print positive number entered by the user
// If the user enters a negative number, it is skipped

#include <iostream>
using namespace std;

int main() {

  int number;

  cout << "Enter an integer: ";
  cin >> number;

  // checks if the number is positive
  if (number > 0) {
    cout << "You entered a positive integer: " << number << endl;
  }

  cout << "This statement is always executed.";

  return 0;
}

Example: if..else statement
// Program to check whether an integer is positive or negative
// This program considers 0 as a positive number

#include <iostream>
using namespace std;

int main() {

  int number;

  cout << "Enter an integer: ";
  cin >> number;

  if (number >= 0) {
    cout << "You entered a positive integer: " << number << endl;
  }
  else {
    cout << "You entered a negative integer: " << number << endl;
  }

  cout << "This line is always printed.";

  return 0;
}

C++ Nested if...else
Sometimes, we need to use an if statement inside another if statement. This is known as nested if statement. Think of it as multiple layers of if statements. There is a first, outer if statement, and inside it is another, inner if statement. 

Example:
// C++ program to find if an integer is positive, negative or zero
// using nested if statements

#include <iostream>
using namespace std;

int main() {

  int num;
    
  cout << "Enter an integer: ";  
   cin >> num;    

  // outer if condition
  if (num != 0) {
        
    // inner if condition
    if (num > 0) {
      cout << "The number is positive." << endl;
    }
    // inner else condition
    else {
      cout << "The number is negative." << endl;
    }  
  }
  // outer else condition
  else {
    cout << "The number is 0 and it is neither positive nor negative." << endl;
  }

  cout << "This line is always printed." << endl;

  return 0;
}

Loops:
In computer programming, loops are used to repeat a block of code.

For example, let's say we want to show a message 100 times. Then instead of writing the print statement 100 times, we can use a loop.

There are 3 types of loops in C++.

for loop
while loop
do...while loop

For Loop
Example: Printing Numbers From 1 to 50
#include <iostream>

using namespace std;

int main() {
        for (int i = 1; i <= 50; ++i) {
        cout << i << " ";
    }
    return 0;
}

Example 2: Display a text 5 times
// C++ Program to display a text 5 times

#include <iostream>

using namespace std;

int main() {
    for (int i = 1; i <= 5; ++i) {
        cout <<  "Hello World! " << endl;
    }
    return 0;
}

Example 3: Find the sum of first n Natural Numbers
// C++ program to find the sum of first n natural numbers
// positive integers such as 1,2,3,...n are known as natural numbers

#include <iostream>

using namespace std;

int main() {
    int num, sum;
    sum = 0;

    cout << "Enter a positive integer: ";
    cin >> num;

    for (int i = 1; i <= num; ++i) {
        sum += i;
    }

    cout << "Sum = " << sum << endl;

    return 0;
}

C++ Infinite for loop
If the condition in a for loop is always true, it runs forever (until memory is full). For example,

// infinite for loop
for(int i = 1; i > 0; i++) {
    // block of code
}
In the above program, the condition is always true which will then run the code for infinite times.

while loop

Example 1: Display Numbers from 1 to 50
// C++ Program to print numbers from 1 to 50

#include <iostream>

using namespace std;

int main() {
    int i = 1; 

    // while loop from 1 to 50
    while (i <= 50) {
        cout << i << " ";
        ++i;
    }
    
    return 0;
}

Example 2: Sum of positive numbers till a negative(sentinel value) is entered
// program to find the sum of positive numbers
// if the user enters a negative number, the loop ends
// the negative number entered is not added to the sum

#include <iostream>
using namespace std;

int main() {
    int number;
    int sum = 0;

    // take input from the user
    cout << "Enter a number: ";
    cin >> number;

    while (number >= 0) {
        // add all positive numbers
        sum += number;

        // take input again if the number is positive
        cout << "Enter a number: ";
        cin >> number;
    }

    // display the sum
    cout << "\nThe sum is " << sum << endl;
    
    return 0;
}

C++ do...while Loop
The do...while loop is a variant of the while loop with one important difference: the body of do...while loop is executed once before the condition is checked.

Note: the break statement terminates the loop when it is encountered.
Example:
// program to print the value of i

#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 5; i++) {
        // break condition     
        if (i == 3) {
            break;
        }
        cout << i << endl;
    }

return 0;
}

output: 
1
2

The continue statement is used to skip the current iteration of the loop and the control of the program goes to the next iteration.

// program to print the value of i

#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 5; i++) {
        // condition to continue
        if (i == 3) {
            continue;
        }

        cout << i << endl;
    }

    return 0;
}

output:
1
2
4
5

The switch statement allows us to execute a block of code among many alternatives.
// Program to build a simple calculator using switch Statement
#include <iostream>
using namespace std;

int main() {
    char oper;
    float num1, num2;
    cout << "Enter an operator (+, -, *, /): ";
    cin >> oper;
    cout << "Enter two numbers: " << endl;
    cin >> num1 >> num2;

    switch (oper) {
        case '+':
            cout << num1 << " + " << num2 << " = " << num1 + num2;
            break;
        case '-':
            cout << num1 << " - " << num2 << " = " << num1 - num2;
            break;
        case '*':
            cout << num1 << " * " << num2 << " = " << num1 * num2;
            break;
        case '/':
            cout << num1 << " / " << num2 << " = " << num1 / num2;
            break;
        default:
            // operator is doesn't match any case constant (+, -, *, /)
            cout << "Error! The operator is not correct";
            break;
    }

    return 0;
}

Practicals
Practical Practice Questions:

1. Write a program in C++ to print a welcome text. 
2. Write a program in C++ to print the sum of two numbers. 
Sample Output:
Print the sum of two numbers :
-----------------------------------
The sum of 29 and 30 is : 59
3. Write a program in C++ to find size of fundamental data types. 
Sample Output:
Find Size of fundamental data types :
------------------------------------------
The sizeof(char) is : 1 bytes
The sizeof(short) is : 2 bytes
The sizeof(int) is : 4 bytes
The sizeof(long) is : 8 bytes
The sizeof(long long) is : 8 bytes
The sizeof(float) is : 4 bytes
The sizeof(double) is : 8 bytes
The sizeof(long double) is : 16 bytes
The sizeof(bool) is : 1 bytes

4. Write a program in C++ to print the sum of two numbers using variables. 
Sample output: The sum of 29 and 30 is : 59

5. Write a program in C++ to check the upper and lower limits of integer. 
Expected Output:
Check the upper and lower limits of integer :
--------------------------------------------------
The maximum limit of int data type : 2147483647
The minimum limit of int data type : -2147483648
The maximum limit of unsigned int data type : 4294967295
The maximum limit of long long data type : 9223372036854775807
The minimum limit of long long data type : -9223372036854775808
The maximum limit of unsigned long long data type : 18446744073709551615
The Bits contain in char data type : 8
The maximum limit of char data type : 127
The minimum limit of char data type : -128
The maximum limit of signed char data type : 127
The minimum limit of signed char data type : -128
The maximum limit of unsigned char data type : 255
The minimum limit of short data type : -32768
The maximum limit of short data type : 32767
The maximum limit of unsigned short data type : 65535

7. Write a program in C++ to display various type or arithmetic operation using mixed data type. 
Sample output:
Display arithmetic operations with mixed data type :
---------------------------------------------------------
5 + 7 = 12
3.7 + 8.0 = 11.7
5 + 8.0 = 13.0
5 - 7 = -2
3.7 - 8.0 = -4.3
5 - 8.0 = -3.0
5 * 7 = 35
3.7 * 8.0 = 29.6
5 * 8.0 = 40.0
5 / 7 = 0
3.7 / 8.0 = 0.5
5 / 8.0 = 0.6

9. Write a program in C++ to display the operation of pre and post increment and decrement. 
Sample Output:
Display the operation of pre and post increment and decrement :
--------------------------------------------------------------------
The number is : 57
After post increment by 1 the number is : 58
After pre increment by 1 the number is : 59
After increasing by 1 the number is : 60
After post decrement by 1 the number is : 59
After pre decrement by 1 the number is : 58
After decreasing by 1 the number is : 57

10. Write a program in C++ to formatting the output. 
Sample Output:
Formatting the output :
----------------------------
The value of pi : 3.1416
The value of pi 4 decimal place of total width 8 : | 3.1416|
The value of pi 4 decimal place of total width 10 : | 3.1416|
The value of pi 4 decimal place of total width 8 : |--3.1416|
The value of pi 4 decimal place of total width 10 : |----3.1416|
The value of pi in scientific format is : 3.1416e+00
Status in number : 0
Status in alphabet : false

12. Write a program in C++ to add two numbers accept through keyboard. 
Sample Output:
Sum of two numbers :
-------------------------
Input 1st number : 25
Input 2nd number : 39
The sum of the numbers is : 64

13. Write a program in C++ to swap two numbers. 
Sample Output:
Swap two numbers :
-----------------------
Input 1st number : 25
Input 2nd number : 39
After swapping the 1st number is : 39
After swapping the 2nd number is : 25

14. Write a program in C++ to calculate the volume of a sphere. 
Sample Output:
Calculate the volume of a sphere :
---------------------------------------
Input the radius of a sphere : 6
The volume of a sphere is : 904.32

15. Write a program in C++ to calculate the volume of a cube. 
Sample Output:
Calculate the volume of a cube :
---------------------------------------
Input the side of a cube : 5
The volume of a cube is : 125

16. Write a program in C++ to calculate the volume of a cylinder. 
Sample Output:
Calculate the volume of a cylinder :
-----------------------------------------
Input the radius of the cylinder : 6
Input the height of the cylinder : 8
The volume of a cylinder is : 904.32

17. Write a program in C++ to find the Area and Perimeter of a Rectangle. 
Sample Output:
Find the Area and Perimeter of a Rectangle :
-------------------------------------------------
Input the length of the rectangle : 10
Input the width of the rectangle : 15
The area of the rectangle is : 150
The perimeter of the rectangle is : 50

18. Write a program in C++ to find the area of any triangle using Heron's Formula. 
Sample Output:
Find the area of any triangle using Heron's Formula :
----------------------------------------------------------
Input the length of 1st side of the triangle : 5
Input the length of 2nd side of the triangle : 5
Input the length of 3rd side of the triangle : 5
The area of the triangle is : 10.8253

19. Write a program in C++ to find the area and circumference of a circle. 
Sample Output:
Find the area and circumference of any circle :
----------------------------------------------------
Input the radius(1/2 of diameter) of a circle : 5
The area of the circle is : 78.5397
The circumference of the circle is : 31.4159

20. Write a program in C++ to convert temperature in Celsius to Fahrenheit. 
Sample Output:
Convert temperature in Celsius to Fahrenheit :
---------------------------------------------------
Input the temperature in Celsius : 35
The temperature in Celsius : 35
The temperature in Fahrenheit : 95

21. Write a program in C++ to convert temperature in Fahrenheit to Celsius. 
Sample Output:
Convert temperature in Fahrenheit to Celsius :
---------------------------------------------------
Input the temperature in Fahrenheit : 95
The temperature in Fahrenheit : 95
The temperature in Celsius : 35

22. Write a program in C++ to find the third angle of a triangle. 
Sample Output:
Find the third angle of a triangle :
-----------------------------------------
Input the 1st angle of the triangle : 30
Input the 2nd angle of the triangle : 60
The 3rd of the triangle is : 90

23. Write a program in C++ that converts kilometers per hour to miles per hour. 
Sample Output:
Convert kilometers per hour to miles per hour :
----------------------------------------------------
Input the distance in kilometer : 25
The 25 Km./hr. means 15.5343 Miles/hr.

30. Write a program in C++ to compute the total and average of four numbers. 
Sample Output:
Compute the total and average of four numbers :
----------------------------------------------------
Input 1st two numbers (separated by space) : 25 20
Input last two numbers (separated by space) : 15 25
The total of four numbers is : 85
The average of four numbers is : 21.25

31. Write a program in C++ to input a single digit number and print a rectangular form of 4 columns and 6 rows. 
Sample Output:
Make a rectangular shape by a single digit number :
--------------------------------------------------------
Input the number : 5
5555
5     5
5     5
5     5
5     5
5555

32. Write a program in C++ to check whether a number is positive, negative or zero. 
Sample Output:
Check whether a number is positive, negative or zero :
-----------------------------------------------------------
Input a number : 8
The entered number is positive.

34. Write a C++ program to display the current date and time. 
Sample Output:
Display the Current Date and Time :
----------------------------------------
seconds = 57
minutes = 33
hours = 12
day of month = 6
month of year = 7
year = 2017
weekday = 4
day of year = 186
daylight savings = 0
Current Date: 6/7/2017
Current Time: 12:33:57

35. Write a program in C++ to compute the specified expressions and print the output. 
Sample Output:
Compute the specified expressions and print the output:
------------------------------------------------------------
Result of the expression (25.5 * 3.5 - 3.5 * 3.5) / (40.5 - 4.5) is : 2.13889

38. Write a program in C++ that takes a number as input and prints its multiplication table upto 10. 
Sample Output:
Print the multiplication table of a number upto 10:
--------------------------------------------------------
Input a number: 5
5 x 1 = 5
5 x 2 = 10
5 x 3 = 15
5 x 4 = 20
5 x 5 = 25
5 x 6 = 30
5 x 7 = 35
5 x 8 = 40
5 x 9 = 45
5 x 10 = 50


42. Write a language program in C++ which accepts the user's first and last name and print them in reverse order with a space between them. 
Sample Output:
Print the name in reverse where last name comes first:
-----------------------------------------------------------
Input First Name: Anita
Input Last Name: Mahajan
Name in reverse is: najahaM atina

43. Write a language program which accepts the radius of a circle from the user and compute the area and circumference. 
Sample Output:
Find the area and circumference of any circle :
----------------------------------------------------
Input the radius(1/2 of diameter) of a circle : 5
The area of the circle is : 78.5397
The circumference of the circle is : 31.4159

Ref:https://www.w3resource.com/cpp-exercises/basic/index.php