ADVANCED DATA-STRUCTURES & ALGORITHM ANALYSIS

ADVANCED DATA-STRUCTURES & ALGORITHM ANALYSIS Dr.Sukhamay Kundu Computer Science Dept, Louisiana state University Baton Rouge, LA 70803 kundu@csc.lsu.edu Spring 2011 (copyright@2010 , @2011) 1.2 ROLE OF DAT A-STRUCTURES IN COMPUTATION Makes Computations Faster: •Faster is better.(Another way to makecomputations faster is to use parallel or distributed computation.) Three Basic Computation Steps: Computation = Sequence of Computation Steps (1) Locate/Access data-values (inputs to a step) (2) Compute avalue (output of a step) (3) Store the newvalue External Input External

Output Program: Algorithm + DataStructure + Implementation. • Algorithm − The basic method; it determines the data-items computed. − Also, the order in which those data-items are computed (and hence the order of read/write data-access operations). • Data structures − Supports efficient read/write of data-items used/computed. Total Time =Time to access/store data + Time to compute data. Efficient Algorithm = Good method + Good data-structures (+ Good Implementation) Question: •? What is an efficient program? •? What determines the speed of an Algorithm? •? A program must also solvea"problem". Which of the three parts algorithm, data-structure, and implementation embodies this? 1.3 ALGORITHM OR METHOD vs. DAT A STRUCTURE Problem: Compute the average of three numbers. Tw o Methods: (1) aver=(x+y+z)/3. (2) aver=(x/3) + (y/3) + (z/3). •Method (1) superior to Method (2); twoless div-operations. •Theyaccess data in the same order: 〈x, y, z,aver〉. •Any improvement due to data-structure applies equally well to both methods. Data structures: (a) Three variables x, y, z. (b) An array nums[0..2]. − This is inferior to (a) because accessing an array-item takes more time than accessing a simple variable. (Toaccess nums[i], the executable code has to compute its address addr(nums[i]) = addr(nums[0]) + i*sizeof(int), which involves 1 addition and 1 multiplication.) − When there are large number of data-items, naming indi- vidual data-items is not practical. − Use of individually named data-items is not suitable when a varying number of data-items are involved (in particular,if theyare used as parameters to a function). APoor Implementation of (1): Using 3 additions and 1 division. a=x+y;//uses 2 additional assignments b=a+z; aver = b/3; 1.4 LIMITS OF EFFICIENCY Hardwarelimit: • Physical limits of time (speed of electrons) and space (layout of circuits). This limit is computation problem independent. From 5 mips (millions of instructions per sec) to 10 mips is an improvement by the factor of 2. One nano-second = 10−9 (one billionth of a second); 10 mips = 100 ns/instruction. Softwarelimit: • Limitless in a way,except for the inherent nature of the problem. That is, the limit is problem dependent. Sorting Algorithm A1: O(n.log n)time Sorting Algorithm A2: O(n2)time (n =number of items sorted) A1 is an improvement overA2bythe factor n2 n.log n = n log n = →∞as n →∞. • O(n.log n)isthe efficiency-limit for sorting Algorithms. 1.5 MEASURING PERFORMANCE Analytic Method: •Theoretical analysis of the Algorithm’stime complexity. Empirical Methods: •Count the number of times specific operations...

Website: www.csc.lsu.edu | Filesize: -
No of Page(s): 154
Download ADVANCED DATA-STRUCTURES & ALGORITHM ANALYSIS.pdf