## [902 25701 01] Data Structures and Algorithms (I), Fall 2010 [902 25702 01] Data Structures and Algorithms (II), Spring 2011

### Synopsis

This is a one-year required course offered for the undergraduate students at the Department of Computer Science and Information Engineering, National Taiwan University.

### Information

• Instructor: Prof. Hsueh-I Lu
• Time and Place
• Classroom: Room 103, CSIE Building
• Time: 9:10am~12:10pm, Friday
• Office hours: 1:30pm~2:30pm, Wednesday, Room 516.
• TAs and TA hours:
• See the first set of slides.

### Exam

• Midterm (spring semester)
• Date: April 22, 2011
• Problem set: pdf
• Final (spring semester)
• Date: June 17, 2011
• Problem set: pdf
• Midterm (fall semester)
• Date: Nov 12, 2010
• Problem set: pdf.
• Final (fall semester)
• Date: Jan 14, 2011
• Problem set: pdf.

### Slides (Spring semester)

1. Syllabus
2. Depth-first search
3. Shortest path
4. Implementing Dijkstra's algorithm with Fibonacci heap
5. All-pairs distance
6. Minimum-weight spanning tree
7. Maximum flow and bipartite matching
8. String matching: Gusfield's algorithm
9. Suffix tree
10. Applications of suffix tree
11. Range minima query, lowest common ancestor, and document listing
12. NP versus P and polynomial-time reduction
13. Approximation algorithms

### Slides (Fall semester)

1. Syllabus
2. Why algorithms?
3. Hardness of a problem.
4. Asymptotic notation
5. An illustrating example: heapification problem
6. The comparison-based sorting problem
7. The non-comparison-based sorting problem
8. Divide-and-conquer and the master theorem
9. The matrix multiplication problem
10. The selection problem
11. Dynamic programming
12. Greedy approach
13. Intermission: feedback from the class
• (pptx: Dec 03 2010, 08:20),
14. Various implementations of set
15. 2-3-4 tree and B-tree
16. Nearest points
17. Segment intersection
18. Amortized analysis
19. Convex hull and farthest points
20. Magic of randomness

### Homeworks

• Homework 1: pdf (out: 10/1/2010, due: 10/8/2010)
• Homework 2: pdf (out: 10/15/2010, due: 10/22/2010)
• Homework 3: pdf (out: 10/22/2010, due: 11/5/2010)
• Homework 4: pdf (out: 10/29/2010, due: 11/19/2010 (extended))
• Homework 5: pdf (out: 12/10/2010, due: 12/24/2010)
• Homework 6: pdf (out: 12/24/2010, due: 1/7/2011)
• Homework 7: pdf (out: 2/25/2011, due: 3/11/2011)
• Homework 8: pdf (out: 3/6/2011, due (extended): 3/25/2011)
• Homework 9: pdf (out: 3/11/2011, due (extended): 4/1/2011)
• Homework 10: pdf (out: 3/18/2011, due (extended): 4/15/2011)
• Homework 11: pdf (out: 3/24/2011, due: 4/15/2011)

### Outline

• Foundations
• Sorting and order statistics
• Data structures
• Advanced design and analysis techniques