DS286: Data Structures and Programming

Department of Computational and Data Sciences

Data Structures and Programming

  • Instructor: Yogesh Simmhan (email | www)
  • Teaching Assistant: Prateeksha Varshney (email)
  • Course number: DS286 (Formerly SE286)
  • Credits: 2:1
  • Semester: Aug, 2016
  • Lecture: Wed/Fri 10-11AM, Lab: Mon 10-11AM
  • Room: CDS/SERC 202

Overview

This is an introductory course in data structures and programming, meant for students who have not had a formal course in programming, algorithms and data structures as part of their undergraduate program. The course will introduce of problem solving using programs and design of algorithms and their complexity. It will review elementary data structures such as Arrays, Stack, Queues, Maps, and related algorithms for manipulating the data structures. It will also discuss sorting and searching techniques, and their complexity. We will also briefly explore more advanced data structures such as graphs and graph algorithms, balanced trees, tries and heaps. A overview of parallelism and concurrent data structures will also be given toward the end of the course. Algorithmic strategies such as greedy Algorithms, Dynamic Programming and Divide and Conquer will also form part of the learning.

These lectures will be complemented by lab sessions that introduce object oriented programming with C++, implementing the data structures using C++, and also using standard data structure libraries present in the language. There will be periodic programming assignments to validate these concepts.

Topics in this course are loosely based on IEEE and ACM’s Curriculum Guidelines for Undergraduate Degree Programs in Computer Engineering, a draft of which is available online.

This course is a precursor to more advanced courses like E0 251: Data Structures and Algorithms, E0 225: Design and Analysis of Algorithms, DS 292: High Performance Computing, DS 295: Parallel Programming, and DS 256: Scalable Systems for Data Science. Students already familiar with data structures and programming may prefer those rather than this introductory course.

Pre-requisites

This is an introductory course on data structures and programming. So the pre-requisites are minimal — knowing to operate a computer, preferable Linux, using the commandline, installing packages, using SSH, using a text editor or IDE — but students are expected to pick up the skills rapidly as part of the lab sessions.

Assessment

The total assessment score for the course is based on a 1000 point scale. Of this, the weightage to different activities will be as follows:

40% Homework About 7 programming assignments of 50-100 points each (400 points)
10% Online Coding Self-selected programming assignments on online coding website (CodeChef) (100 points)
50% Exams One Mid-term (200 points) and one Final (300 points) exam.

Academic Integrity

Students must uphold IISc’s Academic Integrity guidelines. We have a zero-tolerance policy for cheating and unethical behavior in this course and failure to follow these guidelines will lead to sanctions and penalties. This includes a reduced or failing grade in the course, and recurrent academic violations will be reported to the Institute and may lead to an expulsion.

Learning takes place both within and outside the class. Hence, discussions between students and reference to online material is encouraged as part of the course to achieve the intended learning objectives. However, while you may learn from any valid source, you must form your own ideas and complete problems and assignments by yourself. All works submitted by the student as part of their academic assessment must be their own.

Plagiarism
Verbatim reproduction of material from external sources (web pages, books, papers, etc.) is not acceptable. If you are paraphrasing external content (or even your own prior work) or were otherwise influenced by them while completing your assignments, projects or exams, you must clearly acknowledge them. When in doubt, add a citation!
Cheating
While you may discuss lecture topics and broad outlines of homework problems and projects with others, you cannot collaborate in completing the assignments, copy someone else’s solution or falsify results. You cannot use notes or unauthorized resources during exams, or copy from others. The narrow exception to collaboration is between team-mates when competing the project, and even there, the contribution of each team member for each project assignment should be clearly documented.
Classroom Behavior
Ensure that the course atmosphere, both in the class, outside and on the online forum, is conducive for learning. There are no “stupid” questions, so ask away. Actively participate in discussions but do not dominate or be abusive. Be considerate of your fellow students and avoid disruptive behavior.

Resources

Teaching & Office Hours

  • Lecture: Wed and Fri 10-11AM, CDS/SERC 202 (Yogesh)
  • Lab: Mon 10AM-11AM, CDS/SERC 202 (Prateeksha)
  • Office Hours: By appointment

Tentative Schedule

The course schedule — both dates and topics — are subject to change. Please subscribe to the mailing list to get notified of changes.

Lecture Schedule

No.DateTopicsSlides
12016-08-05
Introduction to the CourseL1 slides
22016-08-12Introduction to ProgrammingL2 slides
32016-08-17Introduction to Software DesignL3 slides
4,52016-08-24,26Lists, Linked list, Arrays, Sparse MatricesL4+5 slides
6,72016-08-31,2016-09-02Introduction to Algorithmic AnalysisL6+7 slides
82016-09-07StacksL8 slides
92016-09-09QueuesL9 slides
102016-09-14Dictionary, Skip ListL10 slides
11,122016-09-16,21Hashmap, Hash FunctionL11+12 slides
13,142016-09-23,26Tree, Binary Trees, Expression TreesL13+14 slides
15,162016-09-28,30Binary Search TreeL15+16 slides
172016-10-05SortingL17 slides
*2016-10-07MIDTERM EXAM (200 points)
Topics from Lectures 1-16		Midterm review
182016-10-14Balanced Trees: AVL TreesL18 slides
192016-10-21Balanced Trees: B-TreeL19 slides
20-212016-10-26,28Graph Data StructuresL20-21 slides
22-232016-11-02,04Graph AlgorithmsL22-23 slides
242016-11-04Heap, Priority Queue
L24 slides
25-262016-11-11,16Algorithmic Strategies: Dynamic programming, Greedy strategies
L25-26 slides
27-292016-11-18,23,25Concurrent Data StructuresL27-28 slides, L29 slides
*2016-12-07, 11AMFINAL EXAM (300 points)
Topics from Lectures 1-30

Lab Schedule

DS286-Aug16 Lab Schedule

No.DateTopicsSlides
12016-08-08
Introduction to C++, Hello World, IDE, compiling
Lab 1

https://www3.ntu.edu.sg/home/ehchua/programming/howto/EclipseCpp_HowTo.html,
http://www.ubuntuhandbook.org/index.php/2014/06/install-latest-eclipse-ubuntu-14-04/,
http://www.eclipse.org/downloads/eclipse-packages/
22016-08-10
Introduction to C++, OO programmingLab 2
32016-08-19Intro to C++, primitive types, control flow, Pointers, Memory Management.
Assignment 1 To Be Posted
Lab 3?
42016-08-22Intro to C++, Pointers, Memory Management, Makefile, Headers. Review of Assignment 1.Lab 4?
52016-08-29C++ Lists, Linked List, Arrays, etc.
Assignment 2 To Be Posted
62016-09-14
72016-09-19
82016-09-26
.........

Assignments

  • Assignment 0
  • Assignment 1 [PDF] (Posted on 2016-08-20, Due on Sunday 2016-08-28 by 11:59PM IST) [50 points]

    • Skeleton Code required for assignment: DS286.Aug16.A01
    • Errata: The skeleton code can store only 6 items at a time in the list. So example 4 in Sample Inputs section with 8 inputs retained at a time will not work: 
      ./listdemo.out a157a2.0a3.0a0.0a.1a1.0a.1e10a1e23p
[157,2.0,3.0,0.0,0.1,1.0,0.1e10,1e23]

      Instead, replace example with:

      ./listdemo.out a157a2.0a3.0a.1a.1e10a1e23p
[157,2.0,3.0,0.1,0.1e10,1e23]
  • Assignment 2 (Posted on 2016-08-29, Due on Sunday, September 11, 2016, 11:59pm IST) [50 points]
  • Assignment 3 (Posted on 2016-09-15, Due on Wednesday, September 28, 2016, 11:59pm IST) [75 points]

    • Assignment description:  ds286-aug16-assignment3.pdf
    • Skeleton code: ds286-aug16-03assgn.tar
    • Errata: In ParenMatch.h, the comment: 
      // Updates the Expression in parenStack as necessary.

      should instead read:

      // Updates the Expression in exprStack as necessary.
  • Assignment 4 (Posted on 2016-10-13, Due on Wednesday October 26, 2016, 11:59pm IST) [75 points]
  • Assignment 5 (Posted on 2016-10-28, Due on  Monday, 14 November, 2016, 11:59pm IST) [100 points]
    • Assignment description: ds286-aug2016-a05.pdf
    • TBD: Sample graph files small.in , medium.in and large.in with input parameters.