Course-instructor: Ahnaf Hosssain Rodoshi (AHR)
Course Outline:
| Week & lecture | Topic |
|---|---|
| Week 1 | Arrays |
| Lecture 1 | Linear Array, Array creation, iteration, copying, resize, reverse,shifting left-right, rotating left-right, insertion, deletion etc |
| Lecture 2 | Circular Array Forward and backward iteration, linearization, resizing, insertion and deletion. |
| Week 2 | Linked Lists |
| Lecture 1 | Singly Linked list Creation, iteration, counting elements, searching elements by value or index, insertion, removal, copying, reverse, left right rotation etc. |
| Lecture 2 | Doubly Linked list Creation, iteration, insertion, deletion, link list conversions etc |
| Week 3 | Stacks and Queues |
| Lecture 1 | Stack Implementation, infix-postfix conversions, string reversal, edit history maintenance, grid traversal, histogram problem etc. |
| Lecture 2: | Queue Implementation, palindrome checking, grid traversal etc. |
| Week 4 | Recursion |
| Lecture 1 | Recursive definitions recurrence relations, recursive programming, fibonacci numbers, factorials, length of a string or list, sum of an array, exponentiation etc. |
| Lecture 2 | linear search, binary search, finding max of a list in the linear way or the divide and conquer approach, selection sort, insertion sort and bubble sort, Iterative memoization and recursive memoization. |
| Week 5 | Searching and Sorting |
| Lecture 1 | Searching Linear search, binary search, ternary search, random search etc. |
| Lecture 2 | Sorting Insertion sort, bubble sort, selection sort etc. |
| Week 6 | Graph |
| Lecture 1 | Graph Terminologies Directed vs undirected graphs, weighted vs unweighted graphs, directed acyclic graphs etc Lecture 2 |
| Week 7 | Trees |
| Lecture 1 | Tree terminologies Free tree vs rooted tree, ordered tree, n-ary tree tree, binary tree etc, recursive definitions of n-ary tree, rooted tree, ordered tree etc |
| Lecture 2 | Tree Traversal pre-order, post order, in-order, breadth first, depth first etc, some recursive algorithms Finding the depth, sum, max etc of a tree. |
| Week 8 | Unbalanced Binary Trees |
| Lecture 1 | Examples of unbalanced binary trees |
| Lecture 2 | Performance analysis of binary search tree |
| Week 9 | Priority Queue and Heap |
| Lecture 1 | Priority Queue using sorted or unsorted array |
| Lecture 2 | Priority Queue using heap |
| Week 10 | Balanced Binary Trees |
| Lecture 1 | Tree Balancing, examples of BBT such as Red-black tree, AVL tree, Treap etc. |
| Lecture 2 | Performance analysis of AVL tree. |
| Week 11 | Hashing |
| Lecture 1 | Key indexed searching aka counting sort |
| Lecture 2 | Hash Tables |
Marks Allotment:
- Quizzes: 5-10%
- Assignments: 15-20%
- Labs: 25%
- Midterm: 20%
- Final Exam: 30%
-
Introduction to Algorithms is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
-
The Algorithm Design Manual by Steven Skiena Algorithms in Java by Robert Sedgewick
-
Practice data structures problems here at https://www.hackerrank.com/domains/data-structures.
-
For data structures visualization https://visualgo.net/en
Google doc link to course info & outline & resources : here
Personal Drive folder for cse220 here
Self Suggestion
Workload - 30 days
Ending on 1st August: 2022