Sir Syed University of

Engineering & Technology

Data Structures & Algorithms

(CS-212)

Computer Science Department

Sir Syed University of Engineering & Technology
University Road, Karachi 75300
http://www.ssuet.edu.pk
 Sir Syed University of Engineering & Technology
Department of Computer Science
Course Plan of Data Structures and Algorithms (CS-212)
Spring Semester 2020

Data Structures and Algorithms (CS-212)

Credit Hours: 3+1 Prerequisites: Programming
Fundamentals

Class: BS (CS) (Sec A, B, C, D & E) Semester: 3rd

Instructor/s Name: Mr. Mohammad Asad Abbasi Tutorial/ Mon-Fri at 9:00
Mr. Adeel Saeed Consultation am to 11:00 am
Ms. Syeda Sabeen Fatima Time:

Contact E-mail: m.asadabbasi@yahoo.com

adeel_csku@yahoo.com
syeda_sabeenfatima@hotmail.com

Course Description:
This course covers the concepts related to design, analysis and implementation of various data structures
and algorithms to solve real world problems using an object‐oriented programming language. Topics
include elementary data structures (including arrays, stacks, queues and lists), advanced data structures
(including trees and graphs), the algorithms used to manipulate these structures, and their applications to
solving practical engineering problems.

Course Learning Outcomes (CLOs):

At the end of the course the students will be able to:

1. Implement various data structures and their algorithms, and apply them in implementing simple
applications.
2. Analyze simple algorithms and determine their complexities.

3. Apply the knowledge of data structures to other application domains.

4. Design new data structures and algorithms to solve problems.

Course Content:
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.
Teaching Methodology:

Lectures, Written Assignments, Practical labs, Semester Project, Presentations

Course Assessment:

Sessional Exam, Home Assignments, Quizzes, Project, Presentations, Final Exam

Reference Materials:

1. Data Structures and Algorithms in C++ by Adam Drozdek

2. Data Structures and Algorithm Analysis in Java by Mark A. Weiss
3. Data Structures and Abstractions with Java by Frank M. Carrano & Timothy M. Henry
4. Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss
5. Java Software Structures: Designing and Using Data Structures by John Lewis and Joseph Chase

Marks Distribution:
Assignments: 5%
Quizzes: 5%
Final Lab: 20%
Midterm Exam: 20%
Final Exam: 50%
Total: 100%
 WEEKLY LECTURE PLAN
S.No Topics
Week1 Data Structures and their Operations:
Introduction, Overview of Data Structures, Data Structure’s operations, Types of
Data Structures, Abstract data types

Week 2 Algorithm Analysis:

Introduction, Pseudo coding, Control Structures, Analysis of Algorithms, Efficiency
of Algorithms, Complexity of Algorithms, Asymptotic Notation/ Big O Notations

Week 3 Pointers:
Introduction, Pointer vs Arrays, Arrays of Pointer, Pointer to Pointer, Null pointer,
Void Pointer, Invalid Pointer, Dangling Pointer Reference Variable, Dynamic Array
(malloc, new, free, delete operators). Constructor in class, types of Constructor
(Null, Default, Parametric, Overloading, Copy Constructor)

Week 4 & 5 Sorting and Searching Techniques:

Linear Search, Binary Search, Efficiency of Algorithms, Bubble Sort, Selection Sort,
Insertion Sort, Quick Sort, Shell Sort, Radix Sort, Merge Sort, Heap Sort

Week 6 Linked Lists:

Introduction, Representation of Linked lists in memory, Traversing a linked list,
Searching a linked list, Memory allocation, Insertion and Deletion, Efficiency of
Linked lists, Header Linked lists, Two way lists, Two way Circular Header linked
list, Operations on Two way CHL

Week 7 Stacks:
Introduction, Stack Model, Array & Link List representation of Stacks,
Representation of Stack through Class ,Recursion, Parenthesis Checking through
stack, Efficiency of Stack. Polish Notations, Prefix, Infix, Postfix

Week 8 Queues:
Introduction, Queue Model, Array & Link List implementation of Queues, Deques,
Priority Queues, Linked list & Array implementation of Priority Queues

Week 9 Mid Term Exam

Week 10 & 11 Trees:
Basic Terminologies, Binary Trees, Array/Link List representation of binary trees in
memory, Traversing Binary Trees, Pre, In, and Post-order traversal, Binary Search
Trees, Searching, Inserting, and Deleting in Binary Search Trees, Efficiency of BST,
Binary Heaps, Heap creation and operations, Heap sort, AVL Tree, Creating AVL
Trees, Balancing AVL Tree by single or double rotations, Red-Black Trees, Decision
Trees,CPU burst (Exponential averaging)

Week 12 Minimum Spanning Trees:

Applications of Shortest path algorithms (Prim’s Algorithm, Dijkstra’s Algorithm)
Week 13 & 14 Graphs:
Basic Terminologies, Graph Theory, Directed, Undirected Graphs, Sequential
representation of graphs, Adjacency Matrix, Path Matrix, Graph algorithms, Link
List representation of graphs, Operations on Graphs, Graph Traversals (Depth-First
Traversal, Breadth First Traversal)

Week 15 Data Compression:

Encoding /Decoding, Huffman’s Algorithm, Revision

Week 16 Final Exam

WEEKLY LECTURE PLAN For Lab Practical

S.No Topics

Week1 An overview of Data Structures and their Operations: Brief Revision of Array

Implementation of Array operations

One Dimensional Array

Multidimensional Array

Abstract data types

Week 2 Algorithm Analysis:

Implementation of Pseudo coding, Control Structures

Programming examples for Analysis of Algorithms, Efficiency of Algorithms,

Complexity of Algorithms

Week 3 Pointers:

Implementation of Null pointer, Void Pointer, Invalid Pointer, Dangling Pointer

Reference Variable

Week 4 & 5 Sorting and Searching Techniques:

Implementation for elementary sorting algorithms such as Bubble Sort, Selection

Sort, Insertion Sort, Quick Sort, Merge Sort

Implementation of searching algorithms such as Linear Search and Binary Search

Week 6 Linked Lists:

Implementation of linked list with the help of algorithms for Insertion, Deletion and
Search an element

Implementation of Doubly Link List

Implementation of Circular Link List

Week 7 Stacks:

An array and link list based implementation of STACK

Week 8 Queues:

An array and link list based implementation of QUEUES

Week 9 Mid Term Exam

Week 10 & 11 Trees:

Implementation of Binary Trees, Array/Link List representation of binary trees in

memory

Tree Traversal (Binary Trees, Pre, In, and Post-order traversal)

Week 12 Binary Search Trees:

Implementation of Binary Search Trees

Searching, Inserting, and Deleting in Binary Search Trees, Binary Heaps, Heap
creation and operations

Week 13 & 14 Graphs:

Implementation of Directed, Undirected Graphs, Sequential representation of graphs,

Operations on Graphs

Graph Traversals (Depth-First Traversal, Breadth First Traversal)

Week 15 Revision

Week 16 Final Viva