**CS4349.001: Advanced Algorithms**
**Design
and Analysis**

**FALL 2014: TR: 4:00 -- 5:15 @ ECSS 2.203**

**Instructor: R. Chandrasekaran**

**Office:** ECSS 4.611

**Phone:** (972) 883-2032

**Office Hours:** W 3:00 -- 4:30

**URL:** `http://www.utdallas.edu/~chandra`

email: chandra AT utdallas DOT edu

**Teaching Assistant:**

**Office & Hours:**

**email**:

**Teaching Assistant:**

**Office & Hours:**

**email**:

**Textbook:** ``Introduction to Algorithms,'' T.H. Cormen,
C.E. Leiserson ,R.L. Rivest, and C. Stein,
Third Edition.

**Prerequisites:** CS 3345 (Data structures and algorithms): Abstract
data types: lists, stacks, queues, trees, search trees. Hashing.
Priority queues: heaps. Sorting and searching. Graphs: representation and
algorithms. Running-time analysis of algorithms and order
notation.

**Course Objectives:**

- Ability to use asymptotic notations, solve recurrences, perform algorithm analysis
- Ability to design, analyze, and prove correctness of algorithms based on Divide-and-Conquer techniques
- Ability to design, analyze, and prove correctness of algorithms based on Greedy techniques
- Ability to design, analyze, and prove correctness of algorithms based on Dynamic Programming techniques
- Ability to design, analyse and prove correctness of graph algorithms

**Topics:** Order Notation, Recurrence relations. Divide and conquer,
greedy methods, dynamic programming. Graph algorithms: Minimum spanning trees, Shortest path problems, Maximum flow problems.

**Grades:** Assignments -20%; Exam I: (25%); Exam II: - (25%);
Exam III: (30%)

There will be no programming assignments.

- Lecture #1
- Lecture #2
- Lecture #3
- Lecture #4
- Lecture #5
- Lecture #6
- Lecture #7
- Cheat-Sheet
- Lecture #8
- Lecture #9
- Lecture #10
- Lecture #11
- Lecture #12
- Assignment #1
- Assignment #2
- Assignment #3
- Assignment #4
- Assignment #5
- Assignment #6
- Sample-Graph
- Solution #1
- Solution #2
- Solution #3
- Solution #4
- Solution #5
- Solution #6

**Student Responsibilities:**

- Assignments are due in class on the specified date.
Turn in what is completed by the deadline for partial credit. No late
submissions will be accepted.
- All submissions must be your own work. Identical
assignments will not be accepted.
- Regular class attendance and participation is expected
and is the responsibility of each individual. There is a strong
correlation between regular class attendance and good performance. If a
student should elect not to attend a class, (s)he
is responsible for any handouts, announcements, reading material and
contents of missed lectures.
- You are subject to all rules pertaining to integrity of
the University -- see http://www.utdallas.edu/judicialaffairs/UTDJudicialAffairs-AcademicIntegrity.html