DSE 513
Programming,
Data Structures
and Algorithms
What is relation between: Programming, Data
Structures and Algorithms
ANY IDEA? EXAMPLES
Data Structure:
• Structure that holds data:
Correct data structure for your
needs.
• 𝑥 2 + 2𝑦 − 2 = 1
• Holding data: placeholder
• Messed room: find bike key
• Advice: Right place, next time
get stuff easily.
• Arrange and keep everything in such a
structure: search for something you get that
easily and as soon as possible.
• Some way of storing are efficient than
others.
Data structures enable us to store and organize data in order to facilitate access and modifications
Data Organization
• Help Structure your data in efficient
way
• Trillion GB, process it and use it easily
• Example: In library, find a book on Set
Theory
• Way we organize information on our
computers.
• Way to arrange data in main
memory
• Computer scientists process and
look for the best way we can
organize the data
It can be better processed based on the input provided
Data type
• System defined/Primitive data types
• Derived data types
• Structure
• Classes
• Linear vs non-linear
• Accessed and stored in a non-linear order
Algorithms
• Step-by-step procedure for solving
a problem
• Approach use to perform any
operation in data
• Independent of programming
• Write first; Idea of how to solve it.
Then write actual code
• Data Structure: Ingredients for
making efficient algorithm
Data structures: organise and store data.
Algorithms enable us to process that data in a meaningful sense.
Prepare tea
Properties
• Step by step procedure of solving a problem
• Computational procedure
• Input to output
• Finite amount of time
• One problem, different solution
• Finiteness, effectiveness (no intelligence needed to apply),
Definiteness
Types of Algo
• Iterative: sequentially execute input
• Loops, conditional statement
• Linear search
• Recursive
• Recursively break large problem to small
• Solve these problem
• Combine: Solution to main problem
Programming
• Algorithm + Data-Structure
• Data Structures and Algorithms
are building blocks of
programming.
• Understood and executed by a
computer
Goal: Learning various decision science
procedures and solution algorithms.
• Algorithm design
Content of • Comparison
the course • Complexity
• Data Structure
• Arrays and Matrices
• Stacks and Queues
• Trees and Graphs
• Insertion, deletion, search, traversal
• Programming
• Sorting
• Search structure
• Non-Linear Data Structure
Google
Amazon FB
• Highest number of users
• Store, manipulate,
process
• Most efficient solution
• More optimization needs
to be done
• Compare one Data
Structure to other: Array,
Linked list -Insertion
Facebook
• How they manage data in backend
• Graph:
• Mutual friend
• Strongly connected component in graph
• Whatsapp
• Queue
• Send first, delivered first
Data Structure
• Help Structure your data in efficient way
• Word in the dictionary, Approach?
• page by page? or
• open some page and if the word is not found you open a page prior
to/later to one opened depending upon the order of words to the
current page.
Algorithm
• Search your roll number in a pdf file: 20,000 pages (roll numbers: in increasing order)
• Algorithm 1: Randomly?
• Algorithm 2: In a sequential manner it will take too much time….Naaa
• Algorithm 3:
• Go to page no. 10000
• Not there, but all other roll no. in that page are lesser than your then
• Go to page no. 15000
• Still if your roll no. is not there. but this time all other roll no. is greater than your.
• Go to page no. 12500
• Continue the same process and within 30-40 seconds you will find your roll number: Binary Search
Meaning of Log
Complexity
• Suppose you are working in Amazon.
• Sorting a list of orders from India
• Huge saving in terms of server cost and time.
• Hire a smart developer who can make the right decision and save company
resources, time, and money.
• Optimal solution of a problem:
• Use a Hash table instead of List to solve a specific problem
• Ola, Uber: Complete business on Algo
• Real Life Problem: XYZ company, reduce computational time
Optimization: Trade-off
In a Nutshell
• Significance of data management
• Specific structure helpful in saving a
lot of time
• becomes easier to manipulate
or use them.
• Same goes for the algorithm
• Save time, energy and resources.
Optimization: Trade-off
Mathematical Modeling
Example: Furniture Dealer
Rs 50,000
At most 60 pieces
Parameters Description
Cost 2500 Rs Cost 500 Rs
Profit 250 Rs Profit 75 Rs
Decision: how many tables and chairs to buy from the available mone
Assuming that he can sell all the items which he buy
Iterative way
Combination
Only tables Only chairs
of both
Cost 2500 Cost 500 10 table 50 chair
Profit 250 Profit 75 Maximum space: 60
Maximum space: 60 Maximum space: 60
Profit: 5000 Profit: 4500 Profit: 6250
Three steps for Mathematical Modelling
FORMULATION SOLUTION INTERPRETATION &
SENSITIVITY ANALYSIS
Formulation
10 table 50 chair
Combination
of both Maximum space:
60
Details Table Chair
Cost 2500 500
Profit 250 75
Cost(10,50)=2500*10+500*50
Profit(10,50)=250*10+75*50
Steps In Formulation
1. Decision Variable
2. Parameters: 3 types {A, B, C}
3. Constraints
4. Objective function
• A furniture dealer deals in only two items–tables and chairs. He
has Rs 50,000 to invest and has storage space of at most 60
pieces. A table costs Rs 2500 and a chair Rs 500. He estimates that
from the sale of one table, he can make a profit of Rs 250 and that
from the sale of one chair a profit of Rs 75. He wants to know how
many tables and chairs he should buy from the available money so
as to maximise his total profit, assuming that he can sell all the
Problem items which he buys.
Statement • *NCERT Class 12th
Redraw Table
Details Table Chair
Cost 2500 500
Profit 250 75
Resource Table (x1) Chair (x2) Available
Money 2500 500 50,000
Space 1 1 60
Unit Profit 250 75
Algorithm
An algorithm is the step-by-step unambiguous
instructions to solve a given problem.
Sequence of step to solve given problem.
Write an algo to find sum of elements in an array
The variable sum will be
Declare and initialize an used to calculate the
array. sum of the elements.
Sum of Initialize it to 0.
Elements in
an Array Loop through the array
and add each element
of array to variable sum
as sum = sum + arr[i].
Python
1.#Initialize array
[Link] = [1, 2, 3, 4, 5]
[Link] = 0
4.
5.#Loop through the array to calculate sum of elements
[Link] i in range(0, len(arr)):
7. sum = sum + arr[i]
8.
[Link](‘Sum of all the elements of an array: ’,sum);
Java
public class SumOfArray {
public static void main(String[] args) {
//Initialize array
int [] arr = new int [] {1, 2, 3, 4, 5};
int sum = 0;
//Loop through the array to calculate sum of elements
for (int i = 0; i < [Link]; i++) {
sum = sum + arr[i];
}
[Link]("Sum of all the elements of an array: " + sum);
}
}
C
• #include <stdio.h> • //Calculate length of array arr
• int length = sizeof(arr)/sizeof(arr[0]);
• int main() •
• //Loop through the array to calculate sum of elements
• {
• for (int i = 0; i < length; i++) {
• //Initialize array • sum = sum + arr[i];
• }
• int arr[] = {1, 2, 3, 4, 5}; • printf("Sum of all the elements of an array: %d", sum);
• int sum = 0; • return 0;
• }
Algorithm Linear
Search
Algorithm Linear Search
Algorithm: Linear Search
• The steps used in the implementation of Linear Search are
listed as follows -
• First, we have to traverse the array elements using a for loop.
• In each iteration of for loop, compare the search element with
the current array element, and -
• If the element matches, then return the index of the
corresponding array element.
• If the element does not match, then move to the next
element.
• If there is no match or the search element is not present in the
given array, return -1.
Class Assignment:
Find maximum Print Odd
number in an Numbers in an
array array
• Declare and initialize an array.
• The variable max is used to determine the largest element
in the array
• Initialize max with the first element: initially, to start the
comparison.
Find max in an •Loop over given array from second element till end, and
array for each element: range(1,len(arr))
• Compare the current element with max
• If the current element is greater than max,
then replace the value of max with the current
element. If arr[i]>max; max=arr[i]
•Return and print the value of the largest element of
array max.
Print Odd Numbers in an array?
Correctness: does the
algorithm give solution to the
problem in a finite number of
steps?
Analysis of
Algorithm Efficiency: how much
resources (in terms of
memory and time) does it
take to execute
Whose Algo is better and How much it is better: number of steps to give solution
Why AoA?
• Mode Choice: Depending on the
availability and convenience, we choose
the one that suits us.
• CS: Multiple algorithms are available for
solving the same problem
• a sorting problem: insertion sort, selection
sort, quick sort and many more.
• AoA: algorithm most efficient in terms of time
and space consumed.
• mainly in terms of running time but also in terms
of other factors (e.g., memory, developer effort)
Complexity
5 km
My Home Friend’s Home
Speed: 250 kbps Speed: 250 kbps
Need a file from your friend 100 MB file size
1 MB file size
Algo 1: 4 sec Algo 1: * sec
Algo 1: Internet
Algo 2: constant time (15mins) Algo 2: constant time (15mins)
Algo 2: Physical visit
Find @what file size, I need to chose which Algo
Algo 1: as Input size increases, RT changes.
Write expression for both Algo
Algo 2 Input RT? Algo 1: Input RT?
Constant time: Input>> RT same Linear time
Time Complexity
Quadratic:
Exponential: Cubic: matrix
shortest path
2n multiplication
b/w 2 nodes
Why Important
Ola, Uber: Complete business on Algo. Like: Game
theory
How much time it will take to give output
Algo 1, Algo 2, Algo 3: Chose 1
Most efficient in term of time and space consumed
Running Time Analysis
• How processing time increases as the size of the
problem (input size) increases.
• Input size is the number of elements in the input,
and depending on the problem type, the input may
be of different types.
• The following are the common types of inputs.
• Size of an array
• Polynomial degree
• Number of elements in a matrix
• Number of bits in the binary representation of
the input
• Vertices and edges in a graph.
Compare Algorithms
• Execution times?
• Specific to a particular computer.
• Number of statements executed?
• Varies with the programming language
• style of the individual programmer.
• What to do?
• Express running time as a function of the input size n
(i.e., f(n)) and compare these different functions
corresponding to running times.
• Independent of machine time, programming style, etc.
What is Rate of
Growth:
• The rate at which the running time
increases as a function of input.
• How RT is scaling with input
• Example:
• Buy a car and a bicycle
• What you are buying, then in general
you say buying a car.
• Total cost=cost of car+ cost of bicycle
• Total cost~cost of car
• n4 +2n2 +100n+500: only consider n4
Ignore lower order terms, for higher value of n
Commonly Used Rates
of Growth
Worst case
Role of • Defines the input for which the algorithm takes a long time
(slowest time to complete).
Input: Type • Input is the one for which the algorithm runs the slowest.
of Analysis Best case
• Defines the input for which the algorithm takes the least time
Happening in life of Algo (fastest time to complete).
Array={1,5,7,9,24} • Input is the one for which the algorithm runs the fastest.
Input: a
Average case
compare a with all
best case: k • Provides a prediction about the running time of the algorithm.
worst case: nk • Run the algorithm many times, using many different inputs that
come from some distribution that generates these inputs,
average case: ? All compute the total running time (by adding the individual times),
possible run time/number and divide by the number of trials.
of possibility • Assumes that the input is random
Class Exercise: Find ISOCHRONE for this
5 km
My Home Friends Home
Speed: 250 kbps Speed: 250 kbps
Need a file from your friend 100 MB file size
1 MB file size
Algo 1: 4 sec Algo 1: * sec
Algo 1: Internet
Algo 2: constant time (15mins) Algo 2: constant time (15mins)
Algo 2: Physical visit
Find @what file size, I need to chose which Algo
Algo 1: as Input size increases, RT changes.
Write expression for both Algo
2 days classes instead of 3
days
Class Wednesday: 12:00-1:25 PM &
Thursday: 03:00-04:30 PM
timings
Will see in due course if some
other time is also possible