COL 106 - Datastructures and Algorithms (2019-20 Sem 2)

Course Information

5 Credits (3 - 0 - 4)

Pre-requisite : COL 100

Instructors

The course is taught in two sections, with two different instructors:

  1. Srikanta Bedathur and
  2. Chetan Arora

Lecture slot: F (TWF 11:00-12:00)

Locations

  1. LH 108 (Srikanta, groups 1-4)
  2. LH 111 (Chetan, groups 5-8)

Signup code “col106-2020”

ANNOUNCEMENTS

  • [3-Jan-2020] Screen-scratches and slides for lectures are regularly updated on a shared Google folder.
  • [1-Jan-2020] Lab sessions will be on weekdays between 3pm-5pm during entire January. These will have scheduled help sessions and attendance.
  • [31-Dec-2019] It has been decided not to increase the vacancy of the course - it stays at 385.

Teaching Assistants



Contents


We plan to use Java as the programming language throughout the course, and use JUnit framework

Following is a tentative list of topics (in no particular order):

  • 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, optimal and average BSTs. Balanced BST: AVL Trees, 2-4 trees, red-black trees, B-trees.
  • Priority queues and binary heaps.
  • Sorting: selection, merge, quick, and radix sorts
  • Graphs: Breadth first search and connected components. Depth first search in directed and undirected graphs.
  • Dijkstra’s algorithm, directed acyclic graphs and topological sort.

Textbooks

There is no specific textbook for the course, but we will roughly follow Datastructures and Algorithms in Java by Goodrich and Tamassia. You need not buy a copy of the book.

Tutorials for Java

A number of online tutorials are available for Java.

  1. An excellent “teach-yourself Java” module prepared by Prof. Amitabha Bagchi and the associated code

Lecture schedule

Date Topic Slides/screenscratch (Srikanta) Slides/screenscratch (Chetan)
31-Dec-2019 Intro and Logistics -

Grading scheme

Avatar
Srikanta Bedathur
Associate Professor and Pankaj Gupta Faculty Fellow

Related