Data Structures and Algorithms — Complete Course Notes (BCA 3rd Sem)
Comprehensive lecture notes on asymptotic analysis, stacks, queues, linked lists, trees, graphs, and sorting algorithms for TU BCA.
Data Structures and Algorithms · CACS201 · Semester 3
Course Code: CACS201 | Tribhuvan University BCA 3rd Semester Curriculum.
1. Algorithm Analysis & Asymptotic Notations
The efficiency of an algorithm is measured in terms of Time Complexity (CPU execution time) and Space Complexity (memory storage consumed) as a function of input size n.
Asymptotic Notations:
- Big O (O): Upper bound. Represents worst-case running time: f(n) ≤ c · g(n) for all n ≥ n0.
- Big Omega (Ω): Lower bound. Represents best-case running time: f(n) ≥ c · g(n).
- Big Theta (\Theta): Tight bound. Represents average-case when upper and lower bounds coincide.
2. Linear Data Structures: Stack ADT
A stack is a Last-In, First-Out (LIFO) abstract data structure where insertions and deletions happen only at one end called the top.
Primary Operations:
push(item): Add an element to the top. Checks for Stack Overflow.pop(): Remove the element from the top. Checks for Stack Underflow.peek(): Inspect the current top element without removing it.
```c #define MAX 100 int stack[MAX]; int top = -1;
void push(int item) { if (top == MAX - 1) { printf("Stack Overflow!\n"); return; } stack[++top] = item; }
int pop() { if (top == -1) { printf("Stack Underflow!\n"); return -1; } return stack[top--]; } ```
3. Non-Linear Structures: Binary Search Tree (BST)
A Binary Search Tree is a binary tree where:
- For every node N, values in the left subtree are strictly less than N.key.
- Values in the right subtree are strictly greater than N.key.
- Inorder traversal of a BST always yields sorted keys!
```c struct Node { int key; struct Node left, right; };
struct Node* search(struct Node* root, int key) { if (root NULL || root->key key) return root; if (key < root->key) return search(root->left, key); return search(root->right, key); } ```
4. Sorting Algorithms Comparison
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) | Yes |
| Insertion Sort | O(n) | O(n2) | O(n2) | O(1) | Yes |
| Merge Sort | O(n \log n) | O(n \log n) | O(n \log n) | O(n) | Yes |
| Quick Sort | O(n \log n) | O(n \log n) | O(n2) | O(\log n) | No |
| Heap Sort | O(n \log n) | O(n \log n) | O(n \log n) | O(1) | No |
Data Structures and Algorithms Complete Course (freeCodeCamp)
Open lesson pageLesson videos
- What is the worst-case time complexity of Quick Sort algorithm? (a) O(n) (b) O(n log n) (c) O(n^2) (d) O(log n)objective · 1 marks
- Differentiate between Linear Queue and Circular Queue. Explain how modulo arithmetic prevents false overflow.short · 5 marks
Data Structures and Algorithms
Overview
Data Structures and Algorithms (CACS201) is a core credit course structured under the official university academic syllabus for Bachelor of Computer Application.
Objectives
- Equip students with deep theoretical foundations in Data Structures and Algorithms.
- Develop practical problem-solving, laboratory, and implementation skills.
- Prepare graduates for industry careers, research, and national university examinations.
Unit structure
- Unit 1: Introduction to Data Structures and Asymptotic Analysis6 hrs
By the end of Unit 1, students will be able to explain, implement, and solve problems related to Introduction to Data Structures and Asymptotic Analysis.
Unit 1:Comprehensive study notes, key principles, and examples for Introduction to Data Structures and Asymptotic Analysis. - Unit 2: Linear Data Structures: Stacks and Applications8 hrs
By the end of Unit 2, students will be able to explain, implement, and solve problems related to Linear Data Structures: Stacks and Applications.
Unit 2:Comprehensive study notes, key principles, and examples for Linear Data Structures: Stacks and Applications. - Unit 3: Linear Data Structures: Queues and Priority Queues7 hrs
By the end of Unit 3, students will be able to explain, implement, and solve problems related to Linear Data Structures: Queues and Priority Queues.
Unit 3:Comprehensive study notes, key principles, and examples for Linear Data Structures: Queues and Priority Queues. - Unit 4: Linked Lists: Singly, Doubly, and Circular8 hrs
By the end of Unit 4, students will be able to explain, implement, and solve problems related to Linked Lists: Singly, Doubly, and Circular.
Unit 4:Comprehensive study notes, key principles, and examples for Linked Lists: Singly, Doubly, and Circular. - Unit 5: Non-linear Data Structures: Trees and Binary Search Trees9 hrs
By the end of Unit 5, students will be able to explain, implement, and solve problems related to Non-linear Data Structures: Trees and Binary Search Trees.
Unit 5:Comprehensive study notes, key principles, and examples for Non-linear Data Structures: Trees and Binary Search Trees. - Unit 6: Graphs and Minimum Spanning Trees9 hrs
By the end of Unit 6, students will be able to explain, implement, and solve problems related to Graphs and Minimum Spanning Trees.
Unit 6:Comprehensive study notes, key principles, and examples for Graphs and Minimum Spanning Trees. - Unit 7: Sorting and Searching Algorithms8 hrs
By the end of Unit 7, students will be able to explain, implement, and solve problems related to Sorting and Searching Algorithms.
Unit 7:Comprehensive study notes, key principles, and examples for Sorting and Searching Algorithms.
Learning outcomes
- Demonstrate rigorous technical knowledge and conceptual mastery of Data Structures and Algorithms.
- Design, implement, and analyze efficient algorithms and practical frameworks.
- Solve representative theoretical proofs and complex applied problems independently.
Teaching & evaluation
Classroom lectures (3 hours/week), practical laboratory assignments (3 hours/week), and project work.
Internal Assessment (40 Marks: Theory Exam, Practical Exam, Attendance, Assignments) and Final University Board Examination (60 Marks).
Reference books
- Data Structures Using C and C++ by Langsam, Augenstein & Tenenbaum
- Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (CLRS)
Related video lessons
Practice questions
- What is the worst-case time complexity of Quick Sort algorithm? (a) O(n) (b) O(n log n) (c) O(n^2) (d) O(log n)objective · 1 marks
- Differentiate between Linear Queue and Circular Queue. Explain how modulo arithmetic prevents false overflow.short · 5 marks