COURSE DESCRIPTION



COURSE DESCRIPTION

Department and Course Number: CSC 269 Course Coordinator: Laxmi P Gewali

Course Title: Introduction to Data Structure Total Credit: 3

Current Catalog Description: Introduction sequential and linked structures. File excess including sequential, indexed sequential and other file organizations. Internal structures including stacks, queues, trees, and graphs. Algorithms for implementing and manipulating structured objects. Big-O-notations. Prerequisites: CSC-136 and MAT 181. 3 credits

Text book: Data Structures and Algorithm Analysis in C++, By M A Weiss

Reference: Fundamental of Data Structures in C++,By Horowitz, Sahni, and Mehta

Course Goals: To high-light the importance of abstract data types (ADT).

To provide techniques in the use of appropriate data structure for problem solving.

To give hand-on experience in using linear and non-linear data structures.

To implement important data structure in C++

Prerequisites by Topic

1. Ability to program in high level language

2. Elementary computer organization

3. Assembly language programming

Major Topics Covered in the Course

1. Space/time analysis of algorithms, big-O, big-Omega, and Space/time analysis of algorithms, big-O, big-Omega, and big-Theta notation.

2. Arrays and their use to solve problem on matrix and polygon, etc. Stacks and queues.

3. Linked list and memory organization.

4. Searching and hashing: binary search, search trees, AVL trees, priority queue and heap, red-black trees, splay trees, huffman trees, perfect hashing, collision resolution.

5. Data structure for disjoint set, union/find algorithm

6. Sorting: Insertion Sort, quick sort, merge sort, heap sort, practical considerations for internal sorting.

7. Data structures for representing graphs, graph traversals, file organizations: sequential, random, linked, cellular partition, inverted files.

Laboratory Projects

All programming projects are done in C++

1. Design, analysis, and implementation of a program to find connected components in a two dimensional image.

2. Application of stack data structure for developing programs for expression parsing and evaluation.

3. Application of Binary Search trees for constructing Knowledge Trees.

4. Compare the time and space complexities of several sorting algorithms (insertion, quick, selection, merge, heap, etc.). Identify and verify data sets for which each sorting algorithm performs best and worst.

5. Develop C++ class for manipulating graphs and develop methods for solving simple problem on weighted graphs

Estimate CSAB Category Content

| |CORE |ADVANCED |

|Data structures |2 | |

|Algorithms |1 | |

Oral and Written Communications

Each student is required to prepare a written reports in the form of design, analysis and documentation of assigned programs

Social and Ethical Issues

No significant component

Theoretical Content

Approximately fifty percent of the lecture

Analysis and Design

Please refer to laboratory projects

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download