**CSE Algorithms | CSE 6140 - Fall 2014**

**Course Details:**

**Time:** TR 12:05 - 1:25pm

**Location:** Klaus 1456

**Instructor:** Bistra Dilkina

**Email:** bdilkina@cc.gatech.edu (best way to contact me)

**Office hours:** Thur 2-3pm in my office, Klaus 1304

**TA1:** Elias Khalil <lyes@gatech.edu>

**Office hours:**Mon 11:30-12:30 Klaus 1315, Thur 5:00-6:00pm Klaus CSE common area

**TA2:** Mehrdad Farajtabar <mehrdad@gatech.edu>

**Office hours:** Wed 4:00-5:00 Klaus 1315, Fri 4:00-5:00 Klaus 1315

**TA3:** Spurthi Amba Hombaiah<sah6@gatech.edu>

**Office hours:**Tue 5:00-6:00, Fri 1:30-2:30 Klaus CSE common area.

**Piazza Forum:** https://piazza.com/gatech/fall2014/cse6140/home

**Course Description**

This course will introduce students to designing scalable and effective algorithms for computational science & 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 2014 Tentative Topics: **also click for detailed Lecture SCHEDULE.

- 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, TSP, Steiner Tree
- Backtracking and Intelligent Search
- Approximation algorithms: PTAS, FPTAS, inapproximability
- Approximation algorithms: e.g. vertex cover, set cover, knapsack, max cut, k-center clustering
- Randomized Algorithms
- Heuristics / Local Search
- Experimental Methods and Validation

**Pre-requisites**: design and analysis of algorithms (GT CS 3510 or equivalent).

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 in homeworks and your project will require coding in your choice of language.

**Grading:**

- Midterm 25% (October 16, in class)
- Final 25% (December 11, 11:30am-2:20pm)
- Project 25%
- Homeworks 20%
- Class Participation 5%

**Textbooks**:

- (CLRS) T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, MIT Press, 2010. (required, should be available in bookstore)
- (KT) J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 1st ed., 2005 (strongly recommended)
- (DPV) S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006

**CLASS POLICIES**

- Class announcements will be sent to the Georgia Tech T-Square mailing list.
- 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.
- Each student must read and abide by the Georgia Tech Academic Honor Code, see www.honor.gatech.edu.
- 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.
- 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.
- When working on homework, you may work with other students in the class. However, each student \bf{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.
- 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.