3 Semester Credit Hours

Course Description

This course is a substantial introduction to fundamental data structures and algorithms, their implementation and run-time analysis. Asymptotic notation is introduced and used in this course to derive and express the run-time performance of algorithms and of operations on data structures used to implement important abstract data types. The range of abstract data types and data structures explored in this course begins with the elementary (lists, stacks, queues), and goes as far as binary heaps, binomial heaps, disjoint set forests, and graphs. Algorithms on graphs included in the course solve problems that range from searching to minimum spanning trees and shortest paths. (For precise details see the list of course topics.) The course not only teaches the facts of algorithms and data structures but also the art of applying them to solve problems.

Prerequisites

• One year of college-level calculus (NMTH 1111 and NMTH 1112)

• An undergraduate course in Discrete Mathematics (like NCSC 2201) covering sets, sequences, functions and relations, undirected and directed graphs, asymptotic notation for the running time of algorithms, (concept of proof, and techniques for constructing proofs (by contradiction, by induction)

• A course in programming in C++ or Java (NCSC 1001)

• An undergraduate lower division course in data structures (NCSC 1011)
• General prerequisite: Students must have the knowledge resulting from completing all coursework in the curriculum for a BS degree in Computer Science from a regionally-accredited institution in the United States or the equivalent from a foreign institution; performance level in this coursework should be equivalent to a cumulative undergraduate GPA of 2.9 or better on 4.0 scale.

Course Objectives

On successful completion of this class a student should be able to do the following.

For each abstract data type, data structure, or technique presented in this class:

• define and use the basic terminology correctly
• explain why it is important
• provide and discuss specific uses of it in computer science
• identify its important characteristics
• identify any variants or special cases of it
• perform the basic operations associated with it
• use it to solve problems

For each of the algorithms discussed in class:

• explain its purpose and important characteristics
• give the kinds of problems it is applicable to
• trace its workings given specific input
• explain the key steps it takes
• analyze its time and space requirements
• demonstrate that it correctly solves the problem it is designed for
• implement it from scratch in a modern programming language (e.g. Java)

Given an algorithmic problem:

• identify data structures, algorithms, etc. of potential relevance
• modify these to make a solution to the problem
• present an intellectually economical solution
• implement a solution in a modern programming language (e.g. Java)
• discern whether a supposed solution is correct

Course Topics

The following topics will be covered in the order given.

• Algorithms and Worst-Case Performance in Asymptotic Notation
• Priority Queues, Binary Heaps and Heapsort
• Mergesort and Quicksort
• Recurrence Relations
• Lower Bounds for Sorting
• Selection and Quickselect
• Stacks, Queues and Lists
• Dynamic Sets and Hashing
• Binary Search Trees
• Binomial Trees
• Binomial Heaps
• Disjoint Set Forests
• Graphs
• Minimum Spanning Trees
• Single-source Shortest Paths
• Matrices and Shortest Paths
• All-Pairs Shortest Paths: the Floyd-Warshall Algorithm
• Breadth-First Search
• Depth-First Search
• Edge Classification induced by Depth-First Search Topological Sorting

Technical Requirements:

You will need to have access to C++ or Java compilers for this course.  In addition, you will be required to have Windows Media Player to view the lectures. For the standard technical requirements, please go to the link below: http://www.waldenu.edu/c/Files/DocsGeneral/Getting_Started_Guide.pdf

Textbook

Required: Introduction to Algorithms (includes CD), T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein 2nd ed., 2001, McGraw-Hill, ISBN: 0-07-297054-5.

Disclaimer: The course syllabus may differ slightly from this. Course descriptions will be provided in your online course. Textbook information is provided only to give more information about the course.  Do Not use this information to purchase a textbook.  Up-to-date information will be provided when you register.