Computer Science 385
Design and Analysis of Algorithms

Spring 2018, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Lab 5: Graph Traversals [HTML] [PDF], due before Tuesday's exam (ideally sooner)
    • further suggestions on METAL improvements welcome any time
    • see the list of open issues to which you are welcome to contribute
  • Problem Set 2: [PDF] due this afternoon; I will discuss solutions on Monday even if I can't get them all graded
• Tuesday evening's Exam 1: topics to review
  • Algorithm Design Techniques
    • Brute force algorithm design (including exhaustive search)
  • Data structures
    • Graphs: directed/undirected, weighted/unweighted, indegree & outdegree of vertex in directed graph, degree of vertex in undirected graph, adjacency matrix and adjacency list representations (implementations, memory requirements, running times)
  • Algorithms/Problems
    • Bubble Sort
    • Selection Sort
    • String matching
    • Closest pairs
    • Traveling Salesman
    • Knapsack
    • Depth-first and breadth-first search
    • Convex hull
  • Analysis Techniques
    • Summations
    • Counting basic operations in code/pseudocode using summations
    • Big O, Big Ω, Big Θ
    • Proving growth rates using limits and definitions (i.e., finding constants)
    • Ordering functions by growth rates
    • Basic efficiency classes: constant, logarithmic, linear, quadratic, cubic, polynomial, exponential, factorial
• How to approach Lab 4: Brute-Force Algorithms Question 9
• A few more words about graph traversals
• Decrease and conquer
  • Analysis of recursive insertion sort
  • Levitin describes several more decrease and conquer algorithms
  • We will consider one more "decrease by one": topological sort
  • Please read about generating permutations and subsets

Terminology

• directed acyclic graph/dag
• topological sort
• source removal algorithm for topological sort
• generating permutations of a list
• generating subsets of a list