Programming for Problem

Solving
[Link] D. Gadade
Dept. of Computer Science and Engg.
COEP Technological University, Pune
 Data Structures Files and Algorithms
SN Particulars Marks

1 Mid Sem 30
Total Marks = 100
2 TA (Teacher Assessment) 20 Total Credits = 03
a) Surprise Test 10 Marks
b) Quiz 10 Marks
c) Performance 10 Marks
d) Attendance 10 Marks
e) Other 10 Marks each
____________________________________
Total Marks will be converted to 20 Marks

3 End Sem Exam 50

Total 100

2
Dr. Harish D. Gadade, COEP Technological University, Pune
 Introduction
● Data
● Data Type
● Abstract Data Types
● Algorithms
● Characteristics of Algorithm
● Analyzing Problems/Algorithms
● Asymptotic Notations

3
Dr. Harish D. Gadade, COEP Technological University, Pune
 Data
● Data is a collection of raw facts and figures that by themselves may not
have much meaning, but can be processed to produce information.
● Examples
○ Numbers: 25, 100, 3.14
○ Text: Harish, India
○ Symbols: @, #
○ Records: student marks, phone numbers, attendance lists
● Types of data
○ Numeric data – numbers (age, marks, salary)
○ Text data – words or sentences (names, addresses)
○ Image data – photos, scanned documents
○ Audio/Video data – sound recordings, videos
4
Dr. Harish D. Gadade, COEP Technological University, Pune
 Data Types
● Data Types define the kind of data a variable can hold/store.
● Data Types specify the type of data a variable can store and the operations
that can be performed on it.

Data Types

Non Primitive/Derived Data Types

Primitive / Basic Data Types
● Array
● Integer(int)
● String
● Character(char)
● Structure
● Float/Real
● Class/Object
● Boolean (bool)
● Pointer

5
Dr. Harish D. Gadade, COEP Technological University, Pune
 Abstract Data Types
Data Abstract Data Type (ADT) is a logical or conceptual model that defines a
data type in terms of

● The set of values it can hold, and

● The operations that can be performed on it,

without specifying the internal representation of data or the implementation

details in memory.

Abstract data types (ADTs) are a way of encapsulating data and operations on
that data into a single unit.

6
Dr. Harish D. Gadade, COEP Technological University, Pune
 Algorithms
● Algorithm is a set of finite, well-defined steps or instructions designed to
solve a problem.
● It can also be defined as a procedure for solving a mathematical or
computational problem in a finite number of steps, often involving
repetitive or recursive operations.
● Characteristics
○ Input 1. Start
○ Output 2. Define variables like num1,
○ Finiteness num2, sum
○ Clear and Unambiguous 3. Read two numbers like num1 and
○ Language Independent num2
○ Feasible 4. Perform addition like
sum=num1+num2
5. Print sum
6. stop

7
Dr. Harish D. Gadade, COEP Technological University, Pune
 Analyzing Problems/Algorithms
● Algorithm Analysis is the theoretical, Priori assessment of an algorithm’s
performance, rather than posterior testing.
● Algorithmic efficiency is measured through two types of complexities.
○ Time Complexity
○ Space Complexity
● Types of Analysis
○ Worst Case Analysis
○ Best Case Analysis
○ Average Case Analysis
● The Mathematicians and Computer Scientists use specific notations called
Asymptotic Notations, to describe growth rate of an Algorithms
○ Big ‘O’ Notation
○ Omega ‘Ώ’ Notation
○ Theta ‘Θ’ Notation

8
Dr. Harish D. Gadade, COEP Technological University, Pune
 Asymptotic Notations
1. Big ‘O’ Notation
● O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n)
≤ cg(n) for all n ≥ n0 }

● Big-O notation represents the upper bound of the running time of an

algorithm. Therefore, it gives the worst-case complexity of an
algorithm.
9
Dr. Harish D. Gadade, COEP Technological University, Pune
 Asymptotic Notations
1. Omega ‘Ώ’ Notation
● Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤
cg(n) ≤ f(n) for all n ≥ n0 }

● Omega notation represents the lower bound of the running time of an

algorithm. Thus, it provides the best case complexity of an algorithm

10
Dr. Harish D. Gadade, COEP Technological University, Pune
 Asymptotic Notations
1. Theta ‘Θ’ Notation
● Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that
0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}

● Big-O notation represents the upper bound of the running time of an

algorithm. Therefore, it gives the worst-case complexity of an
algorithm.
11
Dr. Harish D. Gadade, COEP Technological University, Pune