Fall 2017   CSCE 411 - 502   Design and Analysis of Algorithms

Location and Hours:

Tuesday, 5:30pm-8:00pm @ Room 113 Bright Building

Instructor:

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

Office hours: After every class in 113 Bright Buidling, and sometimes also joining TA's office hours.

TA and Grader:

TA: Xiaojing Yu. Email: xiaojingyu@tamu.edu

Office hours: 4--6pm on Mondays and 9:30--11:30am on Wednesdays, in Room B021 in Reed McDonald Building (RDMC).

Grader: Aditya Gurjar, Email: aditya.gurjar08@gmail.com

Course Materials:

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

Grading and Requirements:

Two mid-term exams: 23% each.

Final exam: 24%.

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

Homework policy: No late homework is accepted.

Homework:

1. Homework one. Due: 5:30pm on Tuesday, 9/12/2017 in class.     [Solution Set (sketch)]

    (1) Textbook page 370, Exercise 15.1-2.    (2) Textbook page 370, Exercise 15.1-3.

2. Homework two. Due: 5:30pm on Tuesday, 9/19/2017 in class.    [Solution Set (sketch)]

    (1) Textbook page 378, Exercise 15.2-1.    (2) Textbook page 378, Exercise 15.2-6.    (3) Textbook page 422, Exercise 16.1-3.

3. Homework three. Due: 5:30pm on Tuesday, 9/26/2017 in class.    [Solution Set (Sketch)]

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

4. Homework four. Due: 5:30pm on Tuesday, 10/3/2017 in class.    [Solution Set (Sketch)]

    (1) Textbook page 456, Exercise 17.1-1.    (2) Textbook page 458, Exercise 17.2-1.    (3) Textbook page 602, Exercise 22.2-7.

5. Homework five. Due: 5:30pm on Tuesday, 10/17/2017 in class.    [Solution Set (Sketch)]

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

6. Homework six. Due: 5:30pm on Tuesday, 10/24/2017 in class.    [Solution Set (Sketch)]

    (1) Textbook page 629, Exercise 23.1-3.    (2) Textbook page 629, Exercise 23.1-5.    (3) Textbook page 857, Exercise 29.1-4.    (4) Textbook page 858, Exercise 29.1-5.

7. Homework seven. Due: 5:30pm on Tuesday, 10/31/2017 in class.    [Solution Set (Sketch)]

    (1) Textbook page 878, Exercise 29.3-5.    (2) Textbook page 879, Exercise 29.3-6.    (3) Textbook page 879, Exercise 29.3-7.    (4) Textbook page 885, Exercise 29.4-1.

8. Homework eight. Due: 5:30pm on Tuesday, 11/7/2017 in class.    [Solution Set (Sketch)]

    (1) Textbook page 893, Exercise 29.5-5.    (2) Textbook page 893, Exercise 29.5-6.    (3) Textbook page 893, Exercise 29.5-7.

9. Homework nine. Due: 5:30pm on Tuesday, 11/21/2017 in class.

    (1) Textbook page 1065, Exercise 34.2-3.    (2) Textbook page 1066, Exercise 34.2-10.    (3) Textbook page 1077, Exercise 34.3-2.    (4) Textbook page 1086, Exercise 34.4-7.

10. Homework ten. Due: 5:30pm on Tuesday, 11/28/2017 in class.

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

Syllabus:
 
Date Lectures Reading
9/5/2017
Dynamic programming. Chapter 15
9/12/2017
Dynamic Programming. Greedy algorithms.
Chapters 15, 16
9/19/2017
Greedy algorithms.
Chapters 16
9/26/2017
Amortized analysis. Elementary graph algorithms.
Chapters 17, 22
10/3/2017
Midterm-exam One.

The exam will cover everything we have learned so far. It is open-book: you can bring anything on paper (book, homework, notes, etc.) But no electronic device is allowed.
[Solution]
10/10/2017
Elementary graph algorithms. Minimum Spanning Tree.
Chapters 22, 23
10/17/2017
Minimum Spanning Tree. Linear Programming.
Chapters 23, 29
10/24/2017
Linear Programming.
Chapter 29
10/31/2017
Linear Programming.
Chapter 29
11/7/2017
Midterm-Exam Two. The exam will cover everything we have learned so far, but with a focus on what we learned after midterm one. It is open-book: you can bring anything on paper (book, homework, notes, etc.) But no electronic device is allowed.

NP-completeness.

[Solution]

Chapter 34.
11/14/2017
NP-completeness.
Chapter 34
11/21/2017
NP-completeness. Approximation Algorithms.
Chapters 34, 35
11/28/2017
Approximation Algorithms.
Chapter 35
12/5/2017
Redefined Day. No class.

Final exam: 3:30--5:30pm on 12/13/2017 in 113 Bright Building



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.

Aggie Honor Code: "An Aggie does not lie, cheat or steal, or tolerate those who do." See http://aggiehonor.tamu.edu.