CSC 316 — Data Structures
Fall 2017 Schedule of Lectures
Date  Lecture #  Topic  Assignment  Due 

Aug 17  1 
Overview, goals, logistics
(pdf)
Introduction (pdf) 

Aug 22  2 
Algorithm analysis
(pdf)
Chapter 4 (5th/6th) 
Project 1
(pdf)
(files)
HW 1 (pdf) 

Aug 24  3 
Recursion
(java code)
Chapter 3.5 (5th) / Chapter 5 (6th) 

Aug 29  4 
Stacks, queues
(pdf)
Chapter 5 (5th) / Chapter 6 (6th) 

Aug 31  5 
Linked lists
(pdf)
Chapter 3.23.4, 6 (5th) / Chapter 3.23.4, 7 (6th) Discussion of Project 1 
HW 2 (pdf)  HW 1 (pdf) 
Sep 5  6 
Linked lists (cont'd)
Dictionaries (pdf) Chapter 9.5 (5th) / Chapter 10.1 (6th) 

Sep 7  7 
Binary search
Chapter 9.3 (5th) / Chapter 10.3 (6th) Skip lists Chapter 9.4 (5th) / Chapter 10.4 (6th) 

Sep 12  8 
Introduction to trees
(pdf)
Chapter 7 (5th) / Chapter 8 (6th) 
HW 2 (pdf)  
Sep 14  —  No class (reading day)  Project 2 (pdf) (files)  Project 1 
Sep 19/20  —  First exam  
Sep 21  9 
Binary search trees
(pdf)
Chapter 10.1 (5th) / Chapter 11.1 (6th) 

Sep 26  10 
23 trees, Btrees
(pdf)
Chapter 10.4, 14.3 (5th) / Chapter 11.5, 15.3 (6th) 
HW 3 (pdf)  
Sep 28  11 
Discussion of Project 2 Splay trees (pdf) Chapter 10.3 (5th) / Chapter 11.4 (6th) 

Oct 3  12 
Priority queues
(pdf)
Heaps Chapter 8.18.3 (5th) / Chapter 9.19.4 (6th) 

Oct 5  —  No class (fall break)  
Oct 10  13  Leftist Heaps  HW 3 (pdf)  
Oct 12  —  No class (reading day) 
Project 3
(pdf)
(files)
HW 4 (pdf) 
Project 2 
Oct 17/18  —  Second exam  
Oct 19  14 
Uptrees for unionfind applications
(pdf)
Chapter 11.4 (5th) / Chapter 14.7.3 (6th) 

Oct 24  15  Introduction to graphs (pdf)
Chapter 13.1, 13.2 (5th) / Chapter 14.1, 14.2 (6th) 

Oct 26  16 
Minimum spanning trees
(pdf)
Chapter 13.6 (5th) / Chapter 14.7 (6th) Discussion of Project 3 

Oct 31  17 
Discussion of Project 3
Shortest paths Chapter 13.5 (5th) / Chapter 14.5 (6th) 
HW 5 (pdf)  HW 4 (pdf) 
Nov 2  18 
Shortest paths (cont'd), Topological ordering
Chapter 13.4.1, 13.4.3 (5th) / Chapter 14.6 (6th) 

Nov 7  19 
Graph traversals
(pdf)
Chapter 13.3 (5th) / Chapter 14.3 (6th) 

Nov 9  —  No class  Project 4 (pdf) (files)  Project 3 
Nov 14  20 
PageRank
(pdf)
Hashing techniques (pdf) Chapter 9.2 (5th) Chapter 10.2 (6th) 

Nov 16  21 
Discussion of Project 4
Hashing techniques (cont'd) 

Nov 21  22 
Sorting: Mergesort, Quicksort, Sorting lower bound, Radix sort
(pdf)
Chapter 11.111.4 (5th) / Chapter 12.112.4 (6th) 
HW 5 (pdf)  
Nov 23  —  No class (Thanksgiving Holiday)  
Nov 28  23  Greedy algorithms (ppt)  Project 4  
Nov 30  —  No class (reading day)  
Dec 4/5  —  Final exam 
Syllabus
Prerequisites
Students who wish to take this course must be CSC majors who have received a grade of C or better in both CSC 216 (Programming Concepts with JAVA) and CSC 226 (Discrete Math).Outcomes
The purpose of this course is to introduce the principles and underlying concepts of algorithm design, and enhance your problem solving and software development skills. To this end, a wide range of practical techniques for manipulating data in digital computers will be presented, along with a mathematical analysis of their performance.
At the conclusion of the course you should be able to:
 characterize the worstcase running time and space usage of algorithms and data structure operations as a function of input size;
 identify when recursion is useful, and design and implement complex recursive and iterative algorithms, including sorting algorithms;
 construct and use a number of data structures, including a stack, queue, linked list, array, tree, heap, graph, and hash table;
 explain how abstract data types (e.g., sequences or graphs) can be represented as different data structures (e.g., adjacency lists or adjacency matrices);
 describe and implement algorithms for binary search trees;
 describe and implement algorithms on graphs, including breadthfirst and depthfirst search, constructing minimum spanning trees, and finding shortest paths;
 describe and implement hashing functions and hash tables.
I encourage and expect you to participate actively in the learning process. In particular, I welcome your comments and questions as we cover material in class. Oneway lectures quickly become boring, both for you and for me. By asking lots of questions your understanding of the material will be deepened significantly, and the course will be much more fun!
Outline
The course will cover a wide range of data structures and associated algorithms, including:
 Properties of programs, running time, and asymptotics
 Array and linkedmemory implementations of lists, stacks, and queues
 Searching using lists, unbalanced tree structures (binary search trees, Splay trees) and balanced trees (23 trees, randomized binary search trees)
 Uptrees as sets with unionfind operations
 Graphs and graph algorithms (traversals, shortest paths, minimum spanning trees)
 Sorting (heap sort, merge sort, insertion sort, selection sort, quick sort)
 Hash tables and hashing techniques
Textbook
Students are required to purchase the following textbook:
 M. T. Goodrich, R. Tamassia, Data Structures and Algorithms in JAVA (6th edition), Wiley, 2014
The authors maintain a webpage with useful resources.
I will also make available an extensive set of lecture slides.
Grading
Students are required to complete all assignments and show all work in order to receive full credit. The final grade will be determined using the following weights:
 40% — Four programming projects (10% each)
 10% — Five homework assignments (2% each)
 30% — Two inclass exams (closed book, 15% each)
 20% — Final exam (comprehensive, closed book)
Policies
Attendance: Attendance is not mandatory but strongly encouraged. Students are responsible for making up any course material they miss.
Assignments: No hard copies of assignments or solutions will be handed out. New assignments and solutions will be announced in class and/or the course mailing list, and will be available on the course web page.
Submission: Students must submit their assignments as PDF or Word files using the submit facility. The deadline for submission is midnight (Eastern time) on the day due. Any deadline extensions are up to the discretion of the instructor, and will be announced to the whole class. Extensions may be provided to individual students only in advance of the submission deadline and only under extenuating circumstances.
Late Submission: No late assignments will be accepted and no partial credit will be given for late assignments without a valid excuse.
Cheating: Homework and projects are individual assignments and students are required to submit their own solutions. All students are bound by the University's academic integrity policies (refer to the relevant section below).
Teaching Assistant
Lingnan Gao (glingna@ncsu.edu) is the TA for this course.
His office hours are: Mon/Wed/Fri from 1:302:30 pm in 1229B EB2, or you may contact him to arrange for an online chat or video call at a mutually convenient time.
Feel free to contact the TA for any questions about the course.
Office Hours
My office is in Room 2306 of the EB II building.
My office hours are 1:302:30pm on Mondays/Tuesdays/Wednesdays. Distance students may either call me during those times, or may arrange to stop by or call at a different mutually convenient time.
Academic Integrity
Students are required to respect the NC State academic integrity policies.