PIR MEHR ALI SHAH ARID AGRICULTURE UNIVERSITY
University Institute of Information Technology
Data Structure and Algorithms (CS-443)
Credit Hours: 4(3-2) Prerequisites: Programming Fundamentals
and OOP (CS-323)
Teacher: H. M. Faisal Office # 111 hmfaisal@uaar.edu.pk
Course Learning Outcomes (CLOs)
At the end of course the students will be able to: Domain BT Level*
1. Implement various data structures and their algorithms, C 2,3
and apply them in implementing simple applications.
2. Analyze simple algorithms and determine their C 4,5
complexities.
3. Apply the knowledge of data structures to other C 3
application domains.
4. Design new data structures and algorithms to solve C 6
problems.
*BT- Bloom’s Taxonomy, C=Cognitive domain, P=Psychomotor domain, A=Affective
domain
Course Contents:
Abstract data types, complexity analysis, Big Oh notation, Stacks (linked lists and array
implementations), Recursion and analyzing recursive algorithms, divide and conquer
algorithms, Sorting algorithms (selection, insertion, merge, quick, bubble, heap, shell,
radix, bucket), queue, dequeuer, priority queues (linked and array implementations of
queues), linked list & its various types, sorted linked list, searching an unsorted array,
binary search for sorted arrays, hashing and indexing, open addressing and chaining,
trees and tree traversals, binary search trees, heaps, M-way tress, balanced trees,
graphs, breadth-first and depth-first traversal, topological order, shortest path,
adjacency matrix and adjacency list implementations, memory management and
garbage collection.
Course Objective:
This course aims at teaching the students to write programs that not only are correct but
also computation and space efficient and optimized for the intended use through
appropriate structuring/organization of the related data. Students will learn the standard
data structures such as linked lists, stacks, queues, trees, and graphs and the
algorithms that manipulate them. Students will also be introduced to the concept of
algorithm complexity analysis in order to make them realize the cost of the operations
they perform on their data structures.
Teaching Methodology:
Lectures, Written Assignments, Practical labs (With Lab manual), Semester Project.
Courses Assessment:
Mid Exam, Home Assignments, Quizzes, Project Presentation (Demonstration), Final
Exam.
Reference Materials:
1. Advanced Algorithms and Data Structures by Marcello La Rocca, 2021.
2. Data Structures and Algorithms Thinking Made Easy 5th Edition by Narasimha
Karumanchi, 2017.
3. Data Structures and Algorithms Thinking with Python by Narasimha Karumanchi,
2016.
4. “https://www.tutorialspoint.com/data_structures_algorithms/” , updated 2020.
5. Data Structures and Algorithms in C++ by Adam Drozdek , 4th edition, 2012
6. Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss, 4th edition,
2013.
7. Data Structures and Algorithms in C++ by Michael T. Goodrich 2nd Edition, 2011.
8. Introduction to Algorithms, Thomas H. Cormen et al, MIT Press, 3rd edition, 2009.
Week/Lecture # Theory Practical
Introduction: Fundamental OO Design
Lec-I Introduction to Data Structures- Practical-I and Implementation
Need and Significance Practice
Review of the Pre-requisite Fundamental OO Design
Lec-II Knowledge Practical-II and Implementation
Practice
Week
Abstract Data Types: Fundamental OO Design
1
Arrays, Structures and Classes and Implementation
Abstraction Practice
Lec-III Concrete and Abstract Data Practical-III
Types
Class invariants and pre-and
post conditions.
Complexity Analysis: Pseudocode and
Lecture Complexity Analysis Implementation of linear
Practical-I search.
-I Time and Space Complexity
Big Oh notation
Searching Algorithms: Comparison of searching
Week Arrays (basic and Object types) algorithms
2 Lec-II Algorithms on arrays. Practical-II
Recursion and analyzing
recursive algorithms.
Linear Search Comparison of searching
Lec-III Binary Search Practical-III algorithms
Sorting Algorithms: Implementation and
Selection Sort Comparison of sorting
Lec-I Practical-I algorithm
Bubble Sort
Insertion Sort
Sorting Algorithms: Implementation and
Week
Lec-II Divide and conquer algorithms Practical-II Comparison of sorting
3
Merge Sort algorithm
Quick Sort Implementation and
Comparison of sorting
Lec-III Practical-III
algorithm
Stack Array Implementation:
Stack: Basic/primitive functions Implementation of Static
Lec-I Practical-I
Stack supporting functions Stack.
Stack Array Implementation:
Stack Applications – Arithmetic
Week Expression,
Lec-II Practical-II Infix to Post fix Conversion
4 Infix, post-fix and pre-fix
notations.
In-to post transformation and
post-fix evaluation using
Lec-III Practical-III Post fix Evaluation
algorithm
Stack Array Implementation: Parenthesis matching
Parenthesis validation in validation implementation
Lec-I Practical-I
mathematical expression using
Week stack.
5 Multiple brackets validation Multiple brackets matching
Lec-II Practical-II
using stack. validation implementation
Any other example of validation Multiple brackets matching
Lec-III Practical-III
using stack. validation implementation
Queue Array Implementation: Implementation of queue
Queue: Basic/primitive operations
Lec-I Practical-I
functions
Queue supporting functions
Week
6 Circular queue Implementation of circular
Lec-II Practical-II
queue operations
Priority queue Implementation of priority
Lec-III Practical-III queue operations, SJF
Week Queue Array Implementation: Queue Applications – OS
7 Double ended queue process and Message queues
Lec-I Deiqueue Practical-I
Deoqueue
Lec-II Link List: Practical-II Implementation of double
Introduction of Link List ended queue.
Creating Different types of Link
List.
Linked List – Operations and Linklist implementation
Lec-III Representations Practical-III using primitive functions.
Stack Link List Stack Link list
Implementation: implementation using
Dynamic Implementation of primitive and supporting
Lec-I Practical-I functions.
Stack
Week Recursion using Linklist
8 Linklist operations on Stack
Sorted linked list Sorted Link list
Lec-II Practical-II
implementation.
Searching an unsorted linklist, Searching Link list
Lec-III Practical-III
implementation.
Midterm Exam
Queue Linklist Implementation: Dynamic Queue
Lec-I Linklist implementation of Practical-I Implementation
queue
Week
Linklist based Circular queue Circular queue
9 Lec-II Practical-II
implementation
Linklist based Variations: Priority queue
Lec-III Practical-III
deQueue, priority Queue. implementation
Queue Linklist Implementation: Implementation of doubly
Lec-I Linklist base Variations: doubly Practical-I linklist
linklist.
Week
Hashing: Implementation of circular
10 Lec-II Practical-II
Hashing and indexing doubly linklist
Hashing: Implementation of hashing
Lec-III Practical-III
Open addressing and chaining
Trees and Traversals:
Introduction and terminology,
Lec-I Binary trees and types, Practical-I Tree implementation
Tree traversals
Week Binary Tree representation,
11 basic operations
Binary Search Tree:
Lec-II Binary Search trees and Practical-II Tree implementation
Representation and operations
Lec-III M-Way tree Practical-III BST implementation
Week Balanced Tree and Heaps:
12 AVL tree
Lec-I Heap (max and min) Practical-I Heap implementation
Heaps and Associated
Algorithms
Lec-II Huffman Codes: Practical-II Max and Min Heap
Huffman Algorithm implementation
Lec-III Huffman Algorithm (cont..) Practical-III Heap Sort Implementation
Graphs: Graph implementation using
Terminology, operations and Adjacency List
Lec-I representation Practical-I
Graph traversals and searching
Week
algorithms (BFS-DFS)
13
Weighted Graphs Graph implementation using
Lec-II Practical-II
Dijkstra’s Algorithms Adjacency Matrix
Kruskal’s Algorithm DFS and BFS
Lec-III Practical-III
implementation
Shortest Path: Implementation of shortest
Lec-I Topological order Practical-I path algorithms.
Shortest path
Week Shortest Path: Implementation of shortest
Lec-II Practical-II
14 Using Adjacency matrix path algorithms.
Shortest Path: Implementation of shortest
Lec-III Adjacency list implementations Practical-III path algorithms.
Shortest Path: Implementation of Warshal
Lec-I Unweighted graph Practical-I Floyd’s algorithm
Weighted graph
Week Shortest Path: Implementation of Warshal
Lec-II Practical-II
15 Warshal Floyd’s Algorithm Floyd’s algorithm
Memory management: Implementation of memory
Lec-III Memory Management Practical-III management
Garbage collection.
Project Demos: Revision of programming
Lec-I Practical-I
Project Demos exercises
Week Project Demos Revision of programming
Lec-II Practical-II
16 exercises
Final Course Revision: Revision of programming
Lec-III Practical-III
exercises
Final term Exam
