DSA Course Outline 20022024 042844pm
DSA Course Outline 20022024 042844pm
DSA Course Outline 20022024 042844pm
Instructor Name/Cluster Instructor Name: Mr. Nadeem Sarwar Status □ Regular □ Visiting
Head/Subject Expert
Lab Engineer: Ms. Fatima Zulfiqar
Cluster Head Name: Dr. Iram Noreen Subject Expert Name: Mr. Tahir Iqbal
Course Aims This subject deals to make students convenient in building a memory and time efficient data structures for
the implementation of large-scale (data intensive) computer systems.
Course Objectives The primary objective of the course is to help students understand the importance of data structures and well-designed algorithms
for efficient management of computing resources while programming. Popularly employed linear and nonlinear data structures
are described from the perspective of their specification, application, and implementation. Several sorting and searching
techniques are also discussed to help students design efficient solutions for real life problems. Basic knowledge of algorithm’s
complexity analysis is also provided for identification of time costly processes.
Course Outcomes CLO After successful completion of this course, the students should be able to: PLO
CLO 1 Explain and compare different data structures and their applications 1
CLO 2 Apply appropriate data structures according to the given scenarios and application domain 2
CLO 3 Analyze time complexity of different algorithms 2
CLO 4 Design efficient algorithm(s) to solve real world problems 4
Course Abstract Data Types (ADTs) , Linear data structures (Stacks, Queues, Linked list), Non-linear data structures (Trees, Graphs),
Recursion and recursive algorithms, Sorting Algorithms (Bubble, Insertion, Selection, Quick, Merge, Shell, Heap), Searching
Description/Catalogue (Linear, Binary, Depth First, Breadth First, Shortest Path, Minimum Spanning Trees), Hashing and Collision resolution
techniques (Open Addressing, Separate Chaining, Double Hashing), Data Compression (Huffman’s Code), Complexity Analysis
of Algorithms (Big-O notation).
Lecture Plan (16 Weeks) Week # Lecture/ Reference Text
and Date Contact Topic to be covered
Hour #
Course Introduction:
1 Course Policies/Overview/Course Contents/Course
Week 1 2 Objectives
Introduction to data structures and types
List as Simple Data Structure
1 Simple List as Array
Week 2 Operation on list
2
Traversing, Searching, Inserting and Deleting data element
1 Linked List:
Concept of pointer and linked list
Week 3 2 Static and dynamic variables
Types of Linked list
Implementation of linked list using pointer
1 Operations on Linked List:
Traversing and Searching data element
Week 4
Inserting and Deleting data element
2
Doubly link list
Implement a doubly-linked list.
1 Stack:
Introduction to stack, definitions.
Week 5 Abstract data types of stack and their implementations.
2 Applications of stack.
Evaluating an expression in postfix form, Converting infix
expression to postfix
1 Operations on Stack:
Stack operation
Week 6 2 Implementation of stack using array.
Implementation of stack using linked list.
Applications of stack.
1 Queues:
Introduction to queue, definitions.
Week 7 2 Physical model, linear implementation, circular queue.
Abstract data types of queue and their implementations.
Applications of queue.
1 Operations on Queue:
Insertion and deletion
Week 8 2 Traversing and searching
Applications of queue structure.
1 Tree:
Introduction to tree: definitions.
Week 9 2 Tree size, level and depth in tree.
Binary tree.
Implementation of binary tree.
1 Operations on Tree:
Week 10 Expression tree (Pre-order, In-order and Post-order)
2 Binary Search Tree
AVL Tree
1 Heaps:
Introduction
Week 11 2 Max Heap
Min Heap
Min-Max Heap
1 Graphs:
Week 12 Definition of graph
2
Graph traversals
Shortest path (greedy algorithm)
Graphs as data structures
1 Recursive Algorithms:
Week 13 Base and general case
2 Applications such as recursive evaluation of the binomial
coefficient and recursive traversal of a linked list
Comparison of recursive and iterative algorithms
1 Searching and Sorting Algorithms:
2 Algorithms for sorting
Week 14 Insertion sort, bubble sort, merge sort, quick sort, heap sort.
Sequential search: searching an ordered table, index
sequential search.
Compare different sorting and searching algorithms.
1 Hash Table and Time efficiency of algorithms:
Week 15 Hashing algorithms
2 Big-O notation and time-behavior
Simple examples
Week 16 1
Revisions
2
Final Exam
Semester Calendar for Assignments/Quizzes/Project
Assignments/ Projects Assignment Quiz Project Title Assignment/Project Result Date of
and quizzes Plan Week # No. No. Quiz Date Due date Assignment/Project/Q
uiz
1
2
3 Assignment-1 Quiz-1
4 Assignment-1
5 Assignment-1, Quiz-1
6 Assignment-2 Quiz-2
7 Assignment-2
8 Assignment-2, Quiz-2
10 Assignment-3 Quiz-3
11 Assignment-3
12 Assignment 3, Quiz 3
13 Quiz-4
14 Assignment-4
15 Assignment-4
16 Assignment 4, Quiz 4
Instructor Name: Nadeem Sarwar
Instructor Signature ____________________________
Date ____________________________