CSE310 Lecture01 Algorithms Counting and Data Structures Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Discussion of Syllabus Algorithms Counting and Induction Proof definition time complexity space complexity number of operations space requirement Data Structures stacks and queues advanced data structures 2 Guoliang Xue asu edu Algorithms An algorithm is a well defined step by step computational procedure that is deterministic takes some input produces some output stops on any input Examples illustrating what is an algorithm and what is not an algorithm 3 Guoliang Xue asu edu Example of what is an algorithm Given a sequence of n numbers compute the sum Can we design an algorithm for this Given a sequence of n numbers order them in nondecreasing order Can we design an algorithms for this Introduce insertion sort 4 Guoliang Xue asu edu Example of what is not an algorithm The 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 integers 5 Guoliang Xue asu edu Another view of algorithms An 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 3 6 Guoliang Xue asu edu Time complexity of an algorithm Given 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 multiplication 7 Guoliang Xue asu edu Space complexity of an algorithm Given 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 multiplication 8 Guoliang Xue asu edu Complexity of an algorithm Best case analysis Average case analysis Worst case analysis Amortized analysis 9 Guoliang Xue asu edu Counting techniques and induction proof 1 2 3 4 n 1 1 2 1 3 1 4 1 n 1 1 2 1 4 1 8 1 2 n 12 22 32 n2 10 Guoliang Xue asu edu Growth of functions lg n sqrt n n n log n n2 n3 2n n 11 Guoliang Xue asu edu Data structures What is an Abstract Data Type A collection of data elements A collection of functions on the data elements Why data structures to store data efficiently to process data efficiently Examples of data structures stacks and queues binary search trees 12 Guoliang Xue asu edu Using the right data structures How to represent a polynomial of order n use an array of size n use a linked list How 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 better 13 Guoliang Xue asu edu Using the right algorithm If 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 n th Fibonacci number Which algorithm is better 14 Guoliang Xue asu edu Summary What is an algorithm What is an ADT Counting Proof using mathematical induction Problems and instances Comparison of algorithms 15 Guoliang Xue asu edu Readings and Exercises Most 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 3 2 16 Guoliang Xue asu edu
View Full Document
Unlocking...