Fall 2006Georgia Tech, CS 4803-DAGeorgia Tech, CS 8803-DATu/Th 3:05pm - 4:25pmClassroom: CCB Room 101Computational Science & Engineering (CSE)Algorithmshttp://www.cc.gatech.edu/~bader/COURSES/GATECH/CS8803-Fall2006/Instructor: Prof. David A. Bader, CCB 257, 404-385-0004, bader@ccCourse Assistant:TBDOffice Hours: Tuesday/Thursday 2:00pm-3:00pm, or by appointmentSuggested Textbook:1. [CLRS]: Cormen, Leiserson, Rivest, and Stein,Introduction to A lgorithms, Second edition, MIT Press, 2001.Course Description: This course will introduce students to designing high-performanceand scalable algorithms for computational science & engineering applications. The coursefocuses on algorithm design, complexity analysis, experimentation, and optimization, forimportant science and engineering applications. Students will develop knowledge and skillsconcerning:• the design and analysis of real-world algorithms employed in computational scienceand engineering applications, and• performance optimization of applications using the best practices of algorithm engi-neering.Pre-requisites: design and analysis of algorithms (CS 3510).Students (from the Sciences, Engineering, and Computing) interested in algorithmic appli-cations in science and engineering are encouraged to take this course.This course can be taken for satisfying the theory breadth requirement by computer sciencegraduate students (M.S. and non-theory Ph.D. students). This course cannot be taken byACO students to satisfy their core requirement and theory Ph.D. students in computerscience to satisfy the theory breadth requirement.Grading:(25 %) Midterm(25 %) Final(25 %) Project(20 %) Homework( 5 %) Class participation1CLASS POLICIES1. Please let me know as soon as possible if you will need to re-schedule an exam, or haveany special needs during the semester.2. Each student must read and abide by the Georgia Tech Academic Honor Code, seewww.honor.gatech.edu.3. Plagiarizing is defined by Websters as “to steal and pass off (the ideas or words ofanother) as one’s own: use (another’s production) without crediting the source.” Ifcaught plagiarizing, you will be dealt with according to the GT Academic Honor Code.4. When working on homework, you may work with other students in the class. However;you must turn in separate copies of the homework with the following written on it:your name and the names of everyone with whom you collaborated.5. Homework is due by 5PM on the given due date. Late homeworks will not be acceptedwithout a legitimate excuse and approval from the instructor.6. 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 11sheet of paper) into each exam.7. Unauthorized use of any previous semester course materials, such as tests, quizzes,homework, projects, and any other coursework, is prohibited in this course. Usingthese materials will be considered a direct violation of academic policy and will bedealt with according to the GT Academic Honor Code.8. For any questions involving these or any other Academic Honor Code issues, pleaseconsult me, my teaching assistants, or www.honor.gatech.edu.Coverage of TopicsThe course balances the use of theory and practice in algorithm design by presenting thestudent with case studies from application domains. After an introduction to computationalscience and engineering applications, algorithm theory, and realistic models of computation,the course consists of two modules. The first focuses on the design and analysis of real-worldalgorithms, with an application walk-through from algorithmic techniques to constructionof the algorithm and finally application-level performance. The second module focuses onattaining high-performance implementations through algorithm engineering. These modulesdevelop the theoretic framework and complements the study with examples from real-worldproblems using implementations on modern computing systems.2Computational Science & Engineering Introduction1. Overview of Computational Science and Engineering Applications; characteristics andrequirements2. Computability and Complexity3. Ideal and Realistic Models of Computation4. Design of Parallel Algorithms5. Performance Analysis6. Multi-scale, multi-discipline applicationsReal-World Algorithms: Techniques to Applications1. Detecting Genomic Repeats: Divide and Conquer, cache-aware data structures, stringalgorithms2. Sequence similarity searching: dynamic programming, string algorithms, local align-ments, BLAST3. Parallel Sorting by Regular Sampling: Randomized algorithms, load balancing, parti-tioning, merging, and sorting4. Scientific visualization: greedy algorithms, 3d surface construction, marching cubes5. Graph partitioning: NP-completeness, approximation algorithms, adaptive mesh re-finement6. Graph analysis: search algorithms, semantic networks, betweenness centralityAlgorithm Engineering1. Modeling of the Memory Hierarchy2. Cache-friendly, cache-aware, and cache-oblivious algorithms3. Ideal and realistic models of parallel computation4. Parallel and distributed algorithms and applications5. Parallel disk models6. Problem solving frameworks7. Tools for Performance analysis8. Experimental methods and validation3Fall 2006, Tentative Course ScheduleWeek Date Lec Topic1 22 Aug 1 Intro. to Computational Science & Engineering24 Aug 2 Modern Computer Architecture, Models of Computation2 29 Aug 3 Review of Computability and Complexity31 Aug 4 Performance Analysis, High-Performance Computing3 5 Sep 5 Multi-scale, multi-discipline applications7 Sep 6 Scientific visualization4 12 Sep 7 Detecting Genomic Repeats14 Sep 8 Parallel Sorting by Regular Sampling5 19 Sep 9 Sequence similarity searching 121 Sep 10 Sequence similarity searching 26 26 Sep 11 Graph partitioning 128 Sep 12 Graph partitioning 27 3 Oct 13 Graph analysis 15 Oct 14 Graph analysis 28 10 Oct 15 Algorithm engineering and experiment design12 Oct 16 Modeling of the Memory Hierarchy917Oct-Fall Break19 Oct 17 Parallel disk models10 24 Oct 18 Cache-friendly and cache-aware algorithms26 Oct 19 Practical graph algorithms11 31 Oct 20 Problem solving environments2 Nov 21 Tools for performance analysis12 7 Nov 22 Realistic models of parallel computation9 Nov 23 Parallel and distributed algorithms and applications13 14 Nov 24 Irregular parallel algorithms16 Nov 25 Large-scale graph algorithms14 21 Nov 26 Multicore and Multithreaded