Madhavan Mukund

Programming and Data Structures with Python

Aug–Nov 2024

Administrative details

• Instructor: Madhavan Mukund

• Teaching Assistants: Arnab Sur, Vardhan Kumar Ray

• Evaluation:

  • Quizzes, programming assignments, final exam

  • Weightage approximately 10%, 50%, 40%, to be confirmed

  • Copying is fatal

• Text and reference books:

  • We will not be following any specific text book. There are plenty of resources online. You can find a list of books at the following link: PythonBooks

  • The official Python tutorial is a good place to start learning Python if you already have some programming background.

Course plan

This list is approximate and subject to change.

• Programming in Python

  • Names, values, control flow
  • Lists, dictionaries, strings
  • Exception handling, input/output and files
  • Basics of object-oriented programming

• Data structures and algorithmic techniques

  • Searching and sorting
  • Quantifying efficiency
  • Loop invariants
  • Stacks, queues, priority queues, heaps
  • Backtracking
  • Balanced search trees
  • Dynamic programming

• Python for data science

  • Processing data from tables, displaying charts and graphs
  • numpy, pandas and matplotlib libraries

Assignments

• Assignment 1, 12 September 2024, due 20 September 2024 ( Jupyter notebook, pdf)

• Assignment 2, 2 October 2024, due 13 October 2024

• Assignment 3, 14 October 2024, due 24 October 2024

• Assignment 4, 24 October 2024, due 4 November 2024

• Assignment 5, 11 November 2024, due 18 November 2024

• Assignment 6, 22 November 2024, due 30 November 2024

Practice Assignments

• Practice Assignment 1, 22 August 2024, ( Jupyter notebook, pdf)

• Practice Assignment 2, 02 September 2024

Lectures

• Lecture 1: 06 Aug 2024
  (Class Notes (pdf), Lecture Notes (pdf))

  Introduction to algorithms and programming

  Examples: IPL data – variables, iteration, lists, tuples, dictionaries

• Lecture 2: 08 Aug 2024
  (Lecture Notes ([Jupyter notebook], [pdf]), IPL 2024 spreadsheet

• Lecture 3: 13 Aug 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Basic Python –- Data types: numbers (int and float) and operations, booleans, range(), math library, lists, iteration, functions

• Lecture 4: 20 Aug 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  More Python –- while loops, booleans, if-elif-else

• Lecture 5: 22 Aug 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Lists – positional indexing, slices; range with step; list functions - append, insert, extend, sort, ...

• Lecture 6: 27 Aug 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  List membership, tuples, strings, dictionaries

• Lecture 7: 29 Aug 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Unique elements via dictionary, nested collections, map, filter, list comprehension, mutable and immutable values

• Lecture 8: 10 Sep 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Mutable and immutable values, passing values to functions, the value None

• Lecture 9: 12 Sep 2024
  (Class Notes (pdf), Lecture Notes [Jupyter notebook], [pdf]))

  Local and global scope in Python; arrays and lists

• Lecture 10: 17 Sep 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Arrays, lists, dictionaries; experiments to measure performance; implementing a list using nested dictionaries

• Lecture 11: 19 Sep 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Inductive definitions and recursive functions; introduction to abstract datatypes

• Lecture 12: 24 Sep 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Object-oriented programming: classes, objects, special functions

• Lecture 13: 26 Sep 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Abstract datatypes: building a linked list

• Lecture 14: 08 Oct 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Linked lists: recursive append and delete

  Basic exception handling

• Lecture 15: 10 Oct 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Exception handling: raising exceptions

  Input/output: String formatting, modifying behaviour of print(), introduction to file handling

• Lecture 16: 15 Oct 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]), Sample text file oz.txt) )

  Input/output: Reading and writing files, stripping whitespace

  Numpy: Creating arrays, stacking and splitting, axes, matrix operations, reshaping, copies and views, broadcasting

• Lecture 17: 17 Oct 2024
  (Lecture notes ([Jupyter notebook], [pdf]), Sample csv files (zipped) )

  Pandas: series, data frames, reading csv files, summary information

• Lecture 18: 22 Oct 2024
  ( Class Notes (pdf))

  Complexity of algorithms: Motivating example, asymptotic complexity, big-O notation

• Lecture 19: 24 Oct 2024
  ( Class Notes (pdf))

  Binary search, selection sort, insertion sort, introduction to merge sort

• Lecture 20: 29 Oct 2024
  (Class Notes (pdf), Lecture Notes ([Jupyter notebook], [pdf]))

  Merge sort, quicksort, randomized quicksort, stable sorting, experiments with searching and sorting

• Lecture 21: 05 Nov 2024
  ( Class Notes (pdf))

  Stacks, queues, priority queues, heaps, heap sort

• Lecture 22: 07 Nov 2024
  ( Class Notes (pdf))

  Binary search trees - find, inorder traversal, min/max, insert, delete, Python implementation; AVL trees

• Lecture 23: 19 Nov 2024
  ( Class Notes (pdf))

  Memoization, Dynamic Programming: grid paths, longest common subword

• Lecture 24: 21 Nov 2024
  ( Class Notes (pdf))

  Dynamic Programming: longest common subsequence, edit distance, matrix multiplication