Instructor

Dr. Jason King

Dr. Jason King

Computer Science

Phone: 919-515-8954
Email: jtking@ncsu.edu
Instructor Website
Research Website

CSC 316 Data Structures and Algorithms

3 Credit Hours

The course will cover the following topics: Abstract data types; abstract and implementation-level views of data types. Linear and branching data structures, including stacks, queues, trees, heaps, hash tables, graphs, and others at discretion of instructor. Best, worst, and average case asymptotic time and space complexity as a means of formal analysis of iterative and recursive algorithms. The course will cover a wide range of data structures and associated algorithms, including:

  • Properties of programs, running time, and asymptotics
  • Array and linked-memory implementations of lists, stacks, and queues
  • Searching using lists, unbalanced tree structures (binary search trees, splay trees) and balanced trees (AVL trees, 2-4 trees, red-black trees)
  • Up-trees as sets with union-find operations
  • Graphs and graph algorithms (traversals, shortest paths, minimum spanning trees)
  • Sorting (including heap sort, merge sort, insertion sort, selection sort, quick sort, counting sort, radix sort)
  • Hash tables and hashing techniques

Prerequisite

CSC 216 Programming Concepts – Java and CSC 226 Discrete Mathematics with a grade of C or higher (if you do not meet these requirements, please consult with the instructor). Specifically, since course content varies from school to school, students are expected to know:

  • the topics outlined under  <a href=”https://www.go.ncsu.edu/csc216materials”>Lecture Notes</a><br>
  • Java, JUnit, git version control, and the associated tools outlined at http://go.ncsu.edu/csc216-development-environment (you should have this development environment installed and configured before starting the CSC 316 course). NOTE: The CSC 316 course does not teach you how to program in Java, how to write JUnit tests, how to use git version control, or how to use any of the CSC216 development environment tools.

Course Objectives

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.

Upon successful completion of this course, a student will be able to…

  • characterize the worst-case 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 breadth-first and depth-first search, constructing minimum spanning trees, and finding shortest paths;
  • describe and implement hashing functions and hash tables.

Course Requirements

Project/s 26% — Course projects
Labs 24% — The average of all lab assignments during the semester. Your lowest lab grade will be dropped and not used when calculating your final course average.
Exam 1 14% — Exam 1 is cumulative
Exam 2 14% — Exam 2 is cumulative
Final Exam 18% — The final exam is cumulative
Exercises/Participation 4% — Your participation each week on online activities and/or online discussions

To pass CSC316, you must meet the following three requirements:

  • a weighted average of 60% or higher on the following components: Exam 1, Exam 2, and Final Exam
  • have a weighted average of 60% or higher on the following components: lab and project coding activities
  • a weighted average of 60% or higher on the following components: lab and project written activities

Textbook

Data Structures and Algorithms in Java – M. T. Goodrich, R. Tamassia
Edition: 6th edition
ISBN: 978-0470383261
Web Link: http://bcs.wiley.com/he-bcs/Books?action=index&itemId=1118771338&bcsId=8635
This textbook is required

Computer and Software Requirements

Please review minimum computer specifications recommended by NC State University and Engineering Online.

Updated 4/17/2020