Course Description

In this course fundamental data structures will be explored that are indispensable when programming. Some major areas are objects, lists, arrays, stacks, queues, and more. Tradeoffs in terms of computational complexity and operations on these data structures are also discussed.
Credits: 3, prerequisites: CMPS 162.

Course Preview

All the information that is kept on a computer, both on disk and in memory, must be organized somehow. There are many different ways to organize data and that’s why there are many different data structures. All of them have a different purpose and different trade-offs. For example, one of the most basic data structures is the array that we have already seen in CMPS 162 Introduction to Programming, and it simply stores a list of things. It is really fast for accessing elements but can be slow when inserting elements. This can be contrasted with linked lists that are slower when retrieving elements, but are fast when inserting elements at the front of the list. We will look at many other common data structures and their advantages and disadvantages.

When solving a problem it is important to pick the right data structure. For example, when trying to find the shortest route between two cities, it makes sense to model the roads and intersections as a graph that consist of nodes and edges, which we already came across in CMPS 163 Business Analytics. Then we can apply Dijkstra’s algorithm which finds the shortest path, and this is essentially how route planning software works. We will also spend some time on the algorithmic aspects, specifically searching and sorting, as well as computational complexity. All of this knowledge is very useful for programming skills specifically, as well as for program solving skills in general.

Module 1: JavaScript – A Quick Overview
Module 2: Arrays
Module 3: Stacks
Module 4: Queues
Module 5: Linked Lists
Module 6: Sets
Module 7: Review and Midterm
Module 8: Dictionaries and Hashes
Module 9: Trees
Module 10: Graphs
Module 11: Sorting and Searching Algorithms
Module 12: Patterns of Algorithm
Module 13: Algorithm Complexity
Module 14: Review
Module 15: Final Exam

Course Objectives

1. Describe what kinds of data structures exist.
2. Identify when these data structures are applicable.
3. Compare data structures.
4. Perform operations on these data structures.
5. Have some familiarity with the computational complexity tradeoffs.
6. Model basic data structures with a programming language.

Course Topics

1. Data structures
2. Arrays, lists, stacks and queues
3. Sorting methods
4. Computational complexity