Scribd
Upload
14 views

Chap 1 - Introduction To Algorithms

Uploaded by

tahmidkabirp01814
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views

Chap 1 - Introduction To Algorithms

Uploaded by

tahmidkabirp01814
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

‭CSE 221: Algorithms [ARN] Ariyan Hossain‬

‭Introduction to Algorithms‬
I‭nformally, an algorithm is any well-defined computational procedure that takes some value, or‬
‭set of values, as input and produces some value, or set of values, as output in a finite amount of‬
‭time. An algorithm is thus a sequence of computational steps that transform the input into the‬
‭output.‬

‭Let us consider the problem of preparing an omelet. To prepare, we follow these steps:‬

‭ ) Get the frying pan.‬


1
‭2) Get the oil.‬
‭a. Do we have oil?‬
‭i. If yes, put it in the pan.‬
‭ii. If no, do we want to buy oil?‬
‭1. If yes, then go out and buy.‬
‭2. If no, we can terminate.‬
‭3) Turn on the stove, etc...‬

‭ n algorithm for a computational problem is correct if every problem instance provided as input‬
A
‭halts or finishes its computing in finite time and outputs the correct solution to the problem‬
‭instance.‬

‭There are two main criteria for judging the merits of algorithms:‬

‭●‬ C ‭ orrectness (does the algorithm give a solution to the problem in a finite number of‬
‭steps?)‬
‭●‬ ‭Efficiency (how much resources in terms of memory and time) does it take to execute‬
‭the).‬

‭ efinition:‬‭A finite set of statements that guarantees‬‭an optimal solution in a finite interval of‬
D
‭time‬

‭Examples of real-life algorithms:‬

i‭) The internet allows people all over the world to easily and quickly access a lot of information.‬
‭Smart algorithms help websites manage this huge amount of data by finding the best paths for‬
‭the data to travel. They also use search engines to quickly find pages that contain specific‬
‭information.‬

i‭i) You need to compress a large file containing text to occupy less space. Algorithms such as‬
‭Huffman coding allow you to store with fewer bits.‬

‭1‬
‭CSE 221: Algorithms [ARN] Ariyan Hossain‬

‭Follow-up Question:‬

‭ ) Other than speed, what other measures of efficiency might you need to consider in a‬
Q
‭real-world setting?‬

‭Ans: Number of people required to carry out a single task.‬

‭Algorithm Specification:‬

‭ ‬ I‭nput - Every Algorithm must take zero or more number of input values from external.‬
●
‭●‬ ‭Output - Every Algorithm must produce an output as a result.‬
‭●‬ ‭Definiteness - Every statement/instruction in an algorithm must be unambiguous (only‬
‭one interpretation)‬
‭●‬ ‭Finiteness - For all different cases, the algorithm must produce results within a‬
‭●‬ ‭finite number of steps.‬
‭●‬ ‭Effectiveness - Every Instruction must be basic enough to be carried out and it‬
‭also must be feasible.‬

‭To analyze algorithms, we need to predict the amount of resources required:‬

‭‬ M
● ‭ emory: how much space is needed?‬
‭●‬ ‭Computational time: how fast the algorithm runs‬

‭ unning Time:‬‭The running time of an algorithm refers to the amount of time it takes for the‬
R
‭algorithm to complete its execution, given an input.‬

‭ unning time grows with the size of the input. The input size is the number of elements in the‬
R
‭input eg. size of an array, no. of elements in a matrix, vertices, and edges in a graph.‬
‭Running time = the number of primitive operations (steps) executed before termination such as‬
‭arithmetic operations (+,-), and decision-making (if, while).‬

I‭f computers were infinitely fast and had infinite memory, any correct method for solving a‬
‭problem would do. You would probably want your implementation to be within the bounds of‬
‭good software engineering practice (for example, your implementation should be well-designed‬
‭and documented), but you would most often use whichever method was the easiest to‬
‭implement‬

‭ ifferent algorithms that solve the same problem often differ dramatically in their efficiency (not‬
D
‭only due to differences between hardware and software). For example, two sorting algorithms:‬
‭2‬
‭insertion sort takes time roughly equal to c‬‭1‭n
‬ ‬ ‭to sort n items whereas merge sort takes c‬‭2‬‭nlgn.‬
‭When n is very large, the time difference between the algorithms is significant. There are more‬
‭than 100 million web searches every half hour, and more than 100 million emails sent every‬
‭minute, hence it is important to use an efficient algorithm.‬

‭2‬

You might also like