CS2700: Programming and Data Structures

Course information

  • When: Jul-Nov 2022

  • Lectures: Slot C

  • Where: CS25

  • Teaching Assistants: Nalin Raj Gudipati, Rishabh Singh, Vrushab Ramesh Karia, Amishi Panwar, Ashish Parjapati, Jatin Singh Kanyal, Kartik Arvindbhai Gondaliya, B Abhijit, Muhammed Tharikh, Nitesh Rakesh Patwa, Susmit Jaiswal, Yashasvi Mahajan

Course Content

  • Analysis of algorithms using time and space complexity.

  • Arrays, lists, stacks, queues, trees.

  • Searching and sorting algorithms.

  • Graph algorithms, dynamic programming.

Grading

  • Quiz-I and II: 15% each

  • Final exam: 40%

  • Tutorials: 6% each (Best 5 out of 7)

Important Dates

  • Tutorials: 5 Aug, 19 Aug, 5 Sep, 16 Sep, 14 Oct, 28 Oct, 4 Nov

  • Quiz-I: 24 Aug

  • Quiz-I: 28 Sep

  • Final exam: 14 Nov

Textbooks

  • Michael T. Goodrich, Roberto Tamassia, and David M. Mount. Data structures and algorithms in C++. John Wiley & Sons, 2011.

  • Mark A. Weiss. Data structures and algorithm analysis in C++. Pearson, 2014.

Schedule

Lecture number Topics Covered Section reference
Lecture 1 Analysis of algorithms:
Primitive operations and growth rate		 Section 4.2 of [Goodrich et al.]
Lecture 2 Analysis of algorithms:
Big-oh notation, asymptotic analysis		 Section 4.2 of [Goodrich et al.]
Lecture 3 Analysis of algorithms:
Prefix averaging example, friends of Big-oh		 Section 4.2 of [Goodrich et al.]
Lecture 4 Recurrence equations:
Iterative substitution and guess-and-test
solution approaches 		Section 11.1.5 of [Goodrich et al.]
Lecture 5 Recurrence equations: Master method Appendix A of [Goodrich et al.]
Lecture 6 Merge-sort Section 11.1 of [Goodrich et al.]
Tutorial 1
Lecture 7 Sorting lower bound Section 11.3 of [Goodrich et al.]
Lecture 8 Quick-sort Section 11.2 of [Goodrich et al.]
Lecture 9 Worst-case runtime of quick-sort Section 11.2 of [Goodrich et al.]
Lecture 10 Average-case runtime of quick-sort Section 11.2 of [Goodrich et al.]
Lecture 11 Bucket and radix sort Section 11.3.2 of [Goodrich et al.]
Tutorial 2
Lecture 12 Tutorial-2 discussion
Quickselect		 Section 11.5 of [Goodrich et al.]
Lecture 13 Average-case analysis of quickselect
Sets data structure		 Section 11.5 and 11.4 of [Goodrich et al.]
Quiz 1
Lecture 14 Stacks Section 5.1 of [Goodrich et al.]
Lecture 15 Applications of stacks: evaluating expressions and computing spans Section 5.1 of [Goodrich et al.]
Lecture 16 Queues and singly-linked lists Sections 5.2 and 3.2 of [Goodrich et al.]
Lecture 17 Doubly-linked lists, and growable arrays (vectors) Sections 3.3 and 6.1 of [Goodrich et al.]
Tutorial 3
Lecture 18 Circular linked lists, Sequence ADT Sections 3.4 and 6.3 of [Goodrich et al.]
Lecture 19 Trees: Definition, Traversal algorithms Sections 7.1 and 7.2 of [Goodrich et al.]
Lecture 20 Binary Trees: Properties, Application (expression trees) Section 7.3 of [Goodrich et al.]
Lecture 21 Implementation of Trees
Priority Queues, Selection and Insertion Sort		 Sections 8.1 and 8.2 of [Goodrich et al.]
Lecture 22 Heaps: Definition, Priority Queue implementation Section 8.3 of [Goodrich et al.]
Problem solving session
Tutorial 4
Lecture 23 Heap-sort, Quiz 1 discussion Section 8.3 of [Goodrich et al.]
Lecture 24 Bottom-up heap construction, solving problems on heaps Section 8.3 of [Goodrich et al.]
Lecture 25 Maps ADT Section 9.1 of [Goodrich et al.]
Problem solving session on trees and heaps
Lecture 24 Hash functions and hash codes Section 9.2 of [Goodrich et al.]
Lecture 25 Hashing: Compression functions and
collision handling (separate chaining)		 Section 9.2 of [Goodrich et al.]
Quiz 2
Lecture 26 Quiz-2 discussion
Hashing: Collision handling via linear probing		 Section 9.2 of [Goodrich et al.]
Lecture 27 Hashing: Collision handling via quadratic probing and double hashing Section 9.2 of [Goodrich et al.]
Lecture 28 Dictionary ADT and implementation guidelines Section 9.5 of [Goodrich et al.]
Lecture 29 Skip lists: Search, insertion and deletion Section 9.4 of [Goodrich et al.]
Lecture 30 Probabilistic analysis of skip lists Section 9.4 of [Goodrich et al.]
Problem solving session on hashing and skip lists
Tutorial 5
Lecture 31 Binary search trees: Definition, find and insert operations Section 10.1 of [Goodrich et al.]
Lecture 32 Deletion in binary search trees, introduction to AVL trees Sections 10.1 and 10.2 of [Goodrich et al.]
Lecture 33 AVL trees: Update operations Section 10.2 of [Goodrich et al.]
Problem solving session on search trees
Lecture 34 (2,4) trees: Introduction, insertion Section 10.4
Tutorial 6
Lecture 35 Dynamic programming: Matrix chain product Section 12.2.1
Lecture 36 (2,4) trees: Deletion Section 10.4
Lecture 37 Dynamic programming: Longest common subsequence Section 12.2.2
Lecture 38 Dynamic programming: Allocation problems Chapter 1 of [Applied DP, Bellman and Dreyfus, 1962]
Tutorial 7
Problem solving session on sorting, trees, heaps, dynamic programming