Course description:
This course will introduce students to designing scalable and
effective algorithms for computational science and engineering
applications. The course focuses on algorithm design, complexity
analysis, experimentation, and optimization, for important science and
engineering applications. Students will develop knowledge and skills
concerning:
the design and analysis of real-world algorithms employed in computational science and engineering applications;
proofs of problem complexity, proofs of correctness and time/space requirements of algorithms;
experimental performance analysis of algorithms.
Fall 2017 tentative topics:
Analysis: big o notation, recurrences, models of computation
Greedy algorithms: e.g. fractional knapsack, minimum spanning tree
Dynamic programming: e.g. longest common subsequence, string alignment, edit distance
Flows: max flow/min cut
NP-completeness: decision vs optimization, reductions, hierarchy
NP-completeness: e.g. subset sum, clique, SAT, vertex cover, Steiner Tree
Approximation algorithms: e.g. vertex cover, set cover,
knapsack, max cut, k-center clustering
Heuristics / Local Search
Graph Partitioning
Experimental Methods and Validation
Recommended textbooks:
(KT) J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 1st ed., 2005 (strongly
recommended - main textbook, in bookstore)
(CLRS) T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, Third edition, MIT Press, 2010. (in bookstore)
(BRV) A. Benoit, Y. Robert, F. Vivien. A guide to algorithm design: Paradigms, methods, and complexity analysis. Chapman and Hall/CRC Press 2013. (in bookstore)
(DPV) S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.
(McG) Catherine C. McGeoch, A Guide to Experimental Algorithmics, 1st ed., Cambridge
University Press, 2012.
Pre-requisites: Undergraduate Semester level CS 1331 Minimum Grade of C or Undergraduate Semester level CS 1372 Minimum Grade of C or Undergraduate Semester level CS 2316 Minimum Grade of C or Undergraduate Semester level CX 4010 Minimum Grade of C or Undergraduate Semester level ECE 2035 Minimum Grade of C or Undergraduate Semester level ECE 2036 Mini- mum Grade of C.
Recommended: design and analysis of algorithms (GT CS 3510 or equivalent), some background in discrete math, and graphs. If you do not know what a Depth First Search is, you are most likely not ready to take this course.
Students (from the Sciences, Engineering, and Computing) interested in algorithmic applications in science and engineering are encouraged to take this course.
This course can be taken for satisfying the theory breadth requirement by computer science graduate students (M.S. and non-theory Ph.D. students). This course cannot be taken by ACO students to satisfy their core requirement and by theory Ph.D. students in computer science to satisfy the theory breadth requirement.
Most of the homeworks will involve proofs. Some programming questions and possibly your project will require coding in your choice of language.
Grading:
(25 %) Midterm
(25 %) Final
(25 %) Project
(20 %) Homework
( 5 %) Class participation
Important dates:
Oct 5: Midterm (tentative)
Dec 5: Last class and Project due
Dec 8: Final exam (11:30am-2:20pm)
Aug 22: First class
Aug 25: Drop deadline without W
Oct 28: Withdrawal deadline to change grade mode from letter grade to pass/fail (and vice versa), or drop with a W
Dec 19: Grades available
CLASS POLICIES:
1. Class announcements will be sent to the Georgia Tech T-Square
mailing list, see http://t-square.gatech.edu.
2. Please let me know as soon as possible if you will need to re-schedule an exam, or have any special needs during the semester.
3. Each student must read and abide by the Georgia Tech Academic Honor
Code, see http://www.honor.gatech.edu.
4. Plagiarizing is defined by Webster's as "to steal and pass off (the ideas or words of another) as one's own: use (another's production) without crediting the source." If caught plagiarizing, you will be dealt with according to the GT Academic Honor Code.
5. All homework must be submitted on-time through T-Square. Homework is due by 6PM on the given due date. Late homeworks will not be accepted without a legitimate excuse and approval from the instructor.
6. When working on homework, you may work with other students in the class. However, each student must write homework solutions in their own words independently, and upload their own homework solutions to T-Square with the collaborators names annotated on every copy of the submission.
7. No collaboration is permitted on exams. The midterm and final exams will be in-class, closed-book exams. You will be allowed to take a "cheat sheet" (double-sided 8.5 x 11 sheet of paper) into each exam.
8. Unauthorized use of any previous semester course materials, such as tests, quizzes, homework, projects, and any other coursework, is prohibited in this course. Using these materials will be considered a direct violation of academic policy and will be dealt with according to the GT Academic Honor Code.