DOC PREVIEW
WSU CPTS 223 - Lecture Notes

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

WSU CPTS 223 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?