Page 43 - DCAP407_DATA_STRUCTURE
P. 43

Data Structure



                          2.7   Review Questions

                          1.  “Mathematical  notation is a  system  of symbolic representations of mathematical objects and
                              ideas.” Discuss.
                          2.  “To select the best algorithm, it is necessary to check the efficiency of each algorithm.” Justify.
                          3.  “Big-O notation describes the performance or time complexity of an algorithm.” Comment.

                          4.  “The omega notation can be defined as f(n)≥ c∗ g(n).” Describe.
                          5.  “Floor function gives the largest integer lesser than or equal to x.” Describe with an example.
                          6.  Describe modular arithmetic with the help of a 12 hour clock.
                          7.  “Efficiency of an algorithm can be determined by calculating its performance.” Comment.
                          8.  “Time complexity of an algorithm is the amount of time required by an algorithm to execute.”
                              Discuss with an example.
                          9.  “Time space tradeoff in context of algorithms relates to the execution of an algorithm.” Comment.
                          10.  “Analysis of an algorithm is required to determine the amount of resources it requires.” Discuss.
                          11.  “The best case efficiency of an algorithm is the efficiency of the algorithm for the best case input of
                              size n.” Discuss with an example.

                          12.  “Complexity is a measure of the performance of an algorithm.” Comment.
                          Answers: Self Assessment
                          1.  (a) True       (b) False           (c) True               (d) True      (e) True      (f) False
                          2.  (a) Asymptotic notations   (b) Big-O notation            (c) Minimum
                              (d) Omega                (e) Worst case time complexity
                          3.  (a) Big-O notation         (b) Average case analysis     (c)     Floor function

                              (d) Algorithm analysis   (e) Omega notation
                          2.8   Further Readings


                                      Lipschutz, S. (2011). Data Structures with C. Delhi: Tata McGraw-Hill.

                                      Reddy, P. (1999). Data Structures Using C. Bangalore: Sri Nandi Publications.


                                      http://www-old.oberon.ethz.ch/WirthPubl/AD.pdf
                                      http://msdn.microsoft.com/en-us/library/06bkb8w2%28v=vs.71%29.aspx
                                      http://www.cplusplus.com/doc/tutorial/variables/
                                      http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-
                                      introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-1-administrivia-
                                      introduction-analysis-of-algorithms-insertion-sort-mergesort/lec1.pdf
















                          36                      LOVELY PROFESSIONAL UNIVERSITY
   38   39   40   41   42   43   44   45   46   47   48