# COSC 310 Data Structures and Algorithms

Prerequisite: COSC 210

Fundamental concepts of data design and implementation, data abstraction, data structures, arrays, linked-lists, stacks, queues, recursion, trees, graphs, and hashing. The course will also cover sorting algorithms, divide and conquer techniques, greedy methods, and analysis of algorithms. The object-oriented paradigm will be employed in this course using an object-oriented language.

Course Objectives:

Upon successful completion of this course, the students will be able to:

a. Use abstract data structures, including stacks, queues, trees, graphs, hash tables, and linked-lists, that are appropriate for a given algorithm.
b. Implement abstract data structures, objects, and algorithms using an object-oriented approach and determine the effect of the implementation on the performance of the algorithm.
c. Analyze the time and space efficiency of several significant classes of algorithms, sorting
d. Use the object-oriented approach to program design and recognize its capabilities relative to the procedural paradigm.

Detailed Course Outline:

1. Linear Data Structures (12 hours)
a. Abstract Data Type
b. array storage mapping functions
d. dynamic storage allocation – pointers
e. stacks and queues – array-based and pointer-based implementations
f. circular lists and multi-lists

2. Recursion/Sorting/Algorithms Analysis (12 hours)
a. recursion as a programming technique
b. divide and conquer technique
c. advanced sorting techniques – Mergesort and Quicksort
d. algorithm efficiency analysis (big-O notation)
e. Hashing- Hash functions, resolving collisions, efficiency of Hashing

3. Trees (9 hours)
a. binary trees
b. ADT binary tree, array and pointer implementations of binary trees
c. Binary tree traversals – preorder, postorder, and inorder traversals
d. special applications of binary trees (binary search trees, heaps), parse tree
e. other trees (AVL, b-trees, 2-3-trees)
f. heap sort
g. tree algorithm efficiency analysis

4. Graphs (6 hours)
b. graph traversals – depth-first and breadth-first search
c. greedy method – single-source shortest path and all-pairs shortest paths
d. Applications of graphs – spanning trees, minimum spanning trees (Prim’s and Kruskal’s algorithms)
e.  graph algorithm efficiency analysis

5. Two Class Tests (3 hours)
Total hours in semester = (42 hours)

Evaluation Method:

Evaluation: The final grade of the course will be determined as follows:
Two Class Tests    30-40%
Final Comprehensive Exam  20-30%
Projects, Assignments & Participation 40-50%

90-100% = A, 80-89% = B, 70-79% = C, 60-69% = D, and < 60% = F.

Attendance policy:  The attendance policy will conform to the universitywide attendance criteria.

Sample Projects:  (All projects will use an Object-Oriented Approach.)

• Project #1 Create a class definition of a linked-list using array-based or pointer-based implementation and then insert, retrieve, and delete items from it.
• Project #2 Convert an infix arithmetic expression into a postfix form and evaluate it using an array    implementation of a stack.
• Project #3 Develop a program for preorder, postorder, and inorder traversals of a binary search tree.
• Project #4 Develop a program for graph traversal using either depth-first or breadth-first search.
• Project #5 Create a program to find minimum spanning tree (MST) either using Kruskal’s or Prim’s algorithm.
• Project #6 Create a program for either mergesort or quicksort.

Required Textbook, Supplemental Books and Readings:

Sahni, Sartaj Data Structures, Algorithms, and Applications in C++, McGraw-Hill, 1998, ISBN #0-07-109219-6

• Computer Science Department
• Stright Hall, Room 319
210 South Tenth Street
Indiana, PA 15705
• Phone: 724-357-2524
• Fax: 724-357-2724
• Office Hours
• Monday through Friday
• 7:30 a.m. – 12:00 p.m.
• 1:00 p.m. – 4:00 p.m.