CSE 331 Algorithms and Data Structures

# CSE 331 Algorithms and Data Structures (3 cr)

## Catalog Course Description

Linear data structures, trees, graphs and algorithms which operate on them. Fundamental algorithms for searching, sorting, string matching, graph problems. Design and analysis of algorithms.

## Course Outcomes (Letters refer to program outcomes; caps indicate greater emphasis.)

This course assumes that students are already familiar with advanced programming techniques including the definition of classes, and use of dynamic memory and linked data structures, including lists and trees.

In this course, students will survey fundamental data structures and many associated algorithms at a level above the programming level and without emphasis on software module development. The study of classical abstract data types will be fairly comprehensive. Emphasis will be placed on matching the appropriate data structures and algorithms to application problems: analysis of algorithms is crucial to making proper selections, so analysis is important in the course.

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

1. Apply fundamental algorithms to solving problems. (J)
2. Compare, choose and apply fundamental data structures that implement abstract data types, including sets, tables, queues, trees, and graphs. (b,J)
3. Analyze algorithm complexity and demonstrate comprehension of common complexity classes. (A,J)
4. Choose and apply algorithm strategies such as greedy, divide-and-conquer, dynamic programming, amortized analysis. (A,J)

## Program Outcomes covered in CSE 331

(a)
An ability to apply knowledge of computing and mathematics appropriate to the discipline
(b)
An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution
(j)
An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices

## Assessment

Assessment of how well outcomes are being achieved will be done by applying a rubric to a random sample of at least 25% of the students who have completed the work being used for assessment. Assessment tools are examinations and programming projects. For each outcome being assessed, each student in the sample will be judged to (a) exceed, (b) meet, or (c) fail to meet an objective standard designed to assess this outcome. Unless otherwise specified the thresholds used are: meet (70%), exceed (85%). We will say that this offering of the course achieved the particular outcome if and only if 70% or more of the students sampled were assessed to be in categories (b) or (c).
• Course outcome I, II, III, and IV assessed by
1. specific homework and specific exam questions.

## Topics

• Algorithm and complexity analysis
• Search trees
• B-trees and external files
• Hashing
• Priority queues and heaps
• Dynamic programming
• String matching
• Sorting and searching
• Recursion and recurrence relations
• Graphs and graph algorithms

## Textbook

• Data Structures and Algorithm Analysis in C++, 3rd Edition, Mark Allen Weiss, Addison Wesley, (2006)