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 Section 9.2 of [Goodrich et al.]
Quiz 2