Announcements
- The first assignment has been posted on the assignments page.
Wednesday, January 24, 2007 at 01:17
Course Information
- Lecture
- Days/times TR 11am-12:15pm
- Instructor: Dr. Aaron D. Jaggard (email)
- Office: Gibson 309 (x3642)
- Office Hours: TBA and by appointment
- Text
- Algorithms by Sanjoy Dasgpta, Christos Papadimitriou, and Umesh Vazirani
Note that email is usually a good way to get in touch with me.
Description and Topics
A study of important algorithms (including searching and sorting,
graph/network algorithms, and algorithms in number theory) and
algorithm design techniques (including greedy, recursive, and probabilistic
algorithms). Covers the analysis of algorithms (including worst- and
average-case analysis) and discussion of complexity classes for decision and
enumeration problems (including P, NP, #P, PSPACE).
A tentative list of topics is below. If you're particularly interested
in something that doesn't appear here, let me know.
You'll need to be able to do formal proofs, but that won't be a focus of the course.
You do not need experience with computer programming.
Algorithms
- Basic searching and sorting
- Recursive algorithms
- Average-case analysis of Quicksort
- Matrix multiplication
- FFT
- Graph algorithms, including:
- Network-flow problem
- Analysis of the Ford-Fulkerson algorithm
- Layered networks and the MPM algorithm
- Spanning trees
- Searching, cycle checking, topological sorting
- Number theory algorithms
- Euclidean algorithm for gcd
- Primality and pseudoprimality
- AKS primality test
- Probabilistic algorithms
- Quantum algorithms
Complexity
- Review of computation and decision problems
- P and NP
- Cook's theorem
- Notable NP-complete problems
- Backtracking and approximation
- Other time complexity classes
- Space complexity
- Complexity of enumeration problems
- Probabilistic algorithms and complexity classes
Grading
Your grade in this course will be based on regular homework (including presenting problems in class), exams, and a paper/presentation at the end of the term.
Homework
There will be regular homework sets assigned. During the term I will ask students to present work at the board (either from a homework set or a short problem done in class); this will contribute to your homework grade.
Homework will count for 20-25% of your final grade. However, homework cannot "save" your grade: in order to pass the course (or receive a C), you must earn a passing grade (or a C, respectively) on at least one exam.
Exams
There will be two exams (a midterm and a final), each worth 25-30% of your grade.
Paper/Presentation
You will need to turn in a short (I'm guessing 10 pages; details on this will come later) paper on a topic related to course. You will also give a short (15-20 minute, details to follow) talk on this material in class.
Once we're a little further into the semester I'll have a list of suggested topics, although you'll also be able to choose other topics with my approval.
This will contribute 20-30% of your final grade.
Other References
- The first edition of Algorithms & Complexity, by Herb Wilf, is available online. (The second edition is available in hardcopy.)
- The first (Fundamental Algorithms) and third (Sorting and Searching) volumes of The Art of Computer Programming, by Don Knuth, will be on reserve in the math library.
Tulane Resources
Aaron D. Jaggard (email)
Department of Mathematics
Tulane University
New Orleans, LA 70118
Wednesday, January 24, 2007 at 01:17