CSE 326: Data StructuresIntroductionClass Overview• Introduction to many of the basic data structures used in computer software– Understand the data structures– Analyze the algorithms that use them– Know when to apply them• Practice design and analysis of data structures.• Practice using these data structures by writing programs.• Make the transformation from programmer to computer scientist2Goals• You will understand– what the tools are for storing and processing common data types– which tools are appropriate for which need• So that you can– make good design choices as a developer, project manager, or system customer• You will be able to– Justify your design decisions via formal reasoning– Communicate ideas about programs clearly and precisely3Goals“I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”Linus Torvalds, 20064Goals“Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.”Fred Brooks, 19755Data Structures“Clever” ways to organize information in order to enable efficient computation– What do we mean by clever?– What do we mean by efficient?6Picking the best Data Structure for the job• The data structure you pick needs to support the operations you need• Ideally it supports the operations you will use most often in an efficient manner• Examples of operations:–A List with operations insert and delete–A Stack with operations push and pop7Terminology• Abstract Data Type (ADT)– Mathematical description of an object with set of operations on the object. Useful building block.• Algorithm– A high level, language independent, description of a step-by-step process• Data structure– A specific family of algorithms for implementing an abstract data type.• Implementation of data structure– A specific implementation in a specific language8Terminology examples• A stack is an abstract data type supporting push, pop and isEmpty operations• A stack data structure could use an array, a linked list, or anything that can hold data• One stack implementation is java.util.Stack; another is java.util.LinkedList9 10Concepts vs. Mechanisms• Abstract• Pseudocode• Algorithm– A sequence of high-level, language independent operations, which may act upon an abstracted view of data.• Abstract Data Type (ADT)– A mathematical description of an object and the set of operations on the object.•Concrete• Specific programming language• Program– A sequence of operations in a specific programming language, which may act upon real data in the form of numbers, images, sound, etc. • Data structure– A specific way in which a program’s data is represented, which reflects the programmer’s design choices/goals.Why So Many Data Structures?Ideal data structure:“fast”, “elegant”, memory efficientGenerates tensions:–time vs. space– performance vs. elegance– generality vs. simplicity– one operation’s performance vs. another’s11The study of data structures is the study of tradeoffs. That’s why we have so many of them!Today’s Outline• Introductions• Administrative Info• What is this course about?• Review: Queues and stacks12First Example: Queue ADT• FIFO: First In First Out• Queue operationscreatedestroyenqueuedequeueis_empty13F E D C BenqueuedequeueGACircular Array Queue Data Structureenqueue(Object x) {Q[back] = x ;back = (back + 1) % size}14b c d e fQ0size - 1front backdequeue() {x = Q[front] ;front = (front + 1) % size;return x ;}How test for empty list?How to find K-th element in the queue?What is complexity of these operations?Limitations of this structure?Linked List Queue Data Structure15b c d e ffront backvoid enqueue(Object x) {if (is_empty())front = back = new Node(x)elseback->next = new Node(x)back = back->next}bool is_empty() {return front == null}Object dequeue() {assert(!is_empty)return_data = front->datatemp = frontfront = front->nextdelete tempreturn return_data}Circular Array vs. Linked List• Too much space• Kth element accessed “easily”• Not as complex• Could make array more robust• Can grow as needed• Can keep growing• No back looping around to front• Linked list code more complex16Second Example: Stack ADT• LIFO: Last In First Out• Stack operations– create– destroy– push–pop–top– is_empty17ABCDEFE D C B AFStacks in Practice• Function call stack• Removing recursion• Balancing symbols (parentheses)• Evaluating Reverse Polish Notation18Data StructuresAsymptotic AnalysisAlgorithm Analysis: Why?• Correctness:– Does the algorithm do what is intended.• Performance:– What is the running time of the algorithm.– How much storage does it consume.• Different algorithms may be correct– Which should I use?20Recursive algorithm for sum• Write a recursive function to find the sum of the first n integers stored in array v.sum(integer array v, integer n) returns integerif n = 0 thensum = 0elsesum = nth number + sum of first n-1 numbersreturn sum21Proof by Induction• Basis Step: The algorithm is correct for a base case or two by inspection.• Inductive Hypothesis (n=k): Assume that the algorithm works correctly for the first k cases.• Inductive Step (n=k+1): Given the hypothesis above, show that the k+1 case will be calculated correctly.22Program Correctness by Induction• Basis Step:sum(v,0) = 0. 9• Inductive Hypothesis (n=k): Assume sum(v,k) correctly returns sum of first k elements of v, i.e. v[0]+v[1]+…+v[k-1]+v[k]• Inductive Step (n=k+1): sum(v,n) returnsv[k]+sum(v,k-1)= (by inductive hyp.)v[k]+(v[0]+v[1]+…+v[k-1])=v[0]+v[1]+…+v[k-1]+v[k] 923Algorithms vs Programs• Proving correctness of an algorithm is very important– a well designed algorithm is guaranteed to work correctly and its performance can be estimated• Proving correctness of a program (an implementation) is fraught with weird bugs– Abstract Data Types are a way to bridge the gap between mathematical algorithms and programs24Comparing Two AlgorithmsGOAL: Sort a list of names“I’ll buy a faster CPU”“I’ll use C++ instead of Java – wicked fast!”“Ooh look, the –O4 flag!”“Who cares how I