Computer Science 385

Design and Analysis of Algorithms

Spring 2017, Siena College

Instructor and Course Information

Instructor: | Dr. Robin Y. Flatland, Roger Bacon 315, (518) 782-6541 | |

Electronic mail: | flatland AT siena.edu | |

Office hours: | Monday 11-12:30, Thursday 12:30-3:30, Friday 11-12:30, and by appointment | |

Instructor: | Dr. James D. Teresco, Roger Bacon 321, (518) 782-6992 | |

Electronic mail: | jteresco AT siena.edu (best contact method) | |

Twitter: | @JTerescoSienaCS | |

Office hours: | Tuesday 10-11, Wednesday 2-3:30, Friday 9-10, and by appointment | |

Class URL: | [Link] | |

Class hour: | Monday, Friday 1:30-2:30 or 2:40-3:40, Roger Bacon 302 | |

Lab meetings: | Tuesday 1:00-3:00, 3:10-5:10, or 5:20-7:20, Roger Bacon 302 | |

Texts

The required text for the course is * Introduction to The Design and Analysis of Algorithms, Third Edition*
(Addison-Wesley, 2012, ISBN 0-13-231681-1) by Anany Levitin. This is available from
the Siena Bookstore (and elsewhere). If you buy elsewhere,
be sure to get the correct edition.

Course News

- Our first exam will take place during lab meetings on February
14.
- There will be an optional review session Monday evening, February 13, 7:00-8:30 PM, in Roger Bacon 328.
- This will be a closed book, closed notes exam, but you will be
provided with a copy of the the formulas in Appendix A
of Levitin. You may also bring a double-sided handwritten sheet
of notes on standard
*8.5 ×11*paper. - Except for the 5:20 lab, you will be required to stay until the lab period ends, even if you are finished early.
- Exam 1 Review Topics
- 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 Θ
- 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

- Algorithm Design Techniques
- If you can do all of the lab and homework problems, you will have no trouble with the exam!

- Upcoming due dates:
- Lab 4: Brute-Force Algorithms [PDF]: start of your lab meeting on February 14

Related Information and Links

- We will make use of the LaTeX document preparation system. It
is a set of macros built around the TeX typesetting system created by
Donald Knuth. The philosophy is to separate content from layout. In
other words, worry about
*what*you want to present and let the system determine*how*best to present it. There are many good introductions to LaTeX on the web: - Java Structures:
- 15 Sorting Algorithms in 6 Minutes
- Less relevant, but more fun: [XKCD] [Dilbert] [Fox Trot]