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

Software Development Fundamentals (NC State CSC 216) and Discrete Mathematics (NC State CSC 226) 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 CSC216 & CSC226 Lecture Notes
  • 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.

Additionally, students in the Computer Programming Certificate must have completed Calculus I before taking CSC 316.

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…

A. Data Structures

A1. explain how abstract data types (e.g., lists, stacks, queues, maps, trees, priority queues, sets, and graphs) can be represented as different data structures;

A2. construct and use linear data structures, including array-based lists, linked lists, list-based stacks, and array-based queues;

A3. construct and use tree data structures, including general trees, binary trees, binary search trees, and balanced search trees

A4. construct and use hash tables that use complex hash functions and collision resolution strategies, including chaining and open addressing;

A5. construct and use priority queue data structures, including heaps;

A6. construct and use union-find data structures, including up-trees;

A7. construct and use graph data structures, including adjacency lists and adjacency matrices;

A8. employ phases of software development to design, implement, and test a software solution that uses efficient data structures and algorithms to solve a given problem;

B. Algorithms

B1. characterize the worst-case running time and space usage of iterative algorithms as a function of input size;

B2. characterize the worst-case running time and space usage of recursive algorithms as a function of input size;B3. design and implement complex iterative algorithms

B4. design and implement complex recursive algorithms

B5. describe and implement sorting algorithms, including bubblesort, insertion sort, selection sort, mergesort, quicksort, heapsort, counting sort, and radix sort;

B6. describe and implement tree algorithms, including tree traversals;

B7. describe and implement graph algorithms, including breadth-first and depth-first search, constructing minimum spanning trees, and finding shortest paths;

B8. describe algorithmic design paradigms, including divide-and-conquer, brute-force search, dynamic programming, and greedy algorithms;Algorithms

Course Requirements

Project 20% — One course project, which contains three parts: (1) Project proposal, (2) implementation & testing, and (3) experiment report
Workshops 30% –The average of all workshop assignments during the semester.
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: workshop and project coding activities
  • a weighted average of 60% or higher on the following components: workshop 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 1/18/2021