CSCE 3110 Data Structures

Instructor: Dr. Yan Huang Spring 2007

Announcements

1. 04/23/07, Please fill in Exit Survey.

1. 04/15/07, Assignment 5 is posted and will be due 04/30/07 before class. Assignment 5 is an optional assignment and will replace the lowest score of your previous four assignments.

2. 03/25/07, Assignment 4 is posted and will be due 04/09/07 before class.

3. 03/07/07, sample Solution for Assignment 2 has been posted

4. 02/26/07, Project is posted and will be due 04/29/07 before midnight.

5. 02/19/07, Assignment 3 is posted and will be due 03/05/07 before class.

6. 02/18/07, the Solution for Assignment 1 has been posted. Standard Library Programming Guide has been added to the LINKS section of this webpage.

7. 02/12/07, contact information and office hours for the TA are posted. The due date for Assignment 2 has been posted to Feb. 26, 2007.

8. 02/04/07, Assignment 2 is posted and will be due 02/19/07 before class.

9. 01/29/07, click here to see a short description of “project” command on csp machines.

10. 01/29/07, Assignment 1 is posted and will be due 02/05/07 before class.

11. 01/17/07, Today’s class is cancelled due to inclement weather. We will meet next Monday for the first class.

12. 01/16/07,Join the mailing list

Syllabus [pdf]

Instructor:	Dr. Yan Huang
Office:	Research Park, F251, tel: 940-369-8353
Email:	huangyan ‘at’ cs.unt.edu
Class hours:	MW 02:30-03:50pm, Research Park B142
Office hours:	MW 01:15-02:15pm and 4:00-5:00pm

Teaching assistant:	Sowjanya Vasarla
Office:	F205 and F236
Email:	sv0097 ‘at’ unt.edu
Office hours:	W 12:00pm – 2:00pm, F 2:00pm – 4:00pm (F205) , TTH 10:00am – 2:00pm (F236)


Course description:	This course provides an introduction to the design and analysis of fundamental data structures and algorithms. Basic data structures to be covered including arrays, lists, stacks, queues, trees, heaps, priority queues, hash tables, and graphs. Algorithms include searching, sorting, tree and graph traversal using the above data structures. Algorithm analysis techniques will be emphasized when using the data structures for designing efficient algorithms. The objectives of this course are: · Understand graph representations and algorithms. · Understand time and space analysis for both iterative and recursive algorithms and be able to prove the correctness a non-trivial algorithm. · Be able to translate high-level, abstract data structure descriptions into concrete code. · Understand how real-world problems map to abstract graph problems. · Be able to communicate clearly and precisely about the correctness and analysis of basic algorithms (both oral and written communication). A special emphasis is placed on programming and hands-on experience, meant to reinforce the theoretical aspects covered in lectures.

Schedule and Class Notes

Some sample codes in c++ that we used in class are available from here

(the directory will be updated incrementally with more examples).

Date	Lecture	Reading material	NB
01/15/07	Martin Lurther King Jr. Day – no class	-	-
01/17/07	Class cancelled due to inclement weather	-	-
01/22/07	Introduction. Course Overview.[ppt]	Weiss, chap. 1	-
01/24/07	C++ Programming Style [ppt]	Weiss, chap. 1	-
01/29/07	C++ Programming Style (cont.) [ppt]	Weiss, chap. 1	Assignment 1 is posted and will be due 02/05/07 before class.
01/31/07	Algorithm Analysis [ppt]	Weiss, chap. 2	-
02/05/07	Algorithm Analysis (cont.) [ppt]	Weiss, chap. 2	Assignment 2 is posted and will be due ~~02/19/07~~ 02/26/07 before class.
02/07/07	Algorithm Analysis (cont.) [ppt]	Weiss, chap. 2	-
02/12/07	Arrays (review) [ppt]	Weiss, chap. 3	-
02/14/07	Iterative and Recursive Algorithms [ppt]	Weiss, chap. 2	-
02/19/07	Stacks and Queues [ppt]	Weiss, chap. 3.	Assignment 3 is posted and will be due 02/05/07 before class.
02/21/07	Trees [ppt]	Weiss, chap. 4.	-
02/26/07	Binary Search Trees [ppt]	Weiss, chap. 4.	Project is posted and will be due 04/29/07 before midnight.
02/28/07	Balanced Search Trees [ppt]	Weiss, chap. 4.4	-
03/05/07	Multi-way Search Trees [ppt]	Weiss, chap. 4.7	Sample Exam Questions
03/07/07	Multi-way Search Trees [ppt]	Weiss, chap. 4.7	-
03/12/07	Exam I
03/14/07	Exam I discussion	-	-
03/19/07 03/21/07	Spring Break – no class	-	-
03/26/07	Graph I [ppt]	Weiss, chap. 9	Assignment 4 is posted and will be due 04/09/07 before class.
03/28/07	Graph I [ppt]	Weiss, chap. 9	-
04/02/07	Graph II [ppt]	Weiss, chap. 9	-
04/04/07	Priority Queue [ppt]	Weiss, chap. 6	-
04/09/07	Hashing [ppt]	Weiss, Chap. 5	-
04/11/07	Graph and project discussion.	-	-
04/16/07	Sorting [ppt]	Weiss, Chap. 7	Assignment 5 is posted and will be due 04/30/07 before class.
04/18/07	Sorting II [ppt]	Weiss, Chap. 7	-
04/23/07	Fun with Algorithms	-	-
04/25/07	Mock Exam	-	-
04/30/07	Project Presentation	-	Presentation order
05/02/07	Project Presentation	-	-
05/07/07	Final (1:30pm – 3:30pm)	-	-

Note*: The class notes are a compilation and edition from many sources. The instructor does not claim intellectual property or ownership of the lecture notes.

Assignments

1. Assignment 5 is posted and will be due 04/09/07 before class.

2. Assignment 4 is posted and will be due 04/09/07 before class.

3. Project [.htm, .pdf] is posted and will be due 04/29/07 before midnight.

4. Assignment 3 is posted and will be due 03/05/07 before class.

5. Assignment 2 is posted and will be due ~~02/19/07~~ 02/26/07 before class (sample solution).

6. Assignment 1 is posted and will be due 02/05/07 before class (sample solution).

Books

Required textbook

Data Structures and Algorithm Analysis in C++, 3^rd edition, M.A.Weiss

Buy this book (new) from Amazon.
Compare prices (new or used) at BestBookBuys

Links

1. Standard Library Programming Guide

2. Source code for the examples in the text.

3. Various programming tutorials