CS21003: Algorithms - I

From Metakgp Wiki
Jump to navigation Jump to search
CS21003
Course name Algorithms - I
Offered by Computer Science & Engineering
Credits 4
L-T-P 3-1-0
Previous Year Grade Distribution
32
58
68
39
23
5
5
EX A B C D P F
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