A Short Term Course on "Fundamental Algorithms: Design and Analysis"

09 - 13 February 2017

Venue:

B R Seth Seminar Room,

Department of Mathematics,

IIT Kharagpur

organizes a short term course entitled "Fundamental Algorithms: Design and Analysis" from 09 - 13 February 2017.

Overview:

This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems. The course emphasizes the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems.

Content:

1.     Introduction: Analysis of Algorithms, Insertion Sort, Merge Sort, Asymptotic Notation.

2.     Recurrences: Substitution, Iteration, Master Method.

3.     Divide and Conquer: Strassen's Algorithm, Fibonacci Numbers, Quicksort, Randomized Algorithms.

4.     Divide and Conquer Techniques in Geometry

5.     Heap, Heapsort.

6.     BST sort, Relationship of BST sort with Quicksort, Analysis of Random BST.

7.     Decision Tree, Linear-time Sorting, Lower Bounds, Counting Sort, Radix Sort.

8.     Computational Geometry: 1D Range Tree, 2D Range Tree, Line-Segment Intersection

9.     Fixed-Universe Successor problem : Van Emde Boas data structure

10.  Median, Order Statistics.

11.  Hashing, Hash Functions

12.  Red-black Trees, Rotations, Insertions, Deletions

13.  Augmenting Data Structures, Dynamic Order Statistics, Interval Trees.

14.  Dynamic Programming.

15.  Greedy Algorithms, Graphs, Minimum Spanning Trees, Breadth First Search (BFS), Depth-First Search (DFS)

16.  Shortest Paths

17.  Combinatorial Techniques in Geometry

18.  NP-Completeness

19.  Approximation Algorithms

Features:

 Participants of the program are faculty members, students, working professionals from different institutions, research & development organizations and industries. The participants can attend the course at IIT Kharagpur. The course is FREE for participants from TEQIP II (List can be found here) institutions, whereas there is a course fee for other participants. However, priority will be given to faculty members of TEQIP II institutions.

 Instructions/Information: 1.     All participants from TEQIP II (List can be found here) Institutions must submit the certificate from the college authority, in which it must be mention that, your college is TEQIP II college. 2.     As there are only a few seats available, early-bird registrants will be given preference. However, there will be a rigorous selection procedure for the course. 3.     All participants (excluding TEQIP II institution) will be responsible for all expenses, including accommodation, travel, and food. However, on the immediate request from the participants, the accomodation can be tried to be arranged (on self-payment-basis in some hostels/guestrooms) inside the IIT campus, based on avalability. Best possible available arrangements will be attmpted to be made. However, the course coordinator will not be responsible to meet the quality expectations of the participants in all academic and non-academic aspects. 4.     On successful completion of the course, certificate of participation will be issued to all the candidates by the Continuing Education office of IIT Kharagpur, on the recommendation from the Coordinator. 5.     Attendance of each of the candidates will be taken regularly. 6.     All the selected participants must bring the required original testimonials during the course. 7.     Please note that, the last date of registration is February 03, 2017. 8.       The list of TEQIP II institutions can be found