NEW COSC 310 Syllabus of Record                                                                             Attachment A

                                                                                                                                    3 credits

I. Catalog Description                                                                                                     0 lab hours

                                                                                                                                    3 lecture hours

 

COSC 310 Data Structures and Algorithms                                                                3c-0l-3sh

 

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.

 

   

II. Course Objectives:

 

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

 

  1. Use abstract data structures, including stacks, queues, trees, graphs, hash tables, and linked-lists, that are appropriate for a given algorithm.
  2. 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.
  3. Analyze the time and space efficiency of several significant classes of algorithms, sorting
  4. Use the object-oriented approach to program design and recognize its capabilities relative to the procedural paradigm.

 

 

III. Detailed Course Outline:

 

1. Linear Data Structures                                                                                                         (12 hours)

  1. Abstract Data Type
  2. array storage mapping functions
  3. linked lists - singly and doubly linked lists
  4. dynamic storage allocation – pointers
  5. stacks and queues – array-based and pointer-based implementations
  6. circular lists and multi-lists

 

2. Recursion/Sorting/Algorithms Analysis                                                                      (12 hours)

  1. recursion as a programming technique
  2. divide and conquer technique
  3. advanced sorting techniques- Mergesort and Quicksort
  4. algorithm efficiency analysis (big-O notation)
  5. Hashing- Hash functions, resolving collisions, efficiency of Hashing

 

3. Trees                                                                                                                                   (9 hours)

  1. binary trees
  2. ADT binary tree, array and pointer implementations of binary trees
  3. Binary tree traversals- preorder, postorder, and inorder traversals
  4. special applications of binary trees (binary search trees, heaps), parse tree
  5. other trees (AVL, b-trees, 2-3-trees)
  6. heap sort
  7. tree algorithm efficiency analysis

 

 

 

NEW COSC 310 Syllabus of Record                                                                                 Attachment A

 

 

4. Graphs                                                                                                                                 (6 hours)

  1. undirected and directed graphs, adjacency matrix and adjacency list
  2. graph traversals- depth-first and breadth-first search
  3. greedy method- single-source shortest path and all-pairs shortest paths
  4. 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)

 

 

IV.  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%

 

Grading Scale:  The grading scale will be:

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

 

Attendance policy:  The attendance policy will conform to the University wide 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.