Course Information

Lectures (L5): Wed-4:45 PM, Thu-2:00 PM, Fri 2:55 PM
Labs (Computer Lab 2): Fri 9:00 AM - 12:35 PM

Objectives

Revision of notions of time and space complexity, and trade-offs in the design of data structures. Introduction to object-oriented programming through stacks, queues and linked lists. Dictionaries; skip-lists, hashing, analysis of collision resolution techniques. Trees, traversals, binary search trees. Balanced BSTs, tries, priority queues and binary heaps. Object oriented implementation and building libraries. Applications to discrete event simulation. Sorting: merge, quick, radix, selection and heap sort, Graphs: Breadth first search and connected components. Depth first search in directed and undirected graphs. Union-find data structure and applications. Directed acyclic graphs; topological sort.

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

GEL103: Introduction to Computing

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, 3-4 home assignments, 6-7 quizzes, a mid-semester exam and a final exam. The tentative grade distribution is as follows:

Quizzes (top n-1): 20%
Lab exercises (top n-1): 15%
Assignments: 15%
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 more than 75% attendance would get a bonus mark. 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

Amit Kumar Verma (Email: 2016csz0003@iitrpr.ac.in)
Rohit Chaudhary (Email: 2017csm1011@iitrpr.ac.in)
Pratibha Kumari (Email: 2017csz0006@iitrpr.ac.in)

Contact Me

By appointment at
Room No. 358, Academic Building, IIT Ropar

Feedback Form

Lectures and Calendar

 

Tentative Schedule and List of Topics*

*This is a tentative list of topics that will be covered during the semester. The topics and schedule can change according to the need at the discretion of the instructor.