CS 253 Data and File Structures: Course Outline

2018/19 Catalog data A software design course, which develops concepts and techniques for structuring and manipulating data both in the computer and on external storage devices. Topics include a review of basic data structures, balanced tree structures, graphs, sequential and direct access files, external sorting. An introduction to data base systems is also provided.

Prerequisites CS 152.

Textbook Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser "Data Structures and Algorithms in JAVA", John Wiley & Sons, Inc.

Instructor: Neli P. Zlatareva, Ph.D., Professor of Computer Science.

Office MS303.

Phone (860) 832-2723.

E-mail

Web site

Office hours MW 12:05 p.m. – 1:15 p.m.

TR 10:40 a.m. - 11:40 a.m., 1:30 p.m. – 2:00 p.m.

Course Objectives Having completed this course successfully, the student should:

  1. Be familiar with the use of data structures as the foundational base for computer solutions to problems.
  2. Become introduced to and investigate the differing logical relationships among various data items.
  3. Understand the generic principles of computer programming as applied to sophisticated data structures.
  4. Comprehend alternative implementations using the differing logical relationships and appreciate the significance of choosing a particular logical relationship for implementation within real-world setting.
  5. Demonstrate the ability to plan, design, execute and document sophisticated technical programs to handle various sorts of data structures.

NOTES:

  1. NO CELL PHONES ALLOWED IN THE CLASSROOM.
  2. THE USE OF PERSONAL COMPUTERS LIMITED TO CLASS ACTIVITIES.
  3. CLASS ATTENDANCE IS A MUST FOR SUCCESSFUL COMPLETION.

Topics in the course and number of lecture hours each

1. Introduction to algorithm analysis: pseudo code, algorithm

efficiency (examples: sorting and searching problems),

asymptotic and empirical analysis of algorithms.3.0 hours

2. Introduction to data structures. Linear data structures: vectors,

stacks, queues, linked lists and sequences (operations,

implementations, applications.) 3.0 hours

3. Non-linear data structures: binary trees and general trees

(operations, implementations and applications).

Binary search trees. 6.0 hours

4. Priority queues and heaps: using a heap to implement

a priority queue. Heap sort. 3.0 hours

5. Dictionaries, hash tables. 3.0 hours

6. Balanced search trees: AVL trees, (2,4) and red-black trees. 6.0 hours

7. Sets, selection, and sorting: merge and quick sorts. 3.0 hours

8. Non-linear data structures: graphs (representations,

implementations). Path algorithms: depth-first and

breadth-first searches, transitive closure, topological

ordering). 6.0 hours

9. Non-linear data structures: weighted graphs. Minimum

spanning tree and shortest path algorithms. 6.0 hours

10. Tests and student presentations. 6.0 hours

Total: 45.0 hours

Programming assignments There will be 4 programming assignments, and a research project, which students can do in pairs or individually. There will be a penalty for late submissions.

Academic honesty All programming assignments must be an individual effort of the student submitting the work for grading. See the section "Policy on Academic Honesty" in the CCSU Student Handbook.

Project For the research project, students will choose a graph algorithm to study in depth (2 – 4 references in addition to the book will be chosen by the student), develop an implementation of that algorithm in a selected application context, and write a research paper describing the results of this research. Everybody/team will summarize the results of the research project in a 15 minutes talk given in class. The research paper (typically 8 - 10 pages long), andthe program must be submitted for grading.

Tests There will be two tests during the semester and a final exam.

Grades Programming assignments5 points each

Project20 points

Tests 15 points each

Final exam 30 points

Final grade for the course will be defined according to the following table:

Total points Final grade

------

93 - 100 A

90 - 92.99 A-

87 - 89.99 B+

83 - 86.99 B

80 - 82.99 B-

77 - 79.99 C+

73 - 76.99 C

70 - 72.99 C-

67 - 69.99 D+

63 - 66.99 D

60 - 62.99 D-

below 60 F