CS 351 Syllabus

Data Structures and Algorithms

Revised: June 2016 (Scott Barlowe)

Course Description

This course extends CS 151 by covering more advanced data structures, well-known algorithms, algorithm design techniques, algorithm analysis, and mathematics related to selected algorithms. The goal is to help students learn to write and analyze efficient programs that solve common and difficult problems. Data structures covered include representations of graphs, binary search trees, balanced binary search trees, AVL trees, heaps, and hash tables. Well-known algorithms covered include several sorting algorithms (such as insertion sort, merge sort, and Shell sort), binary search, and a sampling from other areas such as graph algorithms and NP-hard problems. Mathematics related to advanced algorithms and data structures will also be investigated. Mathematics covered may include, but are not limited to, probability and its application to Bayesian networks, Markov chains and decision processes, and Monte Carlo simulations; introduction to machine learning; and applications of linear algebra. Algorithm design techniques the students will practice include dynamic programming, divide-and-conquer, and greedy techniques.

Prerequisites and Notes

  • CS 151
  • Math 153
  • 4 Credit Hours

Objectives

By the end of this course, students will:

  • Use and implement a wide range of data structures.
  • Analyze the time complexity of a given algorithm.
  • Identify the most appropriate algorithm for a given problem and apply it to that problem.
  • Develop algorithms suitable for solving a complex problem.
  • Apply the appropriate mathematics related to advanced data structures and algorithms.

Text

Mark Allen Weiss, Data Structures and Algorithm Analysis in Java, Third Edition, Addison Wesley, 2011

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

  • Review of CS151 Concepts. The concepts reviewed include recursion, the distinction between abstract data types and data structures, and the data structures of arrays, linked lists, stacks, and queues.
  • Review of mathematics relevant to algorithm analysis including power rules, logarithms, and sigma notation.
  • Algorithm analysis with Big-O
  • The Java Collection Framework and abstract data types (including the idea of Maps) and typical implementation of data structures.
  • Graph terminology, representations, searching, sorting, and time analysis.
  • General trees, binary trees, binary search trees, AVL trees, heaps
  • Hash tables.
  • General sorting techniques.
  • Algorithm design techniques (dynamic programming, greedy algorithms, divide and conquer)
  • Undecidability and P versus NP
  • Advanced data structures and algorithms
  • Mathematics related to advanced data structures and algorithms including a sampling of the following
    • Introduction to Probability
    • Bayesian networks
    • Markov chains and decision processes
    • Machine learning
    • Introduction to and application of linear algebra (e.g. matrix manipulation, linear programming, image processing)
Office of Web Services