CSE 207 / CSE 208

CSE 207 / CSE 208

Course Code: CSE 207 / CSE 208
Course Name:
Data Structures
Credit Hours:
Detailed Syllabus:

Data structures: Concept of data types, abstract data types

Arrays: Maximization ordered lists, sparse matrix representation of arrays.

Stacks, Queues and Recursion: Fundamentals, Different types of Stack and Queues, Recursion: Direct and indirect recursion; simulation of recursion; depth of recursion; removal of recursion;

Linked lists: Different types of Linked list and their operations.

Trees: Basic terminology, binary trees, binary tree representation, binary tree traversal; Extended binary trees: 2-trees, internal and external path lengths, Huffman codes; algorithm; threaded binary trees, binary tree representation of trees; Application of Trees: Set representation, decision trees, game trees; counting binary trees.

Graphs: Introduction, definitions and terminology, graph representations, traversals, connected components and spanning trees, shortest path and transitive closure, activity networks, topological sort and critical path, enumerating nil path.

Internal Sorting: Searching, bubble sort, shell sort, insertion sort, selection sort, quick sort, heap sort, 2-way merge sort. How fast can we sort? Sorting on several keys, practical considerations for internal sorting.

External Sorting: General idea: Sorting with disks: K-way merging, buffer handling (or parallel operation, run generation, Sorting with Tapes: Balanced merge sorts, polyphase merge, sorting with fewer than 3 tapes.
Symbol Tables: Static tree tables, dynamic tree tables; Hash Tables: Hashing functions, overflow handling, theoretical evaluation of overflow techniques.

Files: File, queries and sequential organizations; Indexing Technique: Cylinder-surface indexing, hashed indexes, tree indexing- B- trees; Tree indexing.