Algorithm Analysis

Programming is a complex task for several reasons including

1. Large projects involving many people (software engineering).
2. Program may involve storing and accessing large quantities of data (data structures and databases)
3. Program may involve solving complex computational problems for which the obvious solutions are inadequate (algorithms).

The emphasis in an algorithms course is on studying efficient algorithms for solving common programming problems. Efficiency is determined using asymptotic analysis which provided an estimate on how fast the time to solve a problem increases as the size of the problem increases. As we will soon see a faster computer cannot rescue a bad algorithm. Along the way we will look at some of the following general strategies:

• Divide and conquer
• Greedy algorithms
• Dynamic programming
• Tree and graph traversals
• Backtracking
• Branch and bound

Fundamentals

• Notes

Searching

• Notes

Sorting

• Notes

Graphs

Note the graph code provided below includes the DFS, BFS and topological sort.  We will be adding code for finding the shortest path and minimum spanning tree.

• Notes
• Graph code
• Adjacency matrix for DFS and BFS example
• Adjacency matrix for topological sort example

Quizzes and Projects

• Project 1 - Tuesday, February 4
• Project 2 - Tuesday, February 25
• Project 3 - Tuesday, April 8
• Project 4 - Thursday, May 1

Presentation

• Description

Final Exam

• Description

Internet Resources

Courses

• Index of algorithms courses on the internet

• OOPWEB algorithms courses

• compared to what?

• ACM computing curriculum

• Oregon state
• University of Nevada
• University of Toronto
• University of Western Australia
• University of Auckland (graph algorithms)
• University of Illinois
• CMU
• Eppstein lectures
• SUNY Stony Brook
• Eppstein

Dictionaries

• Algorithm and data structures dictionary

Libraries

• Extensive library of data structure and algorithms
• LEDA

Animations

• Algorithm animations
• Complete collection of algorithm animations
• Sorting algorithm animations
• More sorting animations
• Great sorting animations
• Prim's algorithm animation

Miscellaneous

• Algorithm and data structure links
• School of informatics
• Algorithm analysis
• Merriam Webster graph resources