Brief Course outline

• Review of data structure and programming concepts
• Asymptotic notations;
• Recursion and recurrence relations;
• Calculating running time of recusive algorithms
• Divide-and-conquer approach;
• Sorting;
• Greedy approach;
• Dynamic programming;
• String matching;
• NP complete problems;
• Approximation algorithms;
• And few more topics…

Introduction to Algorithms

• Algorithm
• Named after a Muslim mathematician, Al-Khawarzmi

  (عَبْدَالله مُحَمَّد بِن مُوسَى اَلْخْوَارِزْمِي)

• Algorithm is a well defined computational procedure that takes some value (s) as input, and produces some value (s) as output.

Data structures

Data structures let the input and output be represented in a way that can be handled efficiently and effectively.

Example

• Data structure for storing data of students:-
• Arrays
• Linked Lists
• Issues
• Space needed
• Operations efficiency (Time required to complete operations)
• Retrieval
• Insertion
• Deletion

What is Program?

• Operations are associated with data structure
• To perform these operations algorithms are needed

Data structures +Algorithms=Programs

Good Algorithms?

• Run in less time
• Consume less memory

But computational resources (time complexity) is usually more important

Simple Example (1)

// Input: int A[N], array of N integers

// Output: Sum of all numbers in array A

int Sum(int A[], int N)

{

int s=0;

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

s = s + A[i];

return s;

}

How should we analyse this?

Simple Example (2)

1,2,8: Once

3,4,5,6,7: Once per each iteration

of for loop, N iteration

Total: 5N + 3

The complexity function of the

algorithm is : f(N) = 5N +3