CSE310 Lecture01: Algorithms, Counting and Data StructuresTopics of this lectureAlgorithmsExample of what is an algorithmExample of what is not an algorithmAnother view of algorithmsTime complexity of an algorithmSpace complexity of an algorithmComplexity of an algorithmCounting techniques and induction proofGrowth of functionsData structuresUsing the right data structuresUsing the right algorithmSummaryReadings and [email protected] Lecture01:CSE310 Lecture01:Algorithms, Counting and Data StructuresAlgorithms, Counting and Data StructuresGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureDiscussion of SyllabusAlgorithmsdefinitiontime complexityspace complexityCounting and Induction Proofnumber of operationsspace requirementData Structuresstacks and queuesadvanced data [email protected]An algorithm is a well-defined step by step computational procedure thatis deterministictakes some inputproduces some outputstops on any inputExamples illustrating what is an algorithm and what is not an [email protected] of what is an algorithmExample of what is an algorithmGiven a sequence of n numbers, compute the sum. Can we design an algorithm for this?Given a sequence of n numbers, order them in non-decreasing order, Can we design an algorithms for this?Introduce insertion [email protected] of what is Example of what is notnot an algorithm an algorithmThe 3n+1 problem.Given an integer n, if n=1 output n and stop; if n is even, output n=n/2 and continue; if n is odd, output n=3n+1 and continue;Is the above an algorithm?Print out all positive integers.Print our the first 10000000 positive [email protected] view of algorithmsAnother view of algorithmsAn algorithm is a tool to solve a well-defined computational problem.An instance of a problem.Example of a problem: Given a sequence of numbers, order them into non-decreasing order.An instance of the above problem is given by the input sequence 5, 4, 3, 2, 1.Another instance of the above problem is given by the input sequence 7, 5, 1, [email protected] complexity of an algorithmTime complexity of an algorithmGiven an algorithm A for solving a particular problem, what is the time complexity of the algorithm?Time complexity is measured using the number of operations required.We also need to note the input size of the problem instance.Examples: (1) summation, (2) matrix [email protected] complexity of an algorithmSpace complexity of an algorithmGiven an algorithm A for solving a particular problem, what is the space complexity of the algorithm?Space complexity is measured using the number of memory cells required.We also need to note the input size of the problem instance.Examples: (1) summation, (2) matrix [email protected] of an algorithmComplexity of an algorithmBest case analysisAverage case analysisWorst case analysisAmortized [email protected] techniques and induction proofCounting techniques and induction proof1+2+3+4+...+n=?1+1/2+1/3+1/4+...+1/n=?1+1/2+1/4+1/8+...+(1/2)n=?[email protected] of functionsGrowth of functionslg (n)sqrt(n)nn log(n)n2n32n[email protected] structuresData structuresWhat is an Abstract Data Type?A collection of data elementsA collection of functions on the data elementsWhy data structures?to store data efficientlyto process data efficientlyExamples of data structures:stacks and queuesbinary search [email protected] the right data structuresUsing the right data structuresHow to represent a polynomial of order n?use an array of size nuse a linked listHow to perform addition, subtraction and multiplication using the array representation?How to perform addition, subtraction and multiplication using the linked list representation?Which data structure is [email protected] the right algorithmUsing the right algorithmIf the first 6 terms in a sequence are 1, 1, 2, 3, 5, 8, what is the 7th term? What is the nth term?This sequence is called the Fibonacci sequence.Let us write two algorithms for computing the nth Fibonacci number.Which algorithm is [email protected]What is an algorithm?What is an ADT?Counting.Proof using mathematical induction.Problems and instances.Comparison of [email protected] and ExercisesReadings and ExercisesMost materials covered in this lecture can be found in Section 1.1, Section 1.2, Section 2.1 and 2.2.You should work on Exercises 1.1.1-1.1.5 (p.10) and Problems 1.1 (p.13).There may be a pop up quiz on the above topics.Lecture 02 will be on asymptotic notations. To preview, read Sections 3.1 and
View Full Document
Unlocking...