CIS 680: Data Structures
Description
Data abstraction; introduction to algorithm analysis; data structures
and file strucures, including lists, trees, and graphs; searching and
sorting
Level, Credits, Class Time Distribution, Prerequisites
| Level |
Credits |
Class Time Distribution |
Prerequisites |
|
U G |
3 |
Three one-hour lectures |
CIS 560, 570; Stat 427; Math 366 |
Quarters Offered, General Information, Exclusions, Cross-Listings, etc.
Objectives
-
Master analyzing running time of "for" and "while" loops;
-
Master analyzing running time of simple recursive algorithms;
-
Master solving simple recurrence relations;
-
Master using asymptotic notation;
-
Be familiar with designing of divide and conquer algorithms;
-
Be familiar with designing backtracking algorithms;
-
Be familiar with designing branch-and-bound algorithms;
-
Be familiar with designing graph algorithms;
-
Be exposed to analyzing probabilistic algorithms;
-
Be exposed to NP-completeness.
Texts
- Brassard and Bratley, Fundamentals of Algorithmics, Prentice-Hall,
1996.
| Relationship to ABET Criterion 3 |
Relationship to CSE Program Objectives |
| a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
| XXX |
XXX |
X |
|
XX |
X |
|
|
X |
|
XX |
|
| 1a |
1b |
1c |
2a |
2b |
3a |
3b |
3c |
4a |
4b |
| XXX |
XXX |
XX |
|
|
|
|
X |
X |
XXX |
|
Topics
| No. of Weeks |
Topics |
|
1 |
Induction, Arithmetic series (Math review) |
|
1 |
Intro. to algorithm analysis |
|
1 |
Asymptotic notation |
|
1 |
Analysis of "for" and "while" loops |
|
1 |
Analysis of recursive algorithms |
|
1 |
Divide and conquer |
|
1 |
Backtracking; Branch-and-bound |
|
1 |
Probabilistic algorithms |
|
1 |
NP-completeness |
|
1 |
Exams and review |
Representative Lab Assignments
No lab assignments in this class.
Grading Plan
| Homeworks (several) |
20% |
| Midterm Exams |
40% |
| Final Exam |
40% |
Preparer Information and Date:
Syllabus prepared by Rafe Wenger, last modified April 30, 1999.