Course Information

Lectures (L7): Mon-11:00 AM, Tue-12:00 PM, Wed 9:00 AM
Labs: TBA PM

Contents

Introduction to arrays, stacks, linked lists, queues, heaps. Tools and techniques required to analyse various algorithms and data structures, asymptotic notations, asymptotic behaviour of time/space complexity, master theorem, amortised analysis. Search trees: AVL Trees, multi-way trees, red-black trees, splay trees. Lower bound on sorting, quick sort, linear time sorting, Medians and order statistics. Dictionaries, tries, hashing, hash functions, chaining, and expected time analysis, analysis of collision resolution techniques, skip lists. Definition of graphs, paths, trees, cycles. Data structures for graphs: adjacency lists, adjacency matrix. Depth first search, breadth first search and their applications. Union-find data structure and applications. Minimum spanning tree, shortest path algorithms, topological sort, transitive closure.

Outcomes

By taking this course, the students will be able to find answer to the following questions:

What are data structures and where do we use them?

What are the standard algorithms that use these data structures?

How to choose/design data structure for a given problem?

Prerequisite

GE103: Introduction to Computing and Data Structures

Course Requirements

Student are required to attend three lectures per week lectures and appear in two exams. In addition, there will be weekly lab sessions. During lab sessions, the students are required to solve and implement programming assignments.

Grading Policy

There will be approximately 6-7 lab exercises and home assignments, 6-7 quizzes, a mid-semester exam and a final exam. The tentative grade distribution is as follows:

Quizzes (top n-1): 30%
Lab exercises and Assignments: 20%
Mid-semester exam: 25%
Final exam: 25%
A student must score at least 40% marks to pass the course.

Attendance Requirement

There is no attendence requirement; however, students with less than 75% attendance will not get any support from me outside the scope of this course. During lectures :

BE SHARP ON TIME

STAY THROUGH THE LECTURE (DON'T LEAVE IN-BETWEEN THE LECTURE)

It is advised to not indulge in any activity during the lecture that might disturb other students or the instructor.

Code of Ethics & Professional Responsibility

It is expected that students who are taking this course will demonstrate a keen interest in learning and not mere fulfilling the requirement towards their degree. Discussions that help the student understand a concept or a problem is encouraged. However, each student must turn in original work. Plagiarism/copying of any form, will be dealt with strict disciplinary action. This involves, copying from the internet, textbooks and any other material for which you do not own the copyright. Copying part of the code will be considered plagiarism. Lending the code to others will be considered plagiarism too, for it is difficult to investigate who copied whose code. Students who violate this policy will directly receive a failing grade in the course. Remember - Your partial submission can fetch you some points, but submitting other's work as your own can result in you failing the course. Please talk to the instructor if you have questions about this policy. All academic integrity issues will be handled in accordance with institute regulations.

Textbooks

Primary Textbook

Data Structures and Algorithms in C++, 2nd Edition by Michael T. Goodrich, Roberto Tamassia, David M. Mount, 2011 [Link]

Reference Books

1. Introduction to algorithms: Cormen, Thomas H. MIT press, 2009. [Link].
2. Fundamentals of Data Structures in C++: Ellis Horowitz, Sartaj Sahni, Dinesh P. Mehta. Silicon press, 2008. [Link].
3. Algorithms in C++ : Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 (English) 3rd Edition: Robert Sedgewick, 1998. [Link].

Language/Tools

C++

Teaching Assistant

Priyankar

Contact Me

By appointment

Lectures and Calendar