Class Overview Introduction to many of the basic data structures used in computer software CSE 326 Data Structures 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 scientist Introduction 2 Goals Goals 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 precisely 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 2006 3 Goals 4 Data Structures Clever ways to organize information in order to enable efficient computation 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 What do we mean by clever What do we mean by efficient Fred Brooks 1975 5 6 Picking the best Data Structure for the job Terminology Abstract Data Type ADT 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 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 A List with operations insert and delete A Stack with operations push and pop Implementation of data structure A specific implementation in a specific language 7 8 Concepts Terminology examples vs Abstract Pseudocode Algorithm 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 LinkedList Mechanisms Concrete Specific programming language Program 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 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 9 10 Today s Outline Why So Many Data Structures Ideal data structure fast elegant memory efficient Generates tensions time vs space performance vs elegance generality vs simplicity one operation s performance vs another s Introductions Administrative Info What is this course about Review Queues and stacks The study of data structures is the study of tradeoffs That s why we have so many of them 11 12 First Example Queue ADT Circular Array Queue Data Structure Q create destroy enqueue dequeue is empty G enqueue size 1 0 FIFO First In First Out Queue operations b c d e f front dequeue FEDCB A back enqueue Object x Q back x back back 1 size How test for empty list dequeue x Q front front front 1 size return x What is complexity of these operations How to find K th element in the queue Limitations of this structure 13 14 Circular Array vs Linked List Linked List Queue Data Structure b c d e front f back void enqueue Object x if is empty front back new Node x else back next new Node x back back next bool is empty return front null Object dequeue assert is empty return data front data temp front front front next delete temp return return data 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 complex 15 16 Second Example Stack ADT Stacks in Practice LIFO Last In First Out Stack operations create destroy push pop top is empty A EDCBA B C D E F Function call stack Removing recursion Balancing symbols parentheses Evaluating Reverse Polish Notation F 17 18 Algorithm Analysis Why Correctness Data Structures Does the algorithm do what is intended Performance Asymptotic Analysis What is the running time of the algorithm How much storage does it consume Different algorithms may be correct Which should I use 20 Recursive algorithm for sum Proof by Induction Basis Step The algorithm is correct for a base case or two by inspection Write a recursive function to find the sum of the first n integers stored in array v sum integer array v integer n returns integer if n 0 then sum 0 else sum nth number sum of first n 1 numbers return sum 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 21 22 Algorithms vs Programs Program Correctness by Induction Basis Step Proving correctness of an algorithm is very important sum v 0 0 9 a well designed algorithm is guaranteed to work correctly and its performance can be estimated 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 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 programs Inductive Step n k 1 sum v n returns v 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 9 23 24 Comparing Two Algorithms Comparing Two Algorithms GOAL Sort a list of names What we want Rough Estimate Ignores Details I ll buy a faster CPU I ll use C instead of Java wicked fast Really independent of details Coding tricks CPU speed compiler optimizations These would help any algorithms equally Don t just care about running time not a good enough measure Ooh look the O4 flag Who cares how I do it I ll add more memory Can t I just get the data pre sorted 25 Big O Analysis 26 Analysis of Algorithms Ignores details What details Efficiency measure how long the program runs how much memory it uses CPU speed Programming language used