Computer Science 1704 Intro to Data Structures & Soft Eng

# Final Exam Review

The topics for final exam includes all material covered previously in the course. Students should review the test 1 learning objectives and test 2 learning objectives. The objectives below are for material covered after the second test, which includes sections 10-14 of the course notes. The notes and a list of the associated section readings from the textbook are located on the course schedule page. The learning objectives for the course material leading up to the final exam are listed below.

## Final Exam Learning Objectives

Students must be able to:

• Define the standard stack ADT operations.
• Compose and trace code that uses the standard stack ADT interface.
• Understand how to represent and implement standard stack ADT operations using an underlying array representation.
• Understand how to represent and implement standard stack ADT operations using an underlying linked-list representation.
• Define the standard queue ADT operations.
• Compose and trace code that uses the standard queue ADT interface.
• Understand how to represent and implement standard queue ADT operations using an underlying circular array representation.
• Understand how to represent and implement standard queue ADT operations using an underlying linked-list representation.
• Understand how to represent and implement a Drop-Out Stack (DOS) ADT operations using an underlying circular array representation.
• Understand how to represent and implement a Deque ADT operations using an underlying circular array representation.
• Know the various factors affecting the execution time of programs.
• Apply the exact time analysis rules to C++ code to determine a function, T(n), giving the number of executable statements for an arbitrary input size of N.
• Simplify summation expressions using common summation formulas.
• List and understand the complexity classes that the Order of time analysis functions fall into, O(T(n)).
• Understand the basic five Big-O theorems for simplifying O(T(n)).
• Recognize the relationships between the common growth curves and the pratical limitations.
• Apply the Big-O analysis rules to C++ code to determine the Big-O function, O(n), giving the complexity class for T(n) for an arbitrary input size of N.
• Define the best case, worst case and average case execution speed for a given algorithm.
• Determine if a sorting algorithm exhibits the property of "stablity".
• Code, trace, modify and perform a complexity analysis upon the Bubble sort algorithm.
• Code, trace, modify and perform a complexity analysis upon the Selection sort algorithm.
• Trace and understand code that implements a Duplex Selection sort algorithm.
• Understand the O(N log N) limit on comparison based sorting algorithms.
• Trace and understand code that implements a recursive/iterative Quicksort algorithm.
• Know the tradeoffs in swapping records as opposed to swapping pointers to records when sorting.
• Trace and understand code that implements a Binsort algorithm
• Create, trace, and modify C++ code for performing a sequential, linear, search on un-sorted and sorted lists of data.
• Understand the coding techniques for implementing a probability ordered linear search.
• Speed up sequential search code using inlining, and the "sentinel" search method.
• Create, trace, and modify C++ code for performing a binary search on lists of data.
• Understand the coding techniques for implementing a generalized binary (interpolation) search.

 D. Barnette 4/26/2002 Virginia Tech © 1995-2002