| Course Code |
CSC331 |
| Course Title |
Data Structure and Algorithms |
| Credit Hours |
3+1 |
| Prerequisites by Course(s) and Topics |
Object Oriented Programming |
| Assessment Instruments with Weights (homework, quizzes, midterms, final, programming assignments, lab work, etc.) |
SESSIONAL (Quizzes, Assignments, Presentations) =25 %
Midterm Exam =25 %
Final Exam = 50%
|
| Course Coordinator |
MS. Rabia Khan |
| URL (if any) |
|
| Current Catalog Description |
|
| Textbook (or Laboratory Manual for Laboratory Courses) |
The aim of this course is to cover basic and in-depth concepts of Data Structures and Algorithms. Students will learn how data structures are helpful to solve different problems. It will provide foundation in learning advanced algorithm analysis course. Student can use C++ language for the purpose of implementation, and they will learn generic concepts which will be used for developing different software applications. The knowledge of C++ languages is expected as strong background |
| Reference Material |
Nell Dale: C++ Plus Data Structures, Latest Edition, Jones & Bartlett Data Structure using C/C++ by Mark Alan. Yadidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum: Data Structures using C and C++. Dr. Sohail Aslam: Data Structures Handouts. Graph Theory & Algorithms by Dr. M. Ashraf Iqbal |
| Course Goals |
Basic and in-depth concepts of Data Structures and Algorithms to solve different software problems. Selection of appropriate Data Structure and Algorithm for specified application. How appropriate Data Structures and algorithms impact performance of software? Solve different problems using Arrays, Stacks, Queues, Link Lists, Trees, Heaps, Hash Tables and Graphs. Use of different sorting techniques and their efficiency. Students will be able to translate Algorithm ideas into working practical applications. |
| Course Learning Outcomes (CLOs): |
| At the end of the course the students will be able to: | Domain | BT Level* |
|---|
| Demonstrate knowledge about the practical aspects of data structures & algorithms Lab Course. |
C |
3 |
| Adapt the ability for developing Data structures & Algorithms based solutions that meet specified needs for an engineering problem at hand. |
P |
3 |
| Work effectively as an individual or in team to solve real world problems. |
A |
3 |
| * BT= Bloom’s Taxonomy, C=Cognitive domain, P=Psychomotor domain, A= Affective domain |
|
|
|
| Topics Covered in the Course, with Number of Lectures on Each Topic (assume 15-week instruction and one-hour lectures) |
| Week | Lecture | Topics Covered |
|---|
| Week 1 |
1 |
Course Overview, Introduction to Different Data Structures. Data Types, Primitive Data types, Non – Primitive Data Types |
|
2 |
Abstract data types, (ADT’s), Data Structures, Lists, ADT List Operations |
| Week 2 |
3 |
Complexity Analysis & Big Oh Notation |
|
4 |
ADT Stacks, ADT Stack Operations, and implementation |
| Week 3 |
5 |
Implementation of stack using STL library (Push, Pop, Swap) |
|
6 |
Infix, Prefix, Postfix notation, Conversions. Postfix Expression Evaluation. |
| Week 4 |
7 |
Implementation of Selection sort, Bubble Sort |
|
8 |
Implementation of Insertion Sort |
| Week 5 |
9 |
Implementation of List as Singly Link List |
|
10 |
Implementation of List as Singly Link List( Insertion at the start, Insertion at the end and Insertion at a specific position) |
| Week 6 |
11 |
Implementation of List as Singly Link List( Deletion Searching and Display operations) |
|
12 |
Implementation of Doubly Linked List( Insertion and Deletion Operations) |
| Week 7 |
13 |
Implementation of Doubly Linked List( Searching and Display Operations) |
|
14 |
Stack Operations implementation using Circular Linked List |
| Week 8 |
1 hours |
Mid Term |
| Week 9 |
15 |
Stack Operations implementation using Doubly Circular Linked List |
|
16 |
Stack Operations implementation using Doubly Circular Linked List |
| Week 10 |
17 |
Queue , Dequeue & its implementation using arrays |
|
18 |
Priority queues, Circular queues using arrays |
| Week 11 |
19 |
Divide and conquer algorithms |
|
20 |
Binary Tree, Strictly Binary Tree, Complete Binary Tree |
| Week 12 |
21 |
Divide and conquer algorithms |
|
22 |
Binary Tree, Strictly Binary Tree, Complete Binary Tree |
| Week 13 |
23 |
Implementation of BST |
|
24 |
Tree Traversal: Three Tick method |
| Week 14 |
25 |
AVL Trees, Operations on AVL Tree |
|
26 |
Heaps, Min Heaps, Max Heaps |
| Week 15 |
27 |
Implementation of Heap sort |
|
28 |
Min Balanced BST, Max Balanced BST |
| Week 16 |
29 |
Graphs, Types of Graphs |
|
30 |
Adjacency matrix and adjacency list implementations |
| Week 17 |
2 hours |
Final Term |
|
| Laboratory Projects/Experiments Done in the Course |
|
| Programming Assignments Done in the Course |
|
