Data Structures and Algorithms

Units: 12

Description:

95-771 is a one-semester, 12-unit course which covers the fundamental data structures and algorithms for information processing. The course uses the Java programming language to illustrate the concepts covered; students are expected to code their assignments in Java. Students enrolled in the course must have a prior background in programming (course work or practical experience). Students with an adequate grasp of programming should have little difficulty learning the Java constructs required to do their assignments.

It should be noted that this is not a Java programming course. With the exception of some initial background information, the course does not focus on the Java language itself, and students who have not studied Java are responsible for acquiring any additional required skills outside of class. Students without adequate programming preparation should consider taking an additional programming course as a pre-requisite or co-requisite to this course.

A major part of the course focuses on the design and analysis of data structures and their algorithms. Therefore, we will not be using the built-in Java classes that provide immediate access to such data structures.

Learning Outcomes:

At the completion of this course the student will be able to:

1. Design or select an appropriate algorithm for a particular problem.

2. Design or select an appropriate data structures for a particular problem.

3. Write programs that make good use of stacks, queues, linked lists, trees, graphs, and hash tables.

4. Analyze the runtime performance of algorithms in terms of Big O, Big Omega, and Big Theta notation.

5. Understand worse case, best case, average case and amortized analysis.

6. Understand the distinction between algorithm correctness and performance.

7. Understand the theory of NP-completeness.

8. Differentiate between problems that are computable and those that are not.

Prerequisites Description:

95-712 or 95-713

Syllabus: