CSC 541: Advanced Data Structures
MW 2:20-3:35 1226 EB-II
| Instructor: | Christopher G. Healey | |
| Contact: | 2266 EB-II healey@csc.ncsu.edu |
|
| Office Hours: | M 10:00-11:00 in 2266 EB-II, or by appointment | |
| TA: | Nazli Dokuzoglu | |
| Contact: | ndokuzo@ncsu.edu | |
| Office Hours: | W 10:00-11:00 in 2237 EB-II | |
C++ tutorial notes are available via this link in PDF format. Additional supplemental notes that I have made available include:
My goals for you are to:
| Text: | File Organization and Processing, Alan L. Tharp, John Wiley & Sons | |
| Supplemental Texts: | File Structures, M. J. Folk, B. Zoellick, and G. Riccardi, Addison-Wesley Fundamental Algorithms, D. Knuth, Addison-Wesley Searching and Sorting, D. Knuth, Addison-Wesley |
This is a course on advanced data structures for searching and sorting. The course will introduce a number of internal and external searching and sorting techniques. A detailed description of physical storage devices, OS file managers, OS I/O managers, field and record structures, and sequential, direct, and indexed storage and retrieval will be provided. Algorithm efficiency will be discussed, both in terms of execution time and space.
Below is a tentative course schedule. Please note that time frames for each topic will be confirmed in class and are subject to possible changes. Homework assignment due dates and the midterm exam date will be announced in class.
|
Topic
|
File Organization and Processing; Tharp
|
| physical disk | Ch. 1, pp. 11-22; Ch.14, pp. 37-373 |
| order notation | Ch. 1., pp. 4-8 |
| fields, arrays, records | Ch. 2, pp. 27-28 |
| primary, secondary keys | Ch. 2, pg. 27; Ch. 6, pp.147-152 |
| sequential, direct file access | Ch. 2, pp. 25-28; Ch. 3, pp. 36-39 |
| records | Ch. 2, pp. 27-28 |
| keysorting | Ch. 2, pp. 28-34 |
| indexing | Ch. 4, pp. 112-123 |
| quicksort | Ch. 13, pp. 342-346 |
| heapsort | Ch. 13, pp. 347-352 |
| BST, AVL tree | Ch. 3, pp. 77-85; Ch. 8, pp. 199-202; Ch. 8, pp. 203-209 |
| cosequential merging | Ch. 13, pp. 352-354 |
| k-way merge | Ch. 13, pp. 354-358 |
| multiphase merge | Online notes |
| B-trees | Ch. 9, pp. 221-250 |
| kd-trees | Ch. 12, pp. 314-320 |
| linear hashing | Ch. 3, pp. 36-43, pp. 57-60; Ch. 10, pp. 276-284 |
| chained hashing | Ch 3, pp. 61-63 |
| collision resolution techniques | Ch 3, pp. 43-68 |
| dynamic hashing | Ch. 10, pp. 267-275 |
Apart from material in the textbook related to individual lectures, no additional readings will be assigned. Students will be informed in class at the beginning of each week which sections of the textbook will be covered during that week’s lectures.
All programming assignments will be submitted with Wolfware, the university's web-based assignment submission system. The submission system can be accessed via http://courses.ncsu.edu/csc541. All written assignments will be submitted in-class.
Homework 1: Written component due Wednesday, September 2, executables due midnight Friday, September 4; "In-Memory vs. Disk-Based Serching"
Homework 2: Due midnight Friday, September 25; "In-Memory Indexing with Availability Lists"
Homework 3: Due in-class Wednesday, October 14; "Sorting Algorithms"
Homework 4: Due midnight Friday, November 6; "External Searching"
Homework 5: Due midnight Friday, December 4; "External Chained Hashing"
Midterm Exam: 2:20-3:35 Wednesday, October 21, 1226 EB-II
Final Exam: 1:00-4:00 Wednesday, December 9, 1226 EB-II
Grades for the course will be made up from five assignments, a midterm exam, and a final exam. You are expected to attend all lectures, read all relevant portions of the text, and read any on-line notes and programs I provide. Missed exams cannot be made up without an official university excuse. Homework should be submitted via Wolfware by 11:59PM on the due date. Late homework will not be accepted under any circumstances.
Final grades will be calculated as follows, using +/- grading:
Homework: 40%
Midterm Exam: 25%
Final Exam: 35%
Students who audit CSC 541 will be marked P (pass) or F (fail). They will be required to obtain a passing grade (60% or better) on all five homework assignments. They will not be required to write either the midterm or the final exam.
If you miss (or plan to miss) class(es), contact me as soon as possible to identify the material to be covered during your absence. You are expected to "make up" the material by reading the appropriate section(s) in the textbook, and meeting with me as necessary to discuss the material.
To enroll in this course you must be registered as a computer science (CSC) or computer engineering (CPE) major. If you are not a designated major in one of these programs, your registration in CSC 541 will be cancelled. All instruction will be in C++.
The university provides a detailed policy on academic integrity. This policy can be found in the Code of Student Conduct. It is understood that when you sign and submit your homework, term project, and final exam, you are implicitly agreeing to the university honor pledge: "I have neither given nor received unauthorized aid on this test or assignment."
Academic dishonesty (e.g., cheating or plagiarism) will not be tolerated under any circumstances. If you are having difficultly with any part of the course material, please see me or the TA as soon as possible. I will do everything I can to help you with any course-related problems you may be having. If you are found to be guilty of academic dishonesty, however, I will then do everything I can to see that you are punished as forcefully as possible. This may include asking to have you suspended or expelled from the course, the program, and/or the university. At the very least, you will receive -50% for the assignment or exam in question, and your name will be placed on record with the university as having committed an academic offence (multiple offences during your academic career will result in suspension or expulsion from the university). I take absolutely no pleasure in pursuing cases of academic misconduct, and would ask that you please do not put me in this position.
Compliance will be monitored by the MOSS software, which is very good at detecting similarities in programs. MOSS has been used to successfully identify cases of copying or plagiarism in a number of CSC courses, and will be applied to all programming assignments you complete.
All effort will be made to ensure that no students with disabilities are denied any opportunity to successfully complete this course. If you have specific requirements that need to be addressed, please contact me immediately. Possible changes can include (but are not necessarily limited to) rescheduling classes from inaccessible to accessible buildings, or providing access to auxiliary aids such as tape recorders, special lab equipment, or other services such as readers, note takers, or interpreters. This may also include oral or taped tests, readers, scribes, separate testing rooms, or extension of time limits.