CS213 | Data Structures and Algorithms
  • Rating: 4.85
  • (439)
Course overview

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in C++ programming language and will practice implementing them in programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structu

What you will learn
  • CLO-1 Understand the design of fundamental data structures as well as algorithms that operate on them. (C2 - Understanding).

  • CLO-2 Get rigorous hands-on experience on implementing different data structures in a programming language. (C3 - Applying).

  • CLO-3 Summarize data structures according to their typical uses, strengths, and weaknesses for designing optimized computer-based systems. (C4 - Analyzing).

Introduction to Algorithms
Solving the Problem: Improve the Nave Solution, Why Study Algorithms?, Example: Fibonacci Series, Greatest Common Divisor, Big-O Notation
Basic Data Structures
Arrays, Singly/Doubly-Linked Lists, Stack Implementation Arrays and Linked List, Stack Application RPN, Queue Implementation Arrays and Linked List, D-Queues
Data Structure - Tree
Trees API, Tree Traversals, Priority Queues, Heaps, Binary Trees, Complete Binary Trees, Heap Sort, Disjoint Sets
Hash Tables & Binary Search Trees
Applications of Hashing, Direct Addressing Hash Functions, Hash Tables Phone Book Problem, Hashing Strings, Search Trees, Basic Operations, BST Applications
Decomposition of Graphs
Graph Basics, Representing Graphs, Exploring Graphs, Connectivity, Pre-visit and Post-visit Ordering, Directed Acyclic Graphs
Paths in Graphs
Connected Components, Depth First Search Breadth First Search, Implementation of Search, Proof of Correctness
Shortest Path Algorithm
Shortest-Path Tree, Fastest Route, Nave Algorithm, Dijkstras Algorithm
Minimum Spanning Trees
Building a Network, Kruskals Algorithm, Prims Algorithm
Course program
Course marks will be based on five equally-weighted projects due throughout the term, one mid-term examination, and one final examination.
Lessons Name Description Duration Week Slides
1 Introduction Algorithms, Data Structures, Abstract Data Type, Programming 1 hours 1 DSAF2101-01
2 Solving Problems Maximum Pairwise Product, Nave Solution, Stress Test, Faster Solution 2 hours 1 DSAF2101-02
3 Fibonacci Series Algorithms and Complexity, Nave Algorithm, Faster Algorithm 1 hours 2 DSAF2102-01
4 Greatest Common Divisor Algorithms and Complexity, Nave Algorithm, Faster Algorithm 1 hours 2 DSAF2102-02
5 Big-O Notation Computing Runtimes, Asymptotic Notation, Growth Rate 1 hours 2 DSAF2102-03
6 Arrays Multi-Dimensional Arrays, Common Operations 1 hours 3 DSAF2103-01
7 Linked List Singly Linked List, Doubly Linked List 1 hours 3 DSAF2103-02
8 List API Singly Linked List Implementation 1 hours 3 DSAF2103-03
9 Stack ADT Stack Implementation - Array Class 1 hours 4 DSAF2104-01
10 Stack API Stack Implementation - List Class, Parsing XHTML 2 hours 4 DSAF2104-02
11 Stack Application Reverse Polish Notation, Infix to Postfix, Evaluate RPN 3 hours 5 DSAF2104-03
12 Queue ADT Queue Implementation - List Class 1 hours 6 DSAF2105-01
13 Queue ADT Queue Implementation - Array Class, Circular Queue 2 hours 6 DSAF2105-02
14 Deque The STL and Iterator 2 hours 7 DSAF2105-03
15 Trees Terminology and Applications 1 hours 7 DSAF2106-01
16 General Tree Tree Implementation - Abstract Tree 2 hours 8 DSAF2106-02
17 Tree Traversals Breadth & Depth First Traversals 1 hours 8 DSAF2106-03
18 Binary Tree Implementation - Binary Node Class 1 hours 9 DSAF2107-01
19 Binary Tree Traversal In-Order, Post-Order, Pre-Order, Euler Tour 2 hours 9 DSAF2107-02
20 Priority Queues Nave Implementation 1 hours 10 DSAF2107-03
21 Binary Heaps Priority Queues - Efficient Implementation 1 hours 10 DSAF2107-04
22 Complete Binary Tree Definition, Advantages, Pseudocode 1 hours 10 DSAF2107-05
23 Disjoint Sets Merging Two Lists, Nave Implementation 1 hours 11 DSAF2108-01
24 Forests Disjoint Sets - Union By Rank 2 hours 11 DSAF2108-02
25 Binary Search Tree BST via Arrays, Link List and Hash Tables 1 hours 12 DSAF2109-01
26 BST Binary Search Tree - Basic Functions 2 hours 12 DSAF2109-02
27 Graph Theory Graph Terminology and Applications 1 hours 13 DSAF2110-01
28 Graph ADT Adjacency Matrix, Sparse Matrix 2 hours 13 DSAF2110-02
29 Graph Traversals Breadth & Depth First Traversals 1 hours 14 DSAF2110-03
30 Connectedness Connected Graph Components 1 hours 14 DSAF2110-04
31 Graph Paths Single Source Unweighted Path Lengths 1 hours 14 DSAF2110-05
32 Minimum Spanning Tree Spanning Trees - Definition and Applications 1 hours 15 DSAF2110-06
33 Prim's Algorithms Algorithm and Applications 1 hours 15 DSAF2110-07
34 Kruskal's Algorithm Algorithm and Applications 1 hours 15 DSAF2110-08
Lessons Name Description Duration Week Slides
1 Introduction Algorithms, Data Structures, Abstract Data Type, Programming 1 hours 1 DSAF1901-01
2 Solving Problems Maximum Pairwise Product, Nave Solution, Stress Test, Faster Solution 2 hours 1 DSAF1901-02
3 Fibonacci Series Algorithms and Complexity, Nave Algorithm, Faster Algorithm 1 hours 2 DSAF1902-01
4 Greatest Common Divisor Algorithms and Complexity, Nave Algorithm, Faster Algorithm 1 hours 2 DSAF1902-02
5 Big-O Notation Computing Runtimes, Asymptotic Notation, Growth Rate 1 hours 2 DSAF1902-03
6 Arrays Multi-Dimensional Arrays, Common Operations 1 hours 3 DSAF1903-01
7 Linked List Singly Linked List, Doubly Linked List 1 hours 3 DSAF1903-02
8 List API Singly Linked List Implementation 1 hours 3 DSAF1903-03
9 Stack ADT Stack Implementation - Array Class 1 hours 4 DSAF1904-01
10 Stack API Stack Implementation - List Class, Parsing XHTML 2 hours 4 DSAF1904-02
11 Stack Application Reverse Polish Notation, Infix to Postfix, Evaluate RPN 3 hours 5 DSAF1904-03
12 Queue ADT Queue Implementation - List Class 1 hours 6 DSAF1905-01
13 Queue ADT Queue Implementation - Array Class, Circular Queue 2 hours 6 DSAF1905-02
14 Deque The STL and Iterator 2 hours 7 DSAF1905-03
15 Trees Terminology and Applications 1 hours 7 DSAF1906-01
16 General Tree Tree Implementation - Abstract Tree 2 hours 8 DSAF1906-02
17 Tree Traversals Breadth & Depth First Traversals 1 hours 8 DSAF1906-03
18 Binary Tree Implementation - Binary Node Class 1 hours 9 DSAF1907-01
19 Binary Tree Traversal In-Order, Post-Order, Pre-Order, Euler Tour 2 hours 9 DSAF1907-02
20 Priority Queues Nave Implementation 1 hours 10 DSAF1907-03
21 Binary Heaps Priority Queues - Efficient Implementation 1 hours 10 DSAF1907-04
22 Complete Binary Tree Definition, Advantages, Pseudocode 1 hours 10 DSAF1907-05
23 Disjoint Sets Merging Two Lists, Nave Implementation 1 hours 11 DSAF1908-01
24 Forests Disjoint Sets - Union By Rank 2 hours 11 DSAF1908-02
25 Hash Tables Log Processing, Addressing 1 hours 12 DSAF1909-01
26 Hash Functions Map, Chaining, Set 2 hours 12 DSAF1909-02
27 Binary Search Tree BST via Arrays, Link List and Hash Tables 1 hours 13 DSAF1910-01
28 BST Binary Search Tree - Basic Functions 1 hours 13 DSAF1910-02
29 Graph Theory Graph Terminology and Applications 1 hours 13 DSAF1911-01
30 Graph ADT Adjacency Matrix, Sparse Matrix 1 hours 14 DSAF1911-02
31 Graph Traversals Breadth & Depth First Traversals 1 hours 14 DSAF1911-03
32 Connectedness Connected Graph Components 1 hours 14 DSAF1911-04
33 Graph Paths Single Source Unweighted Path Lengths 1 hours 15 DSAF1911-05
34 Minimum Spanning Tree Spanning Trees - Definition and Applications 1 hours 15 DSAF1911-06
35 MST Algorithms Prim's Algorithm, Kruskal's Algorithm 1 hours 15 DSAF1911-07
Lessons Name Description Duration Week Slides
1 Introduction to Course Data Structures & Algorithms 1 hours 1 DSAF1701
2 Solve a Challenging Problem Maximum Pairwise Product 2 hours 1 DSAF1702
3 Why Study Algorithms? An Introduction 1 hours 2 DSAF1703
4 Fibonacci Series Algorithm 1 hours 2 DSAF1704
5 Big-O Notation Computing Runtimes 1 hours 2 DSAF1705
6 Basic Data Structure Arrays, Multi-Dimensional Arrays 1 hours 3 DSAF1706
7 Linked List Singly Linked List & Doubly Linked List 2 hours 3 DSAF1707
8 Stacks Implementation & Applications 1 hours 4 DSAF1708
9 Stack Application Reverse Polish Notation 2 hours 5 DSAF1709
10 Queues Implementation & Applications 3 hours 6 DSAF1710
11 Trees Terminology & Applications 1 hours 7 DSAF1711
12 Tree Traversal Breadth-First & Depth-First Traversals 2 hours 7 DSAF1712
13 Binary Trees In-Order, Pre-Order & Post-Order Traversals 1 hours 8 DSAF1713
14 Priority Queues Naive implementation 2 hours 8 DSAF1714
15 Binary Heaps Priority Queues 1 hours 9 DSAF1715
16 Complete Binary Trees How to keep a tree shallow? 2 hours 9 DSAF1716
17 Disjoint Sets Naive Implementation 1 hours 10 DSAF1717
18 Disjoint Sets Efficient Implementation - Forest 2 hours 10 DSAF1718
19 Hash Tables Introduction 1 hours 11 DSAF1719
20 Hash Tables Hash Functions 2 hours 11 DSAF1720
21 Binary Search Trees Introduction 1 hours 12 DSAF1721
22 Binary Search Trees Basic Operations 2 hours 12 DSAF1722
23 Decomposition of Graphs Representing and Exploring Graphs 1 hours 13 DSAF1723
24 Decomposition of Graphs Connectivity 2 hours 13 DSAF1724
25 Directed Acyclic Graph Topological Sorting 1 hours 14 DSAF1725
26 Directed Graph Strongly Connected Components 2 hours 14 DSAF1726
27 Paths in Graph Most Direct Route - BFS 1 hours 15 DSAF1727
28 Paths in Graph Fastest Route - Dijkstra Algorithm 1 hours 15 DSAF1728
29 Minimum Spanning Tree Kruskal & Prim Algorithms 1 hours 15 DSAF1729
Lessons Name Description Duration Week Slides
1 Introduction to Data Structures Memory Allocation, Linked Allocation, 1 hours 1 DSAF1601
2 Lists Implementation & Memory Requirements 2 hours 1 DSAF1602
3 Linked List Structure, Operations, Implementation 3 hours 2 DSAF1603
4 Stack Stack Implementation via Linked List & Arrays 1 hours 3 DSAF1604
5 Stack Application: Parsing XHTML Parsing XHTML using Stack 2 hours 3 DSAF1605
6 Stack Application: Infix to Postfix Infix, Postfix, Prefix Infix to Postfix Algorithm 1 hours 4 DSAF1606
7 Stack Application: Reverse Polish Notation Reverse Polish Notation Solution Algorithm 2 hours 4 DSAF1607
8 Queues Queue Implementation via Linked List & Arrays 1 hours 5 DSAF1608
9 Deque Abstract Deque, STL, Stepping though Deques, Iterators 2 hours 5 DSAF1609
10 The Tree Data Structure Tree Terminology, Tree Example: XHTML 1 hours 6 DSAF1610
11 Abstract Trees Tree Implementation 2 hours 6 DSAF1611
12 Tree Traversals Breadth First Search, Depth First Search 1 hours 7 DSAF1612
13 Binary Trees InOrder, PreOrder, PostOrder, Level Order, Euler Tour 1 hours 7 DSAF1613
14 Complete Binary Tree Recursive Algorithm, Finding Children, Finding Parent 1 hours 7 DSAF1614
15 N-ary Trees Ternary Trees, Quaternary Trees, TRIE 1 hours 8 DSAF1615
16 Balanced Trees Height Balancing, Null-Path-Length & Weight Balancing 2 hours 8 DSAF1616
17 Binary Search Trees BST Examples, BST Implementation, Finding Kth Object 1 hours 9 DSAF1617
18 AVL Trees AVL Trees, Height of an AVL Tree, Maintaining Balance 2 hours 9 DSAF1618
19 Graph Theory Undirected & Directed Graphs, Path, Weighted Graph 1 hours 10 DSAF1619
20 Graph Data Structures Adjacency Matrix, Sparse Matrix 2 hours 10 DSAF1620
21 Graph Traversals Breadth First Traversal, Depth First Traversal 1 hours 11 DSAF1621
22 Connectedness Determining Connections, Connected Components 1 hours 11 DSAF1622
23 Single Source Un-weighted Path Length Determine Distances of all nodes from a single node 1 hours 11 DSAF1623
24 Identifying Bipartite Graph Bipartite Graph, Algorithm to find Bipartite Graphs 1 hours 12 DSAF1624
25 Minimum Spanning Tree Minimum Spanning Trees and Its Applications 2 hours 12 DSAF1625
26 Prims Algorithm Prims Algorithms Strategy and Execution 1 hours 13 DSAF1626
27 Kruskals Algorithm Kruskals Algorithm for Minimum Spanning Tree 2 hours 13 DSAF1627
28 Single Source Shortest Path Graph Application 1 hours 14 DSAF1628
29 Dijkstra's Algorithm Shortest Path Algorithm 2 hours 14 DSAF1629
30 Topological Sort Scheduling 2 hours 15 DSAF1630
31 Graph Evolution Graphs - Past, Present and Future 1 hours 15 DSAF1631
Lessons Name Description Duration Week Slides
1 Introduction to Data Structures Memory Allocation, Linked Allocation 1 hours 1 DSAF1501
2 Lists Implementation & Memory Requirements 2 hours 1 DSAF1502
3 Linked List Structure, Operations, Implementation 1 hours 2 DSAF1503
4 Stack Implementation using Link List and Arrays 2 hours 2 DSAF1504
5 Stack Application - I Parsing XHTML 1 hours 3 DSAF1505
6 Stack Application - II Infix to Postfix - RPN 1 hours 3 DSAF1506
7 Stack Application - III Reverse Polish Notation 1 hours 3 DSAF1507
8 Queues Implementation using Link List and Arrays 3 hours 4 DSAF1508
9 Tree Data Structure Tree Terminologies and Examples 1 hours 5 DSAF1509
10 Abstract Tree General Tree - Implementation 2 hours 5 DSAF1510
11 Tree Traversals Breadth First, Depth First, Back- Tracking 1 hours 6 DSAF1511
12 Binary Trees Implementation of Binary Node Class, Expression Trees 2 hours 6 DSAF1512
13 Complete Binary Trees Tree Height, Node, Children and Parents 1 hours 7 DSAF1513
14 Binary Search Trees BST Implementation, Finding Kth Object 2 hours 7 DSAF1514
15 Graph Theory Graph Terminologies and Examples 1 hours 8 DSAF1515
16 Graph Data Structure Adjacency Matrix, Sparse Matrix, Adjacency List 2 hours 8 DSAF1516
17 Graph Traversals Breadth First, Depth First, Traversal Applications 3 hours 9 DSAF1517
18 Connectedness Determining Connections, Connected Components 3 hours 10 DSAF1518
19 Path Lengths Single Source Unweighted Path Lengths 3 hours 11 DSAF1519
20 Bipartite Graph Identifying Bipartite Graphs 3 hours 12 DSAF1520
21 Minimum Spanning Tree Spanning Trees on Weighted Graphs, Spanning Forests 3 hours 13 DSAF1521
22 Prims Algorithm To find Minimum Spanning Tree 3 hours 14 DSAF1522
23 Kruskals Algorithm To find Minimum Spanning Tree 3 hours 15 DSAF1523
Lessons Name Description Duration Week Slides
1 Algorithm Analysis Big-O Notation 3 hours 1 DSF1401
2 Abstract Data Type ADT Representation 3 hours 2 DSF1402
3 Arrays Polynomial, Sparse Matrix 3 hours 3 DSF1403
4 Linked List Implementation 3 hours 4 DSF1404
5 Circular and Doubly Link List List ADT Operation 3 hours 5 DSF1405
6 Stack Tower of Hanoi 3 hours 6 DSF1406
7 Infix to Postfix Stack Application 3 hours 7 DSF1407
8 Queues Job Scheduling, Circular Queues 3 hours 8 DSF1408
9 Trees Implementation, Traversals 6 hours 9,10 DSF1409
10 Binary Tree In Order, Post Order, Euler Tour 3 hours 11 DSF1410
11 Binary Search Trees AVL Trees, Multi-Way Search Trees 6 hours 12,13 DSF1411
12 Graph Terminology, Implementation, Traversals 3 hours 14 DSF1412
13 Dijkstra's Algorithm and MST Minimum Spanning Tree 3 hours 15 DSF1413