• HOME
• ACTIVITIES
• OLYMPIAD
• MEMBERS
• ABOUT

Related:

• Overview
• Conferences
• Courses
• Grants
• Notes

Instructional Course at Tirupattur, 11-12 Dec 2003

IARCS home > ACTIVITIES > Courses

• Location and participants
• Course outline
• Lecture notes and problem sheets
• Feedback

Location and participants

A mini course on Algorithms and Data Structures was held at Sacred Hearts College, Tirupattur, Tamil Nadu, during December 11-12, 2003. Tirupattur is a small town about 8 kms from Jolarpettai which is a major junction in the Chennai-Bangalore route, at about three hours train journey from Chennai.

The course was handled by Dr. C. R. Subramanian and Dr. Venkatesh Raman both from the Institute of Mathematical Sciences, Chennai.

The participants of the course were mostly the third year MCA students and some teachers of the computer science department of the college.

Course outline and material

• Introduction to algorithms, data structures and analysis - Venkatesh Raman
  
  • Sorting - Insertion Sort, Selection Sort, their analysis, Big Oh notation, Searching - Binary search.
  • Merging, Mergesort; more on divide and conquer by the example of Karatsuba and Offman's algorithm for integer multiplication.
  • Introduction to Data structures - arrays, linked lists and trees, Graphs and their representations, Dijkstra's algorithm for shortest path and the abstract data structure problem required for implementation; various structures to represent a sequence of numbers and to support insert and deletemin with worst case complexity of O(n).
  • Heaps and operations on heaps; application of heaps to priority queue implementation, Dijkstra's algorithm and to sorting.
  • Search data structure - Binary search trees, and the need for balancing. Typical properties of balanced binary search trees.
  • Polynomial versus exponential algorithms and the drawback of exponential algorithms.
• Hard and Easy Problems and Coping Strategies -- C. R. Subramanian
  • Optimization versus decision problems, informal introduction to P, NP classes, polynomial time reduction and NP-complete languages, their motivations, some examples.
  • Introduction to approximate algorithms, fixed parameter tractable algorithms, average case analysis (designing efficient algorithms for random instances) using examples.
• Dynamic Programming technique - C. R. Subramanian
  • Examples including fibonacci numbers, some variant of shortest paths.

Lecture notes and problem sheets

Some introductory notes on algorithms and problem sheets were distributed to the participants the course are available online.

• Lecture notes (Postscript, PDF).
• Problem sheets (Postscript, PDF).

Feedback

• From participants

  • `We learnt how to solve problems in general'
  • `We have done this course before without understanding much, and now we learnt how much is there to learn in data structures and algorithms'
  • `now we have a much better idea for the motivation for AVL trees and what NP-completeness means'

  These were some of the statements made by the students during the feedback session and also during various individual informal meetings. Some of them were motivated enough to attempt on the problems in the problem sheet given and ask questions during breaks.

• From the teachers/organizers

  Despite their busy schedule due to classes and valuations, some teachers attended some sessions and they were quite happy. They would like to organize a (long one - for about a week) course like this exclusively for teachers including teachers from nearby colleges sometime in April.

• From the resource persons

  This course was basically organized by the placement division of the college for the third year MCA students who have already done a course on algorithms and were all ready to leave for the project semester in a couple of days. Defintely the students got something out of the course. Some of them were quite impressive in their answers during the course.

  The impact of the course will be more if there is such a course for them early on (say at the beginning of their second year) when they do this course as a part of their curriculum. It will be much more if it is organized at a time convenient for most of their teachers to attend.

• Arrangements

  The college had excellent class rooms and simple and clean guest house rooms where we were housed.

  Overall hospitality (under the guidance of Prof John Arockiaraj) was great. We were pampered from the time we arrived at the railway station till we were dropped at the station (we even had room service for breakfast). We only wish that that we had more time to talk to the students informally.