RAIK 283: Data Structures and Algorithms

RAIK 283: Data Structures and Algorithms*

Fall 2011, TuTh 1:30-3:20pm

Kauffman 112

Instructor

TAs

Name

Office

Office Hours

Email

Phone

Prof. Ying Lu

Schorr Center 104

M 1:30-2:30pm, W 11:30-12:30pm

and by appointment

ylu at cse.unl.edu

472-5793

Matt Munger

Kauffman 206B

Tu 12:00-1:30pm

F 8:30-10:00am

mungermatthew at gmail.com

560-8022

Neema Bahramzad

Announcements:

· Final exam 1:00-3:00pm, Tuesday, December 13.

Lecture Notes	Reading List
1. Administrivia
2. Introduction	Chap 1
3. Algorithm Analysis	Chap 2.1
4. Asymptotic Notations	Chap 2.2
5. Analysis of Nonrecursive Algorithms	Chap 2.3, Appendix A
6. Analysis of Recursive Algorithms	Chap 2.4, 2.5, Appendix B
7. Brute Force Algorithms	Chap 3
8. Divide and Conquer1: MergeSort and QuickSort	Chap 4.1, 4.2
9. Divide and Conquer2: Binary Search and Multiplication	Chap 4.3, 4.5
10. Divide and Conquer3: Closest Pair and Convex Hull	Chap 4.6
11. Decrease and Conquer1	Chap 5.2, 5.3
12. Decrease and Conquer2	Chap 5.5, 5.6
13. AVL and 2-3 Trees	Chap 6.3
14. Heap and HeapSort	Chap 6.4
15. Space and Time Tradeoff	Chap 7.1, 7.2
16. Greedy Algorithms MST	Chap 9.1, 9.2
17. Dijkstra’s Algorithm	Chap 9.3
18. Huffman Code	Chap 9.4
19. Iterative Improvement	Chap 10
20. Computing a Binomial Coefficient and Longest Common Subsequence	Chap 8.1
21. Warshall’s and Floyd’s Algorithms	Chap 8.2
22. 0-1 Knapsack Problem	Chap 8.4
23. P, NP & NP-Complete	Chap 11.3
24. Approximation Algorithms for NP-hard Problems	Chap 12.3
25. Finite State Machines with Output	Rosen, Chapter 12.2
26. Finite State Machines with No Output	Rosen, Chapter 12.3

Homework Due Date

Homework1 1:30pm Oct 4

Homework2 1:30pm Oct 20

Homework3 1:30pm Nov 10

Homework4 1:30pm Dec 1