Data Structures and Algorithms
Revised: June 2016 (Scott Barlowe)
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
Prerequisites and Notes
- CS 151
- Math 153
- 4 Credit Hours
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.
Mark Allen Weiss,
Data Structures and Algorithm Analysis in Java, Third Edition, Addison Wesley, 2011
Grading procedures and factors influencing course grade are left to the discretion
of individual instructors, subject to general university policy.
Attendance policy is left to the discretion of individual instructors, subject to
general university policy.
- Review of CS151 Concepts. The concepts reviewed include recursion, the distinction
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)