Computer Science 385
Design and Analysis of Algorithms

Spring 2018, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Problem Set 5: [PDF] due this afternoon, 4 PM
  • We next meet for labs on April 3/4; please bring laptops to your lab meeting that week
  • Graded work will be returned on our return - need to hold off returning most recent work for now - except labs which are all available
  • Contact Prof. Armitage if you would like to learn more and possibly attend a cyber careers info session on April 4
  • See my email about the potential summer research project on the map data and algorithm visualization tool
• First discussion about Exam 2
  • Tuesday, April 10, Roger Bacon 202
  • Exam available 6-10 PM, but you must start by 8 and cannot leave before 8
  • No lab meetings Tuesday, April 10 or Wednesday, April 11
  • Topics covered are those in the first 8 chapters of Levitin, Lectures up to 17, labs up to 9, and the first five problem sets
  • There will be a strong focus on material since Exam 1, but keep in mind that some is cumulative by nature, and in other cases, we might want to compare more advanced solution techniques like divide and conquer or dynamic programming with the simpler ones we saw earlier such as brute force
  • A list of topics will be made available soon
  • Some practice questions coming, and we can think about some review times
  • You will be provided with all needed summation and log formulas, and you will be permitted a single double-sided sheet of handwritten notes as a reference
  • At the least, I will have extra office hours Tuesday morning and afternoon
• Greedy algorithms
  • basic idea
  • Prim's algorithm
  • Kruskal's algorithm
• Quiz 3
• Have a Happy Easter and a great spring break!

Terminology

• greedy algorithms
• (minimum) spanning tree
• Prim's algorithm
• Dijkstra's algorithm
• single-source shortest path problem