Algorithms

Programme Overview

Learn how to structure and use algorithms to solve real life problems. Algorithms power the biggest web companies and the most promising startups. Interviews at tech companies start with questions that probe for good algorithm thinking.

In this computer science course, you will learn how to think about algorithms and create them using sorting techniques such as quick sort and merge sort, and searching algorithms, median finding, and order statistics.

The course progresses with Numerical, String, and Geometric algorithms like Polynomial Multiplication, Matrix Operations, GCD, Pattern Matching, Subsequences, Sweep, and Convex Hull. It concludes with graph algorithms like shortest path and spanning tree.

Course content

The topics covered in this course:

• Sorting and Searching

• Numerical Algorithms

• String Algorithms

• Geometric Algorithms

• Graph Algorithms

The detailed description is given below:

Topic 1: Complexity

• Learn to analyse algorithm based on its running time

• Empirical Analyses of Running Time

• Differentiating between Average and Worst Case Analysis

• Learn about Asymptotic Analysis

• Understanding the concept of Big-Oh

Topic 2: Sorting

• Learn about Comparison based Sorting

• Learn about Selection, Insertion and Heap Sort of Abstract Data types for Sorting

• Learn about Min-Heap Based Sort and its Array Representation

• Know about Divide and Conquer Approach to Sorting and Merge-Sort Execution Tree

• Learn about Quick-Sort Execution Tree and Worst case Running time of Quick-Sort

Topic 3: Searching (Graph Based)

• Introduction to Graph Traversal Algorithm – (BFS) – Its properties, analysis, and application.

• Introduction to Graph Traversal Algorithm – (DFS) - Its properties, analysis, and application.

• Know about Shortest Path in Weighted Graphs and Dijkstra’s Algorithm

• Know about Shortest Path Algorithms – Bellman-Ford Algorithm

• Introduction to All Pair Shortest Path Algorithm – Floyd-Warshal Algorithm and its examples

Topic 4: Spanning Trees and Numeric Algorithms

• Using Prim’s Algorithm for finding a spanning tree for a graph

• Introduction to Kruskal’s Algorithm and its analysis

• Analysis of Prim’s Algorithm and Kruskal’s Algorithm

• Learn about Bisection Method and its Advantages and Disadvantages

• Introduction and Principles of Newton-Raphson Method

Topic 5: String Algorithms

• Introduction to String Matching Algorithm

• Learn about Naive String Matching Algorithm and its Analysis

• Introduction to Rabin-Karp Algorithm and its Analysis

• Introduction to Finite Automaton Algorithm

• Introduction to Knuth-Morris-Pratt Algorithm and its Analysis

Topic 6: Geometric Algorithms

• Learn about different Computational Geometry Algorithms

• Learn about properties of Line Segment

• Introduction to Convex Hull and its illustrations

Teaching Faculty

Prof. Deepak B Phatak, Professor Emeritus, Dept. of CSE, IIT Bombay

Prof Ajit Diwan, Dept. of CSE, IIT Bombay

Prof Ganesh Ramakrishnan, Dept. of CSE, IIT Bombay

Mr. Nagesh Karmali, Sr. Manager (Research), Dept. of CSE, IIT Bombay

Duration and Venue

This course will be conducted in a self-paced mode, i.e. all the lecture videos, slides, reading materials, activities, and graded assignments will be released on when the course starts. This gives you the flexibility of progressing and completing the graded assignments at your own pace. However, but one would need to complete them before the course ends.

Who Should Attend

Concepts of data structures as covered in ‘Foundations of Data Structures’ and ‘Implementation of Data Structures’ courses are prerequisites of this course.

Course Fee and Certification

The registration fee for the course is Rs. 570/-. However, register before 30 July 2021 for Rs. 470/- only to avail an early bird registration discount.

Important Payment Instruction:

Please note that the registration fee once paid is neither refundable nor adjustable under any circumstances.
While making a payment for the course,
(i) If you receive a transaction failure message and your amount is NOT debited, please pay again by logging in to IITBombayX-LAKSHYA programme(https://www.it.iitb.ac.in/lakshya) website.

(ii) If your amount is debited and you still receive a transaction failure message, please DO NOT make another payment. Send a mail to workshopfund@cse.iitb.ac.in with cc to Eoutreach eoutreach@it.iitb.ac.in with a subject "Transaction failure but amount debited". Also, provide the transaction details in the mail. You will soon receive a reply from us on the same.

Honor Code e-Certificates will be issued on successful completion of the course based on the grading policy mentioned in the course. Please note that all e-certificates will be issued online after the course ends on 21 November 2021. No hard copies will be given.

How to Apply

Enrollment will be strictly online, and no other mode of application will be entertained. The online registration is available from 28 June 2020 till 15 August 2021.

Course registration steps for the IITBombayX-Lakshya portal: 

• Once you select the course of your interest from the homepage. A page will open where Click on the link “Click here for registration form” to get enrolled for this course.
• You will be prompted to enter your email address.
1. If you have already registered in our earlier courses: Use your existing email id and password to get enrolled.
2. If you are here for the first time: A form will open where you have to enter the OTP (received in the entered email), password and other required details and press SUBMIT button (for your account creation).
• You will be routed to Registration form of this course and select your appropriate ‘Audience type’, (if not selected earlier) and Press on ‘Pay Now’ button.
• Once the payment is successful , you will receive an automated email. Also, your name will be listed in the ‘List of Participants’ page in Course page.
• Register on IITBombayX site (https://courses.iitbombayx.in/register) using the same email id to access the course content (if already registered in IITBombayX site with same email, then you may skip this step).
• You will be mapped in IITBombayX of this course within 2 to 3 working days.
• You will be able to access the course in your IITBombayX dashboard after login.

Accommodation

Note

The course content is released under Open Source License. All participants must agree that the content contributed by them in any form, (assignments, questions, etc.) would be released under Open Source Licence, by accepting the terms mentioned under ‘No Objection Certificate’. All contributors will be acknowledged.

Address For Communication

Dr. Kalpana Kannan
Project Coordinator, ESOS Project
Department of CSE, Kanwal Rekhi Building,
Indian Institute of Technology Bombay,
Mumbai - 400 076.
Tel.: +91 9833594905 (Mahendra)
Email: eoutreach@it.iitb.ac.in
Website - www.it.iitb.ac.in/lakshya/ www.iitbombayx.in