Computer Science 385
Design and Analysis of Algorithms

Spring 2018, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Lab 10: Greedy Algorithms and Heaps [PDF] not due until April 17/18 lab meetings, but why not wrap it up sooner?
  • Exam 2 Tuesday evening
    • many details on the Lecture 18 page
    • topic list:
      • decrease and conquer algorithms, including insertion sort, topological sort, generating permutations and subsets, fake coin problems
      • divide and conquer algorithms, including mergesort, quicksort, divide and conquer 2D closest pairs
      • setting up and solving recurrences, master theorem
      • drawing recursive call trees
      • search trees, including standard BST, AVL, 2-3 trees
      • hashing
      • dynamic programming, comparison with recursive exhaustive search, top-down and bottom-up approaches
      • using pre-sorting to improve efficiency
  • You should participate in or volunteer for the hackathon. 10 bonus quiz points available if you do.
• Problem Set 6 out
• Quiz 3 recap
• Recaps of recent problem sets and labs