2023-08-30

in Assignments use python sorting packages.

7 todos left.

What is algorithm?

Set of computational steps, that transforms input to output.

remark

There needs input (or not), and output is a must.

properties

Algorithm needs to be

• definite: each steps should be meaningful

• finite: should be finished at some point.

• effective : it has to do the task effectively.

What problems does Algorithms solve?

• routing algorithms

• search engines

• public key cryptography

• maximizing profit

• et cetra

What is different from Data structure class?

-	data structure	algorithms
Definition	way to organize data	procedure for performing task
#todo : difference between data structure and algorithms

needs good data structure knowledge in order to build a good algorithms. It will help.

Caution

Needs data structure knowledge after finals.

Algorithms - Sorting

• insertion, selection, bubble, shell, merge, heap, quick, quick3

algorithms-sorting

How do you say one algorithm is better than the other?The number of primitive operations needed. We express with big-O notation.

Big-O notation

mathematical notation used to classify algorithms according to how their run time grow as the input size grows.

ex1. get_first_number function needs 1 operation : constant : O(1) ex2. summation function needs n operation : O(n) ex3. Sequential search : n operation : O(n), linear time complexity ex4. Binary search(just like we search on dictionary) : log n operation : O(log n) ex5. brute force : O(n!), worst.

caution. we can only use binary search only when the input is sorted. In other words, input is sorted beforehand.

memo. runtime complexity, space complexity

Comparison between Big-O notations

Big-O notations

Insertion Sort

Find a spot and shift. for each unsorted data array, we choose where to insert in the sorted data array.

this alg. divides data into two parts: sorted and unsorted.

compare with each sorted data backwards (biggest first). if the sorted datum is bigger, shift to right. else if the sorted datum is smaller, put the target to the place.

insertion sort

#todo : implement pseudocode. #todo : implement code.

time complexity : $O(n^2)$

#todo : how to prove?

Merge Sort

divide and conquer

What is Divide and Conquer?

you divide problem into multiple subproblems.

remark subproblems should be the similar problem of the bigger one. divide and conquer is recursive in nature.

steps.

Divide : divide problem into smaller subproblems. Conquer : when the subproblem is small enough, solve in straight-forward manner. Combine : obtain bigger solution with smaller solutions.

#todo : implement merge sort pseudocode. #todo : implement python code.

time complexity : $O(n*log(n))$

#todo : how to prove?