ALGORITHMS AND TIME COMPLEXITY
Credits: 3.0 units
Time Allotment: 8.00 hours lecture every week
By the end of the class students should be able to:
| Topic | Mode of Delivery | Readings/Videos | Events | |
|---|---|---|---|---|
| Week 1 | Class Orientation | |||
| ➢ University Mission & Vision | ||||
| ➢ College Mission & Vision | ||||
| ➢ Course Syllabi | ||||
| ➢ Lab Guidelines and Safety |
Introduction to Analysis of Algorithms ➢ Definition, Applications, Usage
| Lecture Discussion | | | | Week 2 | Introduction to Graph Theory ➢ Definition and Concepts ➢ Graphs as Data Structures ➢ Application in Real World ➢ Problems in GT | Lecture Discussion | | | | Week 3 | Introduction to Proofs ➢ Direct Proof ➢ Proof of Induction ➢ Proof of Contradiction ➢ Proof of Contrapositive | Lecture Discussion | | | | Week 4 | Introduction to Analysis of Algorithms ➢ Concept and description ➢ Time Complexity and Space Complexity
Asymptotic Notations ➢ Big-O, Big Omega, Big Theta ➢ Applications of Analysis | Lecture Discussion | | | | Week 5 | Search Algorithms ➢ Linear Search ➢ Binary Search ➢ Jump Search ➢ Analysis of Search Algorithms | Lecture Discussion Simulation | | | | Week 6 | Sorting Algorithms ➢ Bubble Sort ➢ Selection Sort ➢ Insertion Sort ➢ Quick Sort | Lecture Discussion Simulation | | | | Week 7 | Sorting Algorithms ➢ Merge Sort ➢ Heap Sort
Introduction to Recursions and Recurrence Relations ➢ Analysis of Recursive Algorithms | Lecture Discussion Simulation | | | | Week 8-9 | Recurrence Relations ➢ Concept and description ➢ Solving recurrence relations of recursive sorting algorithms ➢ Solving recursive problems using recurrence relations | Lecture Discussion | | | | Week 10 | Greedy Algorithms ➢ Concept, description, and heuristics ➢ Problems solved by greedy algorithms ➢ Applications | Lecture Discussion Simulation | | | | Week 11 | Dynamic Programming ➢ Concept, description, and heuristics ➢ Problems solved by DP ➢ Applications | Lecture Discussion Simulation | | | | Week 12 | P and NP Classes ➢ Concepts and properties of P, NP classes ➢ Equivalence of definition ➢ P vs NP problem ➢ Applications | Lecture Discussion | | | | Week 13-13.5 | | | | |