COS2611 - Programming Data Structures

COS2611 - Programming Data Structures Contents Appendix A: INTRODUCTION TO ALGORITHMS ANALYSIS (Big O) (p1 – 9 [9])...............................................................2 Chapter 3: Pointers and Array-Based Lists (p131 – 186 [55]).........................................................................................7 Pointers.......................................................................................................................................................................7 Dynamic Arrays...........................................................................................................................................................8 Functions and Pointers...............................................................................................................................................9 Chapter 5: Linked Lists (p265 – 326 [61]) [1/1]............................................................................................................10 Chapter 6: Recursion (p355 – 387 [32])........................................................................................................................16 Chapter 7: Stacks (p395 – 443 [48]) [3/3].....................................................................................................................16 Chapter 8: Queues (p451 – 491 [40]) [2/2]..................................................................................................................21 Chapter 10: Sorting Algorithms (p533 – 594 [61])........................................................................................................26 Chapter 11: Binary Trees and B-Trees (p599 – 678 [79]) [3/3].....................................................................................29 Chapter 12: Graphs (p685 – 724 [39])..........................................................................................................................34 Appendix A: INTRODUCTION TO ALGORITHMS ANALYSIS (Big O) (p1 – 9 [9]) (How time scales with respect to some input variables) 1. Different steps get added. doStep1(); // O(a) doStep2(); // O(b) =O(a + b) = O(n + n) = O(2n) = O(n) 2. Nested steps get multiplied. whileStep1( i = n) { whileStep2( j = n * n) { }} = O(n * n*n) = O(n3 ) 3. Drop constants If an algorithm is O(5n3 ), it is also O(n3 ). If an algorithm is O(n3 +4n2 +3n), it is also O(n3 ) 4. Drop non-dominate terms n 2 + n3 = n3  Here are some common types of time complexities in Big O Notation: O(1) - Constant time complexity O(log n) - Logarithmic time complexity O(n) - Linear time comple