EC9600: Applied Algorithm
Introduction to Algorithms I
Department of Computer Engineering
Faculty of Engineering
University of Jaffna
Mr Nishankar S
BSc Eng (Hons)
About this Course
★ 2 Credit Course
★ Yeah, this course is about Programming :)
★ No Labs, Assignments (Java), May be a small project.
★ Prerequisites: EC4070 Data Structures and Algorithms.
★ Optional Goal/Challenge: 100 Leetcode questions (No marks).
Learning Outcomes
★ Describe real world applications of algorithms;
★ Perform exploratory analysis for solution space search;
★ Explain game theory as a mechanisms to achieve efficient and desirable
global outcomes in spite of the selfish behaviour;
★ Comprehend the use and the difference between localized algorithms as
opposed to centralized algorithms.
Revision on Algorithms
★ Simple sorting algorithms
★ Searching Algorithms
★ Complexity of the Algorithms
★ Correctness of the Algorithms
Why Sorting & Searching
★ They are simple, yet quite useful operations.
★ Most problems come down to sorting and searching.
★ Examples:
○ Sorting Marks of Students
○ Words in dictionary
Bubble Sort
Algorithm (one possible version):
1. Start with the last item,
2. compare it with the previous item and if the previous item is large, swap the current item and the
previous.
3. Move to the next
4. Continue from step 2 until you have reached the first item, now the smallest item will be in the 1st
position.
5. Start at the last item, and repeat step 2 through to 4, until you reach the 2nd item, now the 2nd smallest
item will be in the 2nd position
6. Repeat until all the item are in order.
Bubble Sort
public void bubble_sort(int [] data) {
int i,j;
for(i=0; i < data.length; i++) {
for(j = data.length-1; j > i; j--) {
if(data[j] < data[j-1]) {
int tmp = data[j];
data[j] = data[j-1];
data[j-1] = tmp;
} // end if
} // for(j= …
} // for(i=...
}
Optimization
static void buble_sort_opt(int [] data) {
boolean quit = false;
for(int i=0; i<data.length && !quit; i++) {
quit = true;
for(int j=data.length-1; j > i; j--) {
if(data[j] < data[j-1]) {
int tmp = data[j];
data[j] = data[j-1];
data[j-1] = tmp;
quit = false;
}
Selection Sort
Write the
Pseudo
Code/Java Code
Selection Sort
Comparing Algorithms
1. Why?
Time & Storage
2. How?
The Random Access Model (RAM)
★ Simple operations (ex: +, ==, =) takes one time
step,
★ Each memory access takes one time step (ex: no
cache),
★ Loops and subroutines are collections of simple
operations
We can calculate how many steps
the algorithm will take based on the
arrangement of the data.
Best, Average , & Worst Cases
★ After the exams how do you calculate your marks?
○ How many marks will I get in the worst-case scenario?
★ Big(O) : Analyse the algorithm performance for Worst Case
○ f(n)=O(g(n)) if ∃c>0, and n0 such that f(n)≤c⋅g(n) for all n≥n0
★ Big(Ω): Analyse the algorithm performance for Best Case
○ f(n)=Ω(g(n)) if ∃c>0, and n0 such that f(n)≥c⋅g(n) for all n≥n0
★ Big(Θ): Analyse the algorithm performance for Average Case
○ f(n)=Θ(g(n)) if ∃c1,c2>0, and n0 such that c1⋅g(n)≤f(n)≤c2⋅g(n) for all n≥n0
Exercise
1. T(n)=7n+10
2. T(n)=5n^2+3n+8
3. T(n)=4logn+6
4. T(n)=3n+5n
5. T(n)=10nlogn+2n
Complexity Graphs
Complexity of Bubble sort
Bubble Sort Bubble Sort with optimization
Complexity of Selection sort
Insertion Sort
Comparison
Advanced Sorting Algorithms
★ Quick Sort
★ Merge Sort
★ Heap Sort
Searching Algorithms
★ Searching on Linear Dataset
○ Linear Search
○ Binary Search
Linear Search
Binary Search
