Western Carolina University

WCU is a University of North Carolina Campus

Home > Academics > Departments, Schools & Colleges > College of Arts and Sciences > College of Arts and Sciences Departments > Mathematics and Computer Science Department > Mathematics and Computer Science Academic Programs > Mathematics and Computer Science Undergraduate Majors > B.S. in Computer Science > Syllabi for Computer Science Undergraduate Courses > CS 351 Syllabus

CS 351 Syllabus

Data Structures and Algorithms

Revised: January 2007 (Mark Holliday)

Course Description

This course covers more advanced data structures, algorithm analysis, and design techniques so that students can write efficient programs that solve common and difficult problems.

Starting where CS 151 left off, we further develop the tree data structure and see more uses for it. We also introduce and analyse many other new data structures such as hashtables, sets, and graphs. The mathematical analysis will also be more sophisticated and well-defined in this course than it was in CS 151.

Text

Anany Levitin, Introduction to the Design and Analysis of Algorithms, Second Edition Addison Wesley, 2007.

Grading Procedure

Grading procedures and factors influencing course grade are left to the discretion of individual instructors, subject to general university policy.

Attendance Policy

Attendance policy is left to the discretion of individual instructors, subject to general university policy.

Course Outline

Chapter 1: Introduction. What is an algorithm; Fundamentals of Algorithmic Problem Solving; Important Problem Types; Fundamental Data Structures.
Chapter 2: Fundamentals of the Analysis of Algorithm Efficiency. Analysis framework; asymptotic notation and basic efficiency classes; mathematical analysis of nonrecursive algorithms; mathematical analysis of recursive algorithms.
Chapters 3: Design Technique: Brute Force. Selection sort and bubble sort; sequential search and brute force string matching; closest pair and convex hull problems by brute force; exhaustive search.
Chapters 4: Design Technique: Divide and Conquer. Mergesort; quicksort; binary search; binary tree traversals and related properties; closest pair and convex hull problems by divide and conquer
Chapter 5: Design Technique: Decrease and Conquer. Insertion sort; depth-first search and breadth-first search; topological sorting; variable size decrease algorithms.
Chapter 6: Design Technique: Transform and Conquer. Presorting; balanced search trees, heaps and heapsort; problem reduction.
Chapter 7: Design Technique: Space and Time Tradeoffs. Sorting by counting; input enhancement in string matching; hashing; b-trees.
Chapter 9: Design Technique: Greedy. Prim's algorithm; Kruskal's algorithm; Dijkstra's algorithm; Huffman trees.
Chapter 11: Limitations of Algorithm Power. P, NP, and NP-complete problems.
Chapter 12: Coping with Limitations of Algorithm Power. Backtracking; branch-and-bound.