# CS 220: Data Structures and Algorithms

September 2020

This course will give an introduction to C/C++ programming along with an introduction to Data structure and Algorithms. This is a core course for CS and M&C undergraduate students.

## Details

### Time and Place

• Monday - 9:30 - 10:30 AM
• Tuesday - 2:00 - 3:00 PM
• Friday - 10:30 - 11:30 AM
• (lab) Monday - 4:00 - 6:00 PM

### Video lecture playlist

• Data structure:

## Course Schedule - C/C++ Programming

Week # Topic Resources
1 23/8 Introduction to C
0 First day meeting video link
1 Lecture 1.1 Hello World, Lecture 1.2- Comments, Lecture 1.3 - Basic data types (int, float, char), Lecture1.4 - Review with an example. Creating a resume Lecture 1.1 Lecture 1.2 Lecture 1.3 Lecture 1.4
2 Lecture 2.1 - if else, Lecture 2.2 - Functions, Lecture 2.3 - Scope of a variable Lecture 2.1 Lecture 2.2 Lecture 2.3
3 Lecture 3.1 - Arrays and Strings, Lecture 3.2 - Passing arrays to functions, Lecture 3.3 - Loops (for, while, do while) Lecture 3.1 Lecture 3.2 Lecture 3.3
4 Lecture 4.1 - constants, Lecture 4.2 - Getting user input (using getchar function), Lecture 4.3- Using getchar to get user input from the keyboard Lecture 4.1 Lecture 4.2 Lecture 4.3
2 30/8 Recursion
1 Lecture 5.1 - Recursion, Lecture 5.2 - Recursion example (factorial) , Lecture 5.3 - Recursion Checking for correctness, Lecture 5.4 - Factorial function (lab) , Lecture 5.5 - Execution path for recursive functions Lecture 5.1 Lecture 5.2 Lecture 5.3 Lecture 5.4 Lecture 5.5
2 Lecture6.1 - Binary recursion (eg. Fibonacci number), Lecture 6.2 - Binary recursion, Fibonacci numbers,Subsets of a set, Lecture 6.3-Recursion explained through trees,Fibonacci sequence Lecture 6.1 Lecture 6.2 Lecture 6.3
3 Lecture 7.1 -Multiple recursion Example: mini Sudoku, Lecture 7.2- Mutual recursion Example: Tic Tac Toe, Lecture 7.3-Recursion explained through trees,Tic tac toe program Lecture 7.1 Lecture 7.2 Lecture 7.3
3 6/9 Pointers
1 Lecture 8.1 Binary and Decimal numbers, Lecture 8.2 Bits and Bytes, Lecture 8.3 Memory - Random access memory(RAM), Lecture 8.4 - sizeof operator Lecture 8.1 Lecture 8.2 Lecture 8.3 Lecture 8.4
2 Lecture 9.1- Introduction to pointers, Lecture 9.2 -Introduction to pointers (lab), Lecture 9.3 Pointers and Functions, Lecture 9.4 - Pointers and Arrays Lecture 9.1 Lecture 9.2 Lecture 9.3 Lecture 9.4
3 Lecture 10.1 - Dynamic Memory allocation,malloc, calloc, realloc, free, Lecture 10.2 - Pointer to a pointer, Lecture 10.3 - Array of pointers, Lecture 10.4-Two dimensional arrays and pointers to pointers, Lecture 10.5 - Command line arguments Lecture 10.1 Lecture 10.2 Lecture 11.2 Lecture 10.3 Lecture 10.4
4 13/9 File operations
1 Lecture 11.1 -scanf function , Lecture 11.2 - Using scanf (lab), Lecture 11.3- File handling (file opening, reading, writing, closing) for text files, Lecture 11.4 - command line arguments Lecture 11.1 Lecture 11.3
Structures
1 Lecture 12.1 - Introduction to Structures, Lecture 12.2 - Arrays of structures, Lecture 12.1 Lecture 12.2
2 Lecture 13.1 - shallow vs deep copy, Lecture 13.2 - passing as parameters, returning structures Lecture 13.1 Lecture 13.2
3 Lecture 14.1 - Structures, Dynamic memory allocation, Lecture 14.2 - File input/output with structures Lecture 14.1 Lecture 14.2
4 Lecture 15 - Read/Write Bitmap (BMP) Image, Display image in Text/ASCII Art Lecture 15
5 20/9 Object oriented programming (C++)
1 Lecture 16.1- Challenge to programmers, Lecture 16.2- Header Files Lecture 16.1 Lecture 16.2
2 Lecture 17.1 -Abstraction , Lecture 17.2- Encapsulation, Header files, Lecture 17.3- Data Abstraction, Why Class? Lecture 17.1 Lecture 17.2 Lecture 17.3
3 Lecture 18.1- Introduction to Classes ,Object oriented programming , Lecture 18.2- Constructors and Destructors in C++, Lecture 18.3 -Dynamic memory allocation in C++ ,new and delete , Lecture 18.4 -Polymorphism,Function overloading, Lecture 18.5 -Polymorphism,Operator overloading Lecture 18.1 Lecture 18.2 Lecture 18.3 Lecture 18.4 Lecture 18.5
Data Structures and Algorithm
2 16/11 4.1 Stack data structure : LIFO principle, 4.2 Implementation of Stack ADT : Linked List application, 4.3 Stack implementation (lab), 4.4 Parentheses matching :Application of Stacks, 4.5 Application of Stack data structure ,Example: Matching parentheses (lab), 5.1 Queue data structure: FIFO principle,Queue ADT implementation , 5.2 Queue ADT implementation using linked list (lab) Lecture 4.1 Lecture 4.2 Lecture 4.3 Lecture 4.4 Lecture 4.5 Lecture 5.1 Lecture 5.2
3 17/11 5.3 Tree data structure:Examples, 5.4 Tree terminology :Nodes-Edges,Parent-Child ,Root- Leaf-internal nodes, 6.1 Trees: Edges and Paths,Height and Depth of a tree,Ordered trees, 6.2 Tree Implementation, 6.3 Functions in a Tree ADT, 6.4 Tree: Algorithms for finding height and depth of a Tree, Recursion , 6.5 Trees :Summarizing properties of Trees , 6.6 Family Tree assignment Lecture 5.3 Lecture 5.4 Lecture 6.1 Lecture 6.2 Lecture 6.3 Lecture 6.4 Lecture 6.5 Lecture 6.6
4 1/12 7.1 Binary Trees, 7.2 Full and Complete Binary Trees, 7.3 Properties of Binary trees, 8.1 Tree traversals: pre-order and post-order traversals , 8.2 Tree traversals : Inorder traversal, 9.1 Binary search trees (BST): Introduction Lecture 7.1 Lecture 7.2 Lecture 7.3 Lecture 8.1 Lecture 8.2 Lecture 9.1
5 2/12 9.2 Binary Search Tree (BST): Search Lecture 9.2
6 3/12 9.3 Binary Search Tree: Insertion and Deletion, 10.1 Analysis of Algorithms, 10.2 Asymptotic notation: Big O notation, 10.3 Analysis of Algorithms ,Asymptotic notation, Examples Lecture 9.3 Lecture 10.1 Lecture 10.2 Lecture 10.3
7 7/12 11.1 Asymptotic notation :Theta and Omega notation, 11.2 Asymptotic notation: More examples, 11.3 Asymptotic notation :Introducing small o, 12.1 Asymptotic analysis of algorithms Lecture 11.1 Lecture 11.2 Lecture 11.3 Lecture 12.1
8 8/12 13.1 Searching :Linear Search, 13.2 Searching :Binary Search Lecture 13.1 Lecture 13.2
9 9/12 14.1 Sorting :Internal vs External, Stable sorting , 14.2 Insertion Sort, 14.3 Selection Sort Lecture 14.1 Lecture 14.2 Lecture 14.3
10 10/12 15.1 Bubble Sort, 15.2 Swap function :swap without extra variable , 15.3 Merge Sort Lecture 15.1 Lecture 15.2 Lecture 15.3
11 11/12 16.1 Simplified version of Quicksort algorithm :Worst case analysis,Average case analysis , 16.2 Quicksort algorithm Lecture 16.1 Lecture 16.2

## Books and Course Syllabus

### Books

• Introduction to Algorithms, by T. H. cormen, C.E. Leiserson, R. L. Rivest, C. Stein
• Algorithms in C by Robert Sedgewick

### Syllabus

• C Language : basics and programming with pointers
• Basic data structures: Lists, Stacks, Queues, Heaps and Hashing
• Time and space complexity of algorithm
• Trees: Tree traversals, Binary search trees, Self balancing trees
• Sorting : basic sorting algorithms- Insertion, bubble, merge and quicksort