Madhavan Mukund

Programming and Data Structures with Python

Aug–Nov 2023

Administrative details

• Instructor: Madhavan Mukund

• Teaching Assistants: G Aravind Adithya, Sheikh Shakil Akhtar

• 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

Graded Assignments

• Graded Assignment 1, 20 September 2023, due 27 September, 2023
  (test on Swayam portal, submit via Moodle)

• Graded Assignment 2, 1 October 2023, due 9 October, 2023
  (test on Swayam portal, submit via Moodle)

• Graded Assignment 3, 11 October 2023, due 19 October, 2023

• Graded Assignment 4, 28 October 2023, due 4 November, 2023

• Graded Assignment 5, 12 November 2023, due 20 November, 2023

• Graded Assignment 6, 22 November 2023, due 27 November, 2023
  (test on Swayam portal, submit via Moodle)

Practice Assignments

• Practice Assignment 1, 30 August 2023, ( Jupyter notebook, pdf)

• Practice Assignment 2, 14 September 2023 (on Swayam portal), Test data

• Practice Assignment 3, 19 September 2023 (on Swayam portal), Test data

• Practice Assignment 4, 19 September 2023 (on Swayam portal), Test data

Lectures

• Lecture 1: 08 Aug 2023
  (Class Notes (pdf), Lecture Notes (pdf), Spreadsheet)

  Introduction to algorithms and programming

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

• Lecture 2: 10 Aug 2023
  (Lecture Notes [Jupyter notebook], [pdf])

  Examples from Lecture 1 worked out in Python – variable assignment, for, if, while, list, tuple, dictionary

• Lecture 3: 14 Aug 2023
  (Lecture Notes [Jupyter notebook], [pdf])

  Python basics: names, values, types, expressions, functions

• Lecture 4: 17 Aug 2023
  (Lecture Notes [Jupyter notebook], [pdf])

  Python basics: functions, if-else, list concatenate/append, for

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

  Python basics: range(), while, iteration, nested iteration

• Lecture 6: 24 Aug 2023
  (Lecture Notes [Jupyter notebook], [pdf])

  Python: nested loops, if-elif-else, list slices, nested lists, strings, tuples, dictionaries

• Lecture 7: 05 Sep 2023
  (Lecture Notes [Jupyter notebook], [pdf])

  Python: dictionaries, input/output, type conversion, tuples and multiple assignment, mutable and immutable values

• Lecture 8: 07 Sep 2023
  ( Class Notes, Lecture Notes [Jupyter notebook], [pdf], )

  Lists, arrays, dictionaries.
  Experiments with lists, arrays, dictionaries

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

  Implementing a linked list using nested dictionaries
  Map, filter, list comprehension

• Lecture 10: 14 Sep 2023
  ( Class Notes, Lecture Notes [Jupyter notebook], [pdf], )

  Inductive definitions, recursive functions
  Classes and objects

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

  Classes and objects, linked lists

• Lecture 12: 21 Sep 2023
  ( Class Notes, Lecture Notes (linked lists) [Jupyter notebook], [pdf], Lecture Notes (numpy) [Jupyter notebook], [pdf], )

  Linked lists, numpy

• Lecture 13: 26 Sep 2023
  (Lecture Notes (numpy) [Jupyter notebook], [pdf], Lecture Notes (pandas) [Jupyter notebook], [pdf])

  Numpy: arrays, stacking and splitting, reshaping, axes, broadcasting

  Pandas: series and data frames

• Lecture 14: 10 Oct 2023
  ( Class Notes)

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

• Lecture 15: 17 Oct 2023
  ( Class Notes)

  Analysis of algorithms, Searching, Sorting — selection sort, insertion sort

• Lecture 16: 19 Oct 2023
  ( Class Notes, Searching/sorting experiments [Jupyter notebook], [pdf])

  Recursive insertion sort, Merge sort

• Lecture 17: 24 Oct 2023
  ( Class Notes, Quicksort experiments [Jupyter notebook], [pdf])

  Quicksort, stable sorting

• Lecture 18: 26 Oct 2023
  ( Class Notes)

  Stacks, queues, priority queues, heaps

• Lecture 19: 31 Oct 2023
  ( Class Notes)

  Building heaps, heapsort, binary search trees

• Lecture 20: 02 Nov 2023
  ( Class Notes)

  AVL trees

• Lecture 21: 07 Nov 2023
  ( Class Notes)

  Memoization, Dynamic Programming: grid paths

• Lecture 22: 09 Nov 2023
  ( Class Notes)

  Dynamic Programming: longest common subword, longest common subsequence, edit distance

• Lecture 23: 14 Nov 2023
  ( Class Notes)

  Dynamic Programming: matrix multiplication order, longest ascending subsequence

• Lecture 24: 16 Nov 2023
  ( Class Notes)

  Backtracking; Global and local variables

• Lecture 25: 23 Nov 2023
  ( Class Notes)

  Reading/writing files, formatted output, passing parameters to functions