CS21003: Algorithms - I
| CS21003 | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Algorithms - I | ||||||||||||||||||||||||||||
| Offered by | Computer Science & Engineering | ||||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||||
| L-T-P | 3-1-0 | ||||||||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
| Semester | Autumn | ||||||||||||||||||||||||||||
Syllabus mentioned in ERP
Asymptotic notations and their significance, introduction to RAM model of computation, complexity analysis of algorithms, worst case and average case. Basic introduction to algorithmic paradigms like divide and conquer, recursion, greedy, etc. Searching: binary search trees, balanced binary search trees, AVL trees and Red-black trees, B-trees, skip lists, hashing. Priority queues, heaps, Interval trees, tries. Order statistics. Sorting: Comparison based sorting --quick sort, heap sort, merge sort: worst and average case analysis. Decision tree model and (worst case) lower bound on sorting. Sorting in linear time -- radix sort, bucket sort, counting sort, etc. String matching Graph Algorithms: BFS, DFS, connected components, topological sort, minimum spanning trees, shortest paths -- single source and all pairs.
How to Crack the Paper
The course aims to develop the skill of a student to design efficient algorithms. So, a lot of practice will be needed. Apart from Cormen's book on algorithms, solve easy and medium level questions from geeks for geeks of the relevant topics. Also, make sure that you have solved the tutorials multiple times before the exams.
The paper pattern generally (for the one offered in Autumn semester) has an equal weightage of easy, medium and difficult questions. The easy questions may be like asking definitions or to show the running of the basic algorithms taught in class (like insertion in RB-Tree or the Dynamic Programming approach for Matrix Chain Multiplication). The other two types mainly asks for designing algorithms, some may ask to write pseudo code as well.
To perform well make sure that one is able to solve the easy questions in the least time possible.
Additional Resources
Apart from the classroom notes provided by the respective professors, the student can go through these reference books:
- Introduction to Algorithms 3rd-edition 2010 PDF [1]
- Algorithm Design [2]
Time Table
| Day | 8:00-8:55 am | 9:00-9:55 am | 10:00-10:55 am | 11:00-11:55 am | 12:00-12:55 pm | 2:00-2:55 pm | 3:00-3:55 pm | 4:00-4:55 pm | 5:00-5:55 pm | |
|---|---|---|---|---|---|---|---|---|---|---|
| Monday | ||||||||||
| Tuesday | ||||||||||
| Wednesday | NC442/443 | |||||||||
| Thursday | NC442/443 | |||||||||
| Friday | NC442/443 | NC442/443 |