Computer Science 501
Data Structures and Algorithm Analysis
Fall 2014, The College of Saint Rose
Lecture 5: More Analysis; Searching and Sorting
Date: Tuesday, September 23, 2014
Agenda
- Announcements
- Midterm exam coming soon
- 2 weeks from tonight: October 7
- designed to take 90-120 minutes, you will have the full 150 if needed
- up to 5 sheets of handwritten notes may be brought to the
exam, but no other reference materials will be permitted
- all written responses, including some Java programming
- topics include writing a Java class to meet some
requirement, Vector/ArrayList implementations, design
decisions, and analysis, analysis tools and problems like those
on lecture assignments and labs (Big O, Big Omega, Big Theta
intuition, definitions, application of definitions, complexity
proofs by finding constants, using limits, setting up and
solving summations and recurrences), empirical analysis, generic
data structure implementations and usage, searching and sorting
- Lab 4: Analysis [HTML] [PDF] recap
- Analyzing recursive algorithms
- Searching
- Sorting
- Lab 5: More Analysis [HTML] [PDF] out
Readings and References
Terminology
- divide and conquer algorithms
- master theorem
- linear search
- ordered data
- binary search
- sorting
- bubble sort
- selection sort
- insertion sort
Examples
- BinSearch
- SortingComparisons