|CPSC 327||Data Structures and Algorithms||Spring 2015|
At the heart of computer science is the development of efficient algorithms for solving problems. This course focuses on the design and analysis of algorithms, addressing common algorithmic approaches (iterative, recursive, divide-and-conquer, greedy, backtracking, branch-and-bound, dynamic programming) as well as topics such as correctness, efficiency, complexity, and NP-completeness.
The choice of data structures used to implement an alorithm can have a significant impact on the simplicity and efficiency of a program, so data structures will also be considered. This course continues the study of data structures begun in CPSC 225, with a focus on graphs, trees, dictionaries, sets, and building your own data structure for a particular application.
|Course Web Page||
The Algorithm Design Manual (2nd ed)
This is both a textbook and a useful reference book. It is expected that you will acquire and read it.
Additional material will be handed out or posted on the course webpage.
CPSC 225 is required.
CPSC 229 is recommended.
|Rationale, Aims, and Objectives||
Introductory programming courses focus primarily on the syntax and semantics of a programming language - how to tell the computer what to do. More advanced programming courses begin to introduce the idea that there are typically multiple ways to solve a particular problem; a good programmer is concerned about finding a good solution to the problem.
This course addresses how to solve problems in a smart way, by designing efficient solutions and implementing those solutions in efficient and organized ways. Attention is also paid to ensuring the correctness of the solutions. This topic is at the very core of computer science - after all, you need an algorithm before you can write a program, you need it to work correctly, and, as you will see in this course, there can be enormous differences in the practicality of different algorithms.
The course has three main goals (and several subgoals):
By the end of the course, the successful student will be able to:
|Course Content Overview||
The course material can be arranged into four main units:
Algorithm Analysis: Determining whether one solution is better than another requires some yardstick by which quality can be measured. Time- and space-efficiency will be discussed, and big-Oh notation will be introduced - concepts which will be the fundamental tools used in the rest of the course. Specific objectives include:
Algorithm Design: The study of algorithm design will be organized around three main categories of algorithms: iterative algorithms, recursive algorithms, and algorithms for optimization problems. (A fourth category - randomized algorithms - may be addressed if time permits.) In each case, the emphasis will be on strategies for developing algorithms of that type rather than simply presenting long lists of specific algorithms. Specific objectives include:
ADTs and Data Structures: Appropriate abstract data types (ADTs) are important for simplifying the development and implementation of algorithms, and the performance of an algorithm can be hampered by an inefficient implementation of the ADTs used. This component of the course will focus on developing a toolbox of abstract data types, a set of guidelines for choosing an appropriate ADT, and a toolbox of concrete data structures for efficiently implementing the ADTs studied. Basic ADTs such as lists, stacks, queues, priority queues, and binary trees and their typical implementations will be quickly reviewed. New ADTs such as sets, systems of sets, dictionaries, ordered collections, and graphs will be introduced along with efficient implementations for these data types. Specific objectives include:
Complexity and NP-Completeness: After a semester-long focus on the efficiency of algorithms, some questions might come to mind: Are some problems fundamentally harder to solve than others? Are there problems that can't be solved? We'll delve briefly back into more theoretical topics to examine these questions (and what "hard" actually means), and to look at some of the hardest problems in computer science. Specific objectives include: