CSCE411

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.

Grading and Requirements:

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. Homework assignment one. Due: 9:35am on Thursday 1/31/2019 in eCampus. [Sketch of Solution Set]

    (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

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.)