Spring 2019
CSCE 411-501 Design and Analysis of Algorithms |

**Location and Hours:**

Tuesdays and Thursdays, 9:35am-10:50am @ Room 113 Bright Building

**Instructor:**

Prof. Anxiao (Andrew) Jiang, 309B Bright Building. Email: ajiang@cse.tamu.edu

Office hours: 12:30pm-1:30pm on Tuesdays and Thursdays.

**TA and Grader: **

TA: Pulakesh Upadhyaya. Email: pulakesh@tamu.edu

Office hours: 4:00-5:30pm on Tuesdays and 9:30-11:00am on Wednesdays in Room 526 Bright Building.

Grader: Palash Parmar. Email: palparmar@tamu.edu

**Course Materials:**

Textbook: __Introduction to Algorithms (3rd Edition)__, by *Thomas Cormen*, *Charles Leiserson*, *Ronald Rivest* and * Clifford Stein*.

Two mid-term exams: 23% each.

Final exam: 24%.

Homework and in-class mini-tests: 30%.

Homework Policy: An electronic copy should be turned in in eCampus. No late homework is accepted.

**Homework:**

(1) Textbook page 370, Exercise 15.1-2. (2) Textbook page 370, Exercise 15.1-3. (3) Textbook page 408, Problem 15-7.

2. Homework assignment two. Due: 9:35am on Thursday 2/7/2019 in eCampus. [Sketch of Solution Set]

(1) Textbook page 422, Exercise 16.1-3. (2) Textbook page 436, Exercise 16.3-3. (3) Textbook page 446, Problem 16-1.

3. Homework assignment three. Due: 9:35am on Tuesday 2/19/2019 in eCampus. [Sketch of Solution Set]

(1) Textbook page 602, Exercise 22.2-7. (2) Textbook page 611, Exercise 22.3-5.

4. Homework assignment four. Due: 9:35am on Tuesday 2/26/2019 in eCampus. [Sketch of Solution Set]

(1) Textbook page 614, Exercise 22.4-2. (2) Textbook page 623, Problem 22-3.

5. Homework assignment five. Due: 9:35am on Tuesday 3/5/2019 in eCampus. [Sketch of Solution Set]

(1) Textbook page 630, Exercise 23.1-9. (2) Textbook page 679, Problem 24-3.

6. Homework assignment six. Due: 9:35am on Thursday 3/21/2019 in eCampus. [Sketch of Solution Set]

(1) Textbook page 730, Exercise 26.2-6. (2) Textbook page 731, Exercise 26.2-11.

7. Homework assignment seven. Due: 9:35am on Thursday 3/28/2019 in eCampus. [Sketch of Solution Set]

(1) Textbook page 878, Exercise 29.3-5. (2) Textbook page 879, Exercise 29.3-6.

8. Homework assignment eight. Due: 9:35am on Thursday 4/11/2019 in eCampus. [Sketch of Solution Set]

(1) Textbook page 885, Exercise 29.4-1. (2) Textbook page 893, Exercise 29.5-5; (3) Textbook page 893, Exercise 29.5-6.

9. Homework assignment nine. Due: 9:35am on Tuesday 4/30/2019 in eCampus.

(1) Textbook page 1100, Exercise 34.5-1; (2) Textbook page 1101, Problem 34-1 (a), (b).

**Syllabus:**

Date |
Lectures |
Reading |

1/15/2019 Tuesday |
Dynamic Programming. |
Chapter 15 |

1/17/2019 Thursday |
Dynamic Programming. |
Chapter 15 |

1/22/2019 Tuesday |
Dynamic Programming. |
Chapter 15 |

1/24/2019 Thursday |
Greedy Algorithms. |
Chapter 16 |

1/29/2019 Tuesday |
Greedy Algorithms. |
Chapter 16 |

1/31/2019 Thursday |
Amortized Analysis. | Chapter 17 |

2/5/2019 Tuesday |
Elementary Graph Algorithms. | Chapter 22 |

2/7/2019 Thursday |
Elementary Graph Algorithms. | Chapter 22 |

2/12/2019 Tuesday |
No class. Self-study to prepare for the midterm. | Chapter 22 |

2/14/2019 Thursday |
Midterm Exam 1 (The exam covers everything that we have learned up to 2/7/2019. It is an open-book exam: you can use your textbook, notes, homework, or anything on paper. However, NO electronic device is allowed.) | |

2/19/2019 Tuesday |
Minimum Spanning Tree. | Chapter 23 |

2/21/2019 Thursday |
Single-Source Shortest Paths. | Chapter 24 |

2/26/2019 Tuesday |
Single-Source Shortest Paths. | Chapter 24 |

2/28/2019 Thursday |
Maximum Flow. | Chapter 26 |

3/5/2019 Tuesday |
Maximum Flow. | Chapter 26 |

3/7/2019 Thursday |
Maximum Flow. | Chapter 26 |

3/12/2019 Tuesday |
No class due to spring break. | |

3/14/2019 Thursday |
No class due to spring break. | |

3/19/2019 Tuesday |
Linear Programming. | Chapter 29 |

3/21/2019 Thursday |
Linear Programming. | Chapter 29 |

3/26/2019 Tuesday |
Linear Programming. | Chapter 29 |

3/28/2019 Thursday |
Midterm Exam 2. (The exam covers everything that we have learned up to now, with a focus on what we learned after midterm exam one. It is an open-book exam: you can use your textbook, homework, or anything on paper. However, NO electronic device is allowed.) | |

4/2/2019 Tuesday |
Linear Programming. | Chapter 29 |

4/4/2019 Thursday |
Linear Programming. | Chapter 29 |

4/9/2019 Tuesday |
NP-Completeness. | Chapter 34 |

4/11/2019 Thursday |
NP-Completeness. | Chapter 34 |

4/16/2019 Tuesday |
NP-Completeness. | Chapter 34 |

4/18/2019 Thursday |
NP-completeness. | Chapter 34 |

4/23/2019 Tuesday |
NP-completeness. | Chapter 34 |

4/25/2019 Thursday |
NP-completeness. | Chapter 34 |

4/30/2019 Tuesday |
No class. (Redefined day for Friday) | |

12:30-2:30pm on 5/2/2019, Thursday |
Final Exam. (The exam covers everything that we have learned this semester, with a focus on what we learned after midterm exam two. It is an open-book exam: you can use your textbook, homework, or anything on paper. However, NO electronic device is allowed.) |

Statement: The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact Disability Services, currently located in the Disability Services building at the Student Services at White Creek complex on west campus or call 979-845-1637. For additional information, visit http://disability.tamu.edu.

“An Aggie does not lie, cheat or steal, or to tolerate those who do.” See http://aggiehonor.tamu.edu