Cpt S 223, Fall 2007 Copyright: Washington State University 1Cpt S 223Course OverviewCpt S 223, Fall 2007 Copyright: Washington State University 2Course Goals• Learn about new/advanced data structures• Be able to make design choices on the suitable data structure for different application/problem needs• Analyze (objectively) the run-time and memory complexity of algorithms and problem properties• Design algorithms for problems, and iteratively improve on the efficiency• Express algorithmic language in pseudo-codes (proglanguage independent)Cpt S 223, Fall 2007 Copyright: Washington State University 3Basic Math Background• Summation/Series– Geometric, arithmetic, sum of squares, sum of first n ints• Proving Techniques– By Counterexample– By contradiction– By contra-positive– Induction• Recursion– Tower of Hanoi– Recursive formula from pseudo-codes – Tail recursionCpt S 223, Fall 2007 Copyright: Washington State University 4Algorithmic Notation & Analysis• Big-O O()• Omega Ω()• small-O o()• small-omega w()• Theta ()• Worst-case• Average-case• Best-case • “Algorithms”• Lower-bound • Upper-bound• Tight-bound• “Optimality”Cpt S 223, Fall 2007 Copyright: Washington State University 5Factors for Algorithmic Design Consideration• Run-time• Space/memory• Computational model• Suitability to the problem’s application domain (contextual relevance)• Scalability• Guaranteeing correctness• Deterministic vs. randomized• System considerations: cache, disk, network speeds, etc.Cpt S 223, Fall 2007 Copyright: Washington State University 6Algorithmic Design: An Example• The Maximum Subsequence Sum Problem• Input: An array A[1..n] of integers• Output: Find a stretch with the largest non-negative sum, if one exists• O(n3) ==> O(n2) ==> O(n lg n) ==> O(n)Cpt S 223, Fall 2007 Copyright: Washington State University 7Trees• Trees• Representation– Time-efficient– Space-efficient• Access patterns– Depth-first– Breadth-first– Top-down– Bottom-up• Traversals• Pre-order• Post-order• In-order• EulerianCpt S 223, Fall 2007 Copyright: Washington State University 8Search TreesO(lg n)O(lg n)O(n)HeightO(lg n)O(lg n)O(n)FindO(lg n)O(lg n)Avg-caseO(lg n)O(lg n)Worst-caseAVLO(n)DeleteO(n)InsertWorst-caseBSTCpt S 223, Fall 2007 Copyright: Washington State University 9Search Trees for Disks/Secondary Storage• B+ treesLeavesInternalnodesRoot• M=5 (order of the B+ tree)• L=5 (#data items bound for leaves)• Index to the Data• Each internal node = 1 disk block• Data items stored at leaves• Each leaf = 1 disk blockCpt S 223, Fall 2007 Copyright: Washington State University 10Priority Queues - Heaps• Insert (x)• x = DeleteMin()– Return the next minimum entry in the queue• Alternative: x = DeleteMax()– Return the next maximum entry in the queueCpt S 223, Fall 2007 Copyright: Washington State University 11Heap Main Properties• Structure property• Heap order property• Binary Heap• Binomial HeapCpt S 223, Fall 2007 Copyright: Washington State University 12Binary HeapCpt S 223, Fall 2007 Copyright: Washington State University 13Binomial Heapn = 31 = (1 1 1 1 1)2B0B1B2B3B4B2B3Cpt S 223, Fall 2007 Copyright: Washington State University 14(Amortized) Run-time Per OperationO(log n)O(log n)O(1) Binomial HeapO(log n)O(log n)O(log n)Skew HeapO(log n)O(log n)O(log n)Leftist HeapO(n)O(log n)O(lg n) orO(1)Binary heapMergeDeleteMinInsertCpt S 223, Fall 2007 Copyright: Washington State University 15Union-Find Data Structure• Disjoint Set operations• Two basic operations– Find (x)– Union (x, y)Cpt S 223, Fall 2007 Copyright: Washington State University 16Heuristics for Union-FindO(m Inv.Ackermann(m,n))= O(m log*n)Union-by-rank, Path compression FindO(m log n)Arbitrary Union, Path compression FindO(m log n)Union-by-rank,Simple FindO(m log n)Union-by-size, Simple FindO(m n)Arbitrary Union, Simple FindWorst-case run-time for m operationsExtremely slowGrowing functionCpt S 223, Fall 2007 Copyright: Washington State University 17Algorithm Design Techniques• Divide and Conquer• Greedy• Dynamic ProgrammingCpt S 223, Fall 2007 Copyright: Washington State University 18Class Reminders• COURSE EVALUATIONS– “Very Important”– It does matter!– By Sunday 12/16 • FINALS– 8-10 am, Friday, 12/14Cpt S 223, Fall 2007 Copyright: Washington State University 19Thank
View Full Document