| 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 |
Sahar Moin |
| URL (if any) |
|
| Current Catalog Description |
|
| Textbook (or Laboratory Manual for Laboratory Courses) |
|
| 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* |
|---|
| Identify various data structures and their algorithms |
C |
3 |
| Analyze time and space complexities of data structures and algorithms |
C |
4 |
| Select appropriate algorithms to use in specific applications. |
C |
3,4 |
| Compare tradeoffs in the design and implementations of the data |
C |
4 |
| * 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 |
Stacks: Functions and stl |
| Week 3 |
5 |
Infix, Prefix, Postfix notation, Conversions. Postfix Expression Evaluation |
|
6 |
Recursion and analyzing recursive algorithms |
| Week 4 |
7 |
Sorting algorithms(Selection sort, bubble sort ) |
|
8 |
Insertion sort , Quick sort |
| Week 5 |
9 |
Intro. & Implementation of List as Singly Link List |
|
10 |
Intro. & Implementation of List as Singly Link List( Insertion and deletion function) |
| Week 6 |
11 |
Solving stack problems using Link List Implementation of Queue as Singly Link List |
|
12 |
Intro. & Applications of Doubly Link List (DLL) |
| Week 7 |
13 |
Queue / Stack Operations implementation using DLL |
|
14 |
Intro. & Applications of Circular Link List (CLL) Queue / Stack Operations implementation using CLL |
| Week 8 |
1 hours |
Mid Term |
| Week 9 |
15 |
Queue , Dequeue & its implementation using arrays |
|
16 |
Priority queues, Circular queues using arrays |
| Week 10 |
17 |
Divide and conquer algorithms |
|
18 |
Binary Tree, Strictly Binary Tree, Complete Binary Tree |
| Week 11 |
19 |
Divide and conquer algorithms, |
|
20 |
Binary Tree, Strictly Binary Tree, Complete Binary Tree |
| Week 12 |
21 |
Implementation of BST |
|
22 |
Tree Traversal: Three Tick method |
| Week 13 |
23 |
AVL Trees, Operations on AVL Tree |
|
24 |
Heaps, Min Heaps, Max Heaps |
| Week 14 |
25 |
Implementation of Heap sort |
|
26 |
Min Balanced BST, Max Balanced BST |
| Week 15 |
27 |
Graphs, Types of Graphs |
|
28 |
Adjacency matrix and adjacency list implementations |
| Week 16 |
29 |
Hashing. Hashing Techniques, Collisions & Collisions Avoidance Methods |
|
30 |
Memory management and garbage collection |
| Week 17 |
2 hours |
Final Term |
|
| Laboratory Projects/Experiments Done in the Course |
yes |
| Programming Assignments Done in the Course |
yes |
