COT 5407: Introduction to AlgorithmsWhy should I care about Algorithms?More questions you should askWhy are theoretical results useful?Slide 5Self-IntroductionStudent Self-IntroductionWhat this course is aboutCourse LogisticsEvaluationAlgorithmSome Well-known Computational ProblemsHistory of AlgorithmsEuclid’s AlgorithmBasic Issues Related to AlgorithmsAlgorithm design strategiesAnalysis of AlgorithmsCorrectnessAmount of Work DoneMoreAsymptotic Growth Rates of FunctionsNotationsOther mathematical backgroundWhy study algorithms?Two main issues related to algorithmsSlide 26Analysis of algorithmsImportant problem typesFundamental data structuresSearchSlide 31PolynomialsSlide 3301/14/19 COT 5407 1COT 5407: Introduction to AlgorithmsTao LiECS 318; Phone: [email protected]://www.cs.fiu.edu/~taoli/class/COT5407-F09/index.html8/28/07 COT 5407 2Why should I care about Algorithms?Cartoon from Intractability by Garey and Johnson8/28/07 COT 5407 3More questions you should ask•Who should know about Algorithms?•Is there a future in this field? •Would I ever need it if I want to be a software engineer or work with databases?8/28/07 COT 5407 4Why are theoretical results useful? Cartoon from Intractability by Garey and Johnson8/28/07 COT 5407 5Why are theoretical results useful? Cartoon from Intractability by Garey and Johnson01/14/19 COT 5407 6Self-Introduction•Ph.D. in Computer Science from University of Rochester, 2004–Research Interests: data mining, machine learning, information retrieval, bioinformatics and more ?•Associate Professor in the School of Computer Science at Florida International University•Industry Experience:–Summer internships at Xerox Research (summer 2001, 2002) and IBM Research (Summer 2003, 2004)01/14/19 COT 5407 7Student Self-Introduction•Name–I will try to remember your names. But if you have a Long name, please let me know how should I call you •Major and Academic status•Programming Skills–Java, C/C++, VB, Matlab, Scripts etc.•Research Interest•Anything you want us to know01/14/19 COT 5407 8What this course is about•Introduction to Algorithms•Analysis of Algorithms•How does one design programs and ascertain their efficiency? •Divide-and-conquer techniques, string processing, graph algorithms, mathematical algorithms. Advanced data structures such as balanced tree schemes.01/14/19 COT 5407 9Course Logistics•Meeting Time and Location: Tuesday and Thursday 17:00pm-18:15pm, ECS134 •Office Hours: Tuesday and Thursday 14:30pm-15:30pm•TA: Yali Wu•Textbook: Introduction to Algorithms,3 (Third Edition) Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. MIT Press.01/14/19 COT 5407 10Evaluation•Class participation and Quizzes: 10% •Midterm Exam: 30%•Final Exam: 30%•Assignments:30%•You may work with one other person on homeworks, but you must each write up your solutions separately. If you work with another person, indicate who you worked with on your solution. •Please start a new page for each problem on your solutions, and include your name on each page, so the TA can choose the problems for grading. •Exams are open/closed book ??Algorithm•A computational problem is a mathematical problem, specified by an input/output relation.•An algorithm is a computational procedure for solving a computational problem. 01/14/19 COT 5407 11 “computer” problemalgorithminput output1-12Some Well-known Computational Problems•Sorting•Searching•Shortest paths in a graph•Minimum spanning tree•Primality testing•Traveling salesman problem•Knapsack problem•Chess•Towers of Hanoi•Program termination8/28/07 COT 5407 13History of AlgorithmsThe great thinkers of our field:• Euclid, 300 BC• Bhaskara, 6th century• Al Khwarizmi, 9th century• Fibonacci, 13th century• Babbage, 19th century• Turing, 20th century• von Neumann, Knuth, Karp, Tarjan, …8/28/07 COT 5407 14Euclid’s Algorithm•GCD(12,8) = 4; GCD(49,35) = 7;•GCD(210,588) = ??•GCD(a,b) = ??•Observation: [a and b are integers and a  b]–GCD(a,b) = GCD(a-b,b)•Euclid’s Rule: [a and b are integers and a  b]–GCD(a,b) = GCD(a mod b, b)•Euclid’s GCD Algorithm:–GCD(a,b)If (b = 0) then return a;return GCD(a mod b, b)1-15Basic Issues Related to Algorithms•How to design algorithms•How to express algorithms•Proving correctness•Efficiency–Theoretical analysis–Empirical analysis•Optimality1-16Algorithm design strategies•Brute force•Divide and conquer•Decrease and conquer•Transform and conquer•Greedy approach•Dynamic programming•Backtracking •Branch and bound•Space and time tradeoffs1-17Analysis of Algorithms•How good is the algorithm?–Correctness–Time efficiency: amount of work done–Space efficiency: amount of space used–Simplicity, clarity•Does there exist a better algorithm?–Lower bounds–Optimality01/14/19 COT 5407 18Correctness Proving correctness is dreadful for large algorithms. A strategy that can be used is: divide the algorithm into smaller pieces, and then clarify what the preconditions and postconditions are and prove correct assuming everything else is correct.01/14/19 COT 5407 19Amount of Work Done Rather than counting the total number of instructions executed, we'll focus on a set of key instructions and count how many times they are executed. Use asymptotic notation and pay attention only to the largest growing factor in the formula of the running time. Two major types of analysis: worst-case analysis and average-case analysis01/14/19 COT 5407 20More•Amount of space used: The amount of space used can be measured similarly. Consideration of this efficiency is often important.•Simplicity, clarity: Sometimes, complicated and long algorithms can be simplified and shortened by the use of recursive calls.•Optimality: For some algorithms, you can argue that they are the b est in terms of either amount of time used or amount of space used. There are also problems for which you cannot hope to have efficient algorithms.01/14/19 COT 5407 21Asymptotic Growth Rates of Functions•Big O•Big Omega•Little O•Little Omega•Theta Notation01/14/19 COT 5407 22Notations01/14/19 COT 5407 23Other mathematical background•The ceiling function•The floor function•The exponentials and logarithms•Fibonacci number•Summations and SeriesWhy study algorithms?•Theoretical importance–the core of computer science•Practical importance–A