CS201: Data Structures
Semester 1, 2018-19

 

Course Information Lectures/Calendar Assignments Quizzes

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

    Week Tipics/Slides Readings Events
    Aug6-Aug10 Introduction, OOP Chapter 2
    Aug13-Aug17 Arrays and Linked Lists, Recursion Chapter 3 Q1
    Aug20-Aug24 Analysis Tools 1, Analysis Tools 2 Chapter 4
    Aug27-Aug31 Stacks, Queues , Positions, Itertators Chapter 5, 6 L1
    Sep3-Sep7 Tree Structures, Binary Trees Chapter 8 Q2
    Sep10-Sep14 Heaps and Priority Queues Chapter 9, 10 (10.1-10.3) L2
    Sep17-Sep21 MAPS, Hash Tables Chapter 9.1-9.2 Q3
    Sep24-Sep28 Ordered maps, Dictionary, Skip lists, Review Problems Chapter 9.1-9.2 L3
    Oct1-Oct7 Mid Semester Exam
    Oct8-Oct12 AVL Trees, 2-4 Multiway Trees Chapter 11 (11.1-11.3)
    Oct15-Oct19 Red-Black Trees Chapter 11(11.3-11.6) L4
    Oct22-Oct26 Sorting Chapter 12.1-12.3 Q4
    Oct29-Nov2 Strings, Dynamic Programming Chapter 12.5, Chapter 13 (13.1-13.4) L5
    Nov5-Nov9 Buffer week Q5
    Nov12-Nov16 Graphs1 Chapter 14 (14.1-14.3) L6
    Nov19-Nov23 Graphs2 Chapter 14(14.4-14.6) Q6
    Nov26-Nov30 Buffer week
    Dec3-Dec11 End Semester Exam

    *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.

    Scroll to top

    Quizzes

    Quiz1 - [16/08/2018]

    Quiz2 - [05/19/2018]

    Scroll to top

    Assignments

    Assignment 1 - [Due on 28/08/2018]

    Scroll to top