Professor: Dinesh Mehta
Telephone: (303) 273 3713
Email: dmehta@mines.edu
Textbook: The Algorithm Design Manual, Second Edition, by Skiena
At this point, you know how to program and have seen basic data structures and sorting (CSCI 261 and 262); and you have taken discrete math (CSCI 358). In this course, we take these ideas to the next level. Algorithms is to programming as grammar is to literature! Except that in addition to being beautiful and thought-provoking, we want algorithms to perform well.
The course begins with ideas about algorithm correctness (aka proofs) and how to measure performance (e.g. big-Oh notation). We then review basic data structures and sorting, but with a focus on algorithmic ideas. Sorting, in particular, allows us to fairly painlessly explore pretty advanced concepts - randomized algorithms, lower bounds, divide and conquer, recurrence relations. Next, we study the dynamic-programming meta-technique, an approach that has been used to efficiently solve a variety of optimization problems. One of the problems we will consider, the string edit-distance problem, provides insights into the auto-correct feature on your phone. We then spend several weeks on my favorite part of the course - graph algorithms (including insights on how to escape a corn-maze and how a GPS finds routes) and close out the course with a brief introduction to NP completeness (including a brief look at the famous P = NP question).
The bulk of the grade is exams (50%) spread out over three mid-terms and one final; and four programming projects (40%) - two are individual and two are group projects; 5% is HW assignments and 5% is in-class worksheets.
This class covers the following topics:
Reasoning about algorithm correctness (proofs, counterexamples). Analysis of algorithms: asymptotic and practical complexity. Review of dictionary data structures (including balanced search trees). Priority queues. Advanced sorting algorithms (heapsort, radix sort). Advanced algorithmic concepts illustrated through sorting (randomized algorithms, lower bounds, divide and conquer). Dynamic programming. Backtracking. Algorithms on unweighted graphs (traversals) and weighted graphs (minimum spanning trees, shortest paths, network flows and bipartite matching); NP-completeness and its consequences.
3 hours lecture; 3 semester hours.
CSCI262 with a grade of C- or higher, MATH213, MATH223 or MATH224, MATH/CSCI358.
