CS 235 - Data Structures and Algorithms

Summary	Fundamental data structures and algorithms of computer science; basic algorithm analysis; recursion; sorting and searching; lists, stacks, queues, trees, hashing; object-oriented data abstraction.
Prerequisites	CS 142
Credits	3
Return to Course Listing

 

This document is not a syllabus. Instead, for ALL offerings of this course, this document states the purpose, expected objectives, and topics for the course. Faculty members teaching this course should adhere to these objectives and topics. Students taking this course can expect to achieve the objectives and cover the topics specified, and faculty members teaching follow-on courses can expect students to have been appropriately exposed to the prerequisite material as stated.  The “hours” for topics listed below reflect the approximate number of 50-minute class periods (or equivalent) devoted to each topic.

 

Purpose

CS 235 provides a hands-on introduction to data structures and algorithms. Through projects and exercises, students learn how to select and implement suitable data structures for various problems, how and when to use recursion, and how to analyze the cost of algorithms, especially sorting algorithms.

Objectives

At the end of this course, students should be able to:

1. Use the fundamental data types of computing (lists, stacks, queues, priority queues, sets, maps, trees, etc.).
2. Understand the major techniques for implementing the fundamental data types (linked lists, binary search trees, hashing, heaps, etc.) and implement several of them.
3. Properly use and select data structures from language-provided data-structure libraries.
4. Apply basic algorithm analysis.
5. Understand how recursion works and write programs using recursion to solve problems.
6. Make informed decisions about which sorting and searching algorithms to use in specific circumstances.
7. Write programs that require ~500 lines of code

 

 Topics

 

• Java skills review  (5 hours)
• Using data types in applications (5 hours)
• Recursion (2 hours)
• Big-Oh (2 hours)
• Searching (sequential search, binary search) (1 hour)
• Sorting (selection, insertion, mergesort, quicksort) (4 hours)
• Array and linked implementations of List (2 hours)
• Array and linked implementations of Stack and Queue (2 hours)
• Trees, binary trees, traversals (4 hours)
• Binary search trees (2 hours)
• AVL trees (3 hours)
• Hashing (chaining, linear probing, quadratic probing) (2 hours)
• Binary heaps and heapsort (2 hours)