Computer Science 501
Data Structures and Algorithm Analysis

Fall 2015, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • No office hours the rest of the week while I am away at the CCSC-RM Conference. I will have limited email access but will respond when I can.
• Midterm exam coming soon
  • 2 weeks from tonight: October 14
  • 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
  • practice questions off
• Lab 3: Timing Java [HTML] [PDF] recap
• Lab 4: Analysis [HTML] [PDF] due now, recap next week
• Analyzing recursive algorithms
• Searching
• Sorting
• Lab 5: More Analysis [HTML] [PDF] out

Readings and References

• Bailey Ch. 6
• Bubble Sort at Sorting Algorithm Animations
• Selection Sort at Sorting Algorithm Animations
• Insertion Sort at Sorting Algorithm Animations
• Merge Sort at Sorting Algorithm Animations
• 15 Sorting Algorithms in 6 Minutes

Terminology

• divide and conquer algorithms
• master theorem
• linear search
• ordered data
• binary search
• sorting
• bubble sort
• selection sort
• insertion sort
• merge sort

Examples

• BinSearch
• SortingComparisons