| Course Code |
CSC331 |
| Course Title |
Data Structure and Algorithms |
| Credit Hours |
3+1 |
| Prerequisites by Course(s) and Topics |
Programming Fundamentals |
| 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 |
Muhammad Ali Dildar |
| URL (if any) |
|
| Current Catalog Description |
|
| Textbook (or Laboratory Manual for Laboratory Courses) |
Data Structures and Algorithms in C++ by Adam Drozdek |
| Reference Material |
1. Data Structures and Algorithms in C++ by Adam Drozdek 2. Data Structures and Abstractions with Java by Frank M. Carrano & Timothy M. Henry 3. Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss 4. Java Software Structures: Designing and Using Data Structures by John Lewis and Joseph Chase |
| 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* |
|---|
| Implement various data structures and their algorithms, and apply them in implementing simple applications. |
C |
2,3 |
| Analyze simple algorithms and determine their complexities. |
C |
4,5 |
| Apply the knowledge of data structures to other application domains. |
C |
3 |
| Design new data structures and algorithms to solve problems. |
C |
6 |
| * 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, Abstract Data Types (ADT). Linear vs Non-Linear Data Structures. |
|
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 |
Infix, Prefix, Postfix notation, Conversions. Postfix Expression Evaluation. |
|
6 |
Queue , Dequeue & its implementation using arrays |
| Week 4 |
7 |
Priority queues, Circular queues using arrays |
|
8 |
Recursion and analyzing recursive algorithms |
| Week 5 |
9 |
Sorting algorithms (Selection sort ) |
|
10 |
Insertion sort , Bubble Sort |
| Week 6 |
11 |
Intro. & Implementation of List as Singly Link List |
|
12 |
Intro. & Implementation of List as Singly Link List( Insertion and deletion function) |
| Week 7 |
13 |
Intro. & Implementation of List as Singly Link List( Search and Sorting function) |
|
14 |
Solving stack problems using Link List |
| Week 8 |
1 hours |
Mid Term |
| Week 9 |
15 |
Intro. & Applications of Doubly Link List |
|
16 |
Queue / Stack Operations implementation using DLL |
| Week 10 |
17 |
Intro. & Applications of Circular Link List |
|
18 |
Queue / Stack Operations implementation using CLL |
| Week 11 |
19 |
Introduction and Applications of Doubly Linked List |
|
20 |
Implementation of Doubly Linked List |
| Week 12 |
21 |
Implementation of Doubly Linked Lisr |
|
22 |
Queue/Stack operations using DLL |
| Week 13 |
23 |
Introduction and Applications of Circular Linked List |
|
24 |
Implementation of Circular Linked List |
| Week 14 |
25 |
Divide and Conquer Algo |
|
26 |
Binary Trees and its types & implementation of BST |
| Week 15 |
27 |
Tree Traversal |
|
28 |
AVL trees and their operations |
| Week 16 |
29 |
Heap and its types |
|
30 |
Balanced BST |
| Week 17 |
2 hours |
Final Term |
|
| Laboratory Projects/Experiments Done in the Course |
Student oriented Project |
| Programming Assignments Done in the Course |
4 Assignments |
