Data Structures & Algorithms
Credit Hours: 3 Course Code: COSC-2101 Prerequisites: Object Oriented
Programming
Course Learning Outcomes (CLOs):
At the end of the course, the students will be able to: Domain BT Level*
1. Implement various data structures and their algorithms
C 3
and apply them in implementing simple applications
2. Apply the knowledge of data structure to other application
C 3
domains.
3. Analyze simple algorithms and determine their
C 5
complexities.
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
# SDG Relevant CLOs
CLO 2: Analyze simple algorithms and determine their
1 SDG 4: Quality Education
complexities.
CLO 3: Apply the knowledge of data structure to other application
SDG 9: Industry, domains.
2 Innovation and CLO 4: Design new data structures and algorithms to solve
Infrastructure problems.
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), stacks, expression parsing using stacks, queue,
dequeue, 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, expression trees, binary search trees, heaps, M-way tress, balanced trees
(AVL, Red Black), graphs, breadth-first and depth-first traversal, topological order, shortest path, adjacency
matrix and adjacency list implementations.
Teaching Methodology:
Lectures, Written Assignments, Practical labs, Semester Project, Presentations.
Course Assessment:
Mid Term Exams, Final Term Exams, Assignments, Quizzes, Project, Presentations, Practical Exam
Reference Material:
1. Data Structure 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
78
Data Structures & Algorithms - Lab
Credit Hours: 1 Course Code: COSC-3201 Prerequisites: None
Course Learning Outcomes (CLOs):
At the end of the course, the students will be able to: Domain BT Level*
1. Implement various data structures and their algorithms
C 1
and apply them in implementing simple applications
2. Apply the knowledge of data structure to other application
C 2
domains.
3. Analyze simple algorithms and determine their
C 3
complexities.
4. Design new data structures and algorithms to solve
C 3
problems.
*
BT= Bloom’s Taxonomy, C=Cognitive Domain, P=Psychomotor Domain, A=Affective Domain
# SDG Relevant CLOs
CLO 2: Analyze simple algorithms and determine their
1 SDG 4: Quality Education
complexities.
CLO 3: Apply the knowledge of data structure to other application
domains.
SDG 9: Industry, Innovation
2 CLO 4: Design new data structures and algorithms to solve
and Infrastructure
problems.
Course Contents:
Arrays, Functions and Pointers; Array implementation; Array and functions, Pointers. Complexity Analysis;
Asymptotic notations, Types of complexities (Best, Average, Worst cases), Big oh, Big omega, Big theta,
Complexity analysis of code snippets. Searching & Sorting in Arrays; Linear search, Binary search, Selection
sort, Insertion sort, Bubble sort, Quick sort, Merge sort, Comparison using asymptotic notations. Linked Lists,
Types of Linked Lists (Singly, Doubly, Circular), Algorithms (Searching, sorting, insertion, deletion), Stacks;
PUSH, POP, PEEK functions, Implementation using Arrays, Implementation using Linked Lists, Expression
parsing using Stacks (infix, prefix, postfix). Queues; Queue functions (Enqueue, Dequeue, search, Sort),
Implementation using Arrays, Implementation using Linked Lists, Implementation of different types of queues
(circular buffer, double ended, priority). Hashing. Recursion; Fibonacci series, Tower of Hanoi puzzle. Tree;
Tree traversals (inorder, preorder, postorder). Binary Search Trees; insertion of node, deletion of node,
traversals, searching a node, expression trees. Heap; Min heap, Max heap. Graphs; Searching in graph (BFS,
DFS), Topological order, shortest path first.
Teaching Methodology:
Lectures, Written Assignments, Practical labs, Semester Project, Presentations.
Course Assessment:
Mid Term Exams, Final Term Exams, Assignments, Quizzes, Project, Presentations, Practical Exam
Reference Material:
79
1. Data Communications and Networking by Behrouz A. Forouzan, McGraw-Hill Science, 4th or 5th
Edition.
2. Data and Computer Communications by William Stallings, Prentice Hall, 9th Edition, 2010;ISBN-10:
0131392050
3. Computer Networking: A Top-Down Approach, 7th edition, by James Kurose and Keith Ross (ISBN-13: 978-
0133594140)
80
