Data Structures and Algorithms
Revised: August 2018
Course Description
This course covers 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.
Corequisites and Notes
- CS 253
- Math 255
- 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, 2012
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)