Data Structures& Algorithms Course Outline - University of Sargodha

Course Title: Data Structures& Algorithms

Course Code: CMP-3113

Course Structure: Lectures: 3 / Labs: 0

Credit Hours: 3

Prerequisites: CMP-2124 (Object Oriented Programming)

Course Objectives:

This course provides an introduction to the theory, practice and methods of data structures and
algorithm design.

Course Syllabus:

Introduction to Data Structure & Algorithm.Complexity Analysis.Linked Lists: Singly Linked
Lists, Doubly Linked Lists, Circular List.Stacks, Queues and Priority Queue. Recursion:
Function call and Recursion Implementation, Tail Recursion, Non-tail Recursion, Indirect
Recursion, Nested Recursion, Backtracking. Tree: Trees, Binary Trees, and Binary Search. Tree
Traversal.Insertion.Deletion.Balancing a Tree.Heap.B-Tree, Spanning Tree, Splay Trees.Graphs: Representation, Treversal, Shortest Path, Cycle Detection,.Isomorphic Graphs. Graph Traversal

Algorithms. Sorting: Insertion Sort, Selection Sort, Bubble Sort, Shell Sort, Heap Sort, Quick
Sort, Merge Sort, Radix Sort, Bucket Sort. Hashing: Hash Functions, Collision Resolution,
Deletion. Memory Management & Garbage Collection.

Course Outline:

1.      Complexity Analysis [ TB1: Ch. 1]

2.      Linked Lists: Singly Linked Lists, Doubly Linked Lists, Circular List. [TB1: Ch. 3]

3.       Stacks, Queues and Priority Queue. [TB1: Ch. 4]

4.      Recursion: Function call and Recursion Implementation, Tail Recursion, Nontail
Recursion, Indirect Recursion, Nested Recursion, Backtracking. [TB1: Ch. 5]

5.      Binary Tree: Trees, Binary Trees, and Binary Search. Tree Traversal. Insertion. Deletion.
Balancing a Tree. Heap. B-Tree. [TB1: Ch. 6]

6.      Graphs: Representation,Traversal, Shortest Path, Cycle Detection, Spanning Tree. [Ch. 8]

7.      Sorting: Insertion Sort, Selection Sort, Bubble Sort, Shell Sort, Heap Sort, Quick Sort,
Merge Sort, Radix Sort. [TB1: Ch. 9]

8.      Hashing: Hash Functions, Collision Resolution, Deletion. [TB1: Ch. 10]

9.      Memory Management: Garbage Collection

Textbook(s):

1. Data Structures and Algorithm Analysis in C++ by Mark A. Weiss, Addison-Wesley;
3^rdEdition (March 10, 2006). ISBN-10: 032144146X

Reference Material:

•          Data Structures and Algorithms in C++ by Adam Drozdek, Course Technology;
4^thEdition (August 27, 2012). ISBN-10: 1133608426

•          Data Structures Using C++ by D. S. Malik, Course Technology; 2^ndEdition (July 31,
2009). ISBN-10: 0324782012

Data Structures and Other Objects Using C++ by Michael Main and Walter Savitch,
Prentice Hall; 4^thEdition (March 6, 2010). ISBN-10: 0132129485

Note: This content is obtained from official documents of University of Sargodha and applied on BS Computer Science for Main Campus, Sub Campuses, and Affiliated Colleges.