| 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 |
Eisha Tir Razia |
| URL (if any) |
|
| Current Catalog Description |
|
| Textbook (or Laboratory Manual for Laboratory Courses) |
Data Structures and Algorithm Analysis by Mark A. Weiss |
| 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 |
|
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 |
Mid Term Examination |
|
16 |
Mid Term Examination |
| Week 10 |
17 |
Intro. & Applications of Doubly Link List (DLL) |
|
18 |
Implementation of Doubly Linked List |
| Week 11 |
19 |
Implementation of Doubly Linked List |
|
20 |
Queue / Stack Operations implementation using DLL |
| Week 12 |
21 |
Intro. & Applications of Circular Link List (CLL) |
|
22 |
Queue / Stack Operations implementation using CLL |
| Week 13 |
23 |
Divide and conquer algorithms |
|
24 |
Binary Tree, Strictly Binary Tree, Complete Binary Tree, Implementation of BST |
| Week 14 |
25 |
Tree Traversal: Three Tick method |
|
26 |
AVL Trees, Operations on AVL Tree |
| Week 15 |
27 |
Heaps, Min Heaps, Max Heaps |
|
28 |
Min Balanced BST, Max Balanced BST |
| Week 16 |
29 |
Graphs, Types of Graphs |
|
30 |
Adjacency matrix and adjacency list implementations, Graph Traversal Techniques |
| Week 17 |
2 hours |
Final Term |
|
| Laboratory Projects/Experiments Done in the Course |
Yes |
| Programming Assignments Done in the Course |
Yes |
