Lahore University of Management Sciences
CS 202 Data Structures
(Cross-listed as EE 202)
Spring 2015
Instructor
Class Timings
Room No.
Office Hours
Email
Telephone
Teaching Assistants (TAs)
TA Office Hours
Course URL
Dr. Ihsan Ayyub Qazi
Tue/Thu 5:00pm - 6:15pm
SBASSE 9-114A, Computer Science Department, LUMS
TBA
ihsan.qazi@lums.edu.pk
+92 42 3560 8368
TBA
TBA
LMS (https://lms.lums.edu.pk)
Course Basics
Credit Hours
Lecture(s)
Tutorial (per week)
3 credit hours
2 Per Week
1 Per Week
Course Distribution
Core
Elective
Open for Student Category
Close for Student Category
CS Majors, EE Majors, and CS Minors
All
All
None
Duration
Duration
75 mins
60 mins
COURSE DESCRIPTION
Data structures are essential building blocks for designing efficient algorithms. Thus, they play a central role in computer science
and are important in many areas of electrical engineering, computational biology, computational finance, etc. They are used in a
variety of applications today including web search (e.g., Google, Bing), social networking (e.g., Facebook, Twitter), embedded
systems (e.g., cell phones, robots), and DNA analysis. This course will introduce the fundamentals of data structures and shall
provide a thorough understanding of systematic ways for organizing data in a computer system. In addition to introducing a variety
of data structures and algorithms, this course will provide exposure to analytical tools for comparing data structures in terms of
their time and space complexities. Moreover, students will appreciate that the right programming structures, abstractions and
algorithms are necessary for improving the efficiency and complexity of computer programs.
COURSE PREREQUISITE
CS 200 Introduction to Programming
COURSE OBJECTIVES
To understand the design of fundamental data structures as well as algorithms that operate on them
To introduce tools for analyzing the time and space complexity of data structures
To provide rigorous hands-on experience with implementing different data structures in a programming language
Learning Outcomes
Students
Students
Students
Students
will
will
will
will
become aware of several commonly used data structures in real-world applications
understand the fundamental design choices made in data structures and their reasoning
be able to compare the time and space efficiency of different data structures
be able to write programs to efficiently manipulate, store, and retrieve data
Grading Breakup and Policy
Programming Assignment(s) + Homeworks: 30%
Quiz(s): 20%
Midterm Examination: 20%
Final Examination: 30%
Lahore University of Management Sciences
Examination Detail
Yes/No: Yes
Duration: 3 hours
Midterm
Preferred Date: TBA
Exam
Exam Specifications: TBA
Yes/No: Yes
Duration: 3 hours
Final Exam
Exam Specifications: TBA
Textbook(s)/Supplementary Readings
Required Textbooks
(GTM) Data Structures and Algorithms in C++ by Michael T. Goodrich, Roberto Tamassia, and David Mount (2nd Edition)
(Weiss) Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss (2nd Edition)
Session
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Topics
Overview: Data Structures, Abstract Data Types and Applications
Analysis Tools: Experimental Analysis, Asymptotic Notation
Arrays, Lists (Singly Linked List)
Lists (Doubly Linked List), Stacks
Stacks, Queues
Trees: Foundations, Tree Traversals
Trees: Tree Traversals, Binary Trees
Binary Trees: Analysis, Applications
Binary Search Trees (BST): Basics, BST Analysis
Balanced Binary Trees: AVL Trees
Balanced Binary Trees: AVL Trees, Red-Black Trees (optional)
Hash Tables: Hashing Functions
Hash Tables: Chaining, Open Addressing
Midterm Exam
Priority Queues: Foundations, Binary Heaps
Heaps: Binary Heaps, HeapSort
Sorting: Insertion Sort, Selection Sort, Mergesort
Sorting: Quicksort, Bucket-Sort, Radix-Sort [optional]
Data Compression: Applications, Huffman Coding
Tries: Standard, Compressed, Suffix
Graphs: Basics, Data Structures for Graphs
Graph Traversals: Depth First Search, Breadth First Search
Weighted Graphs: Minimum Spanning Trees, Topological Sort
Weighted Graphs: Directed Graphs, Connected Components
Shortest-Path Algorithms: Dijkstras Algorithm
Network Flow Problem
Advanced DS: Distributed Hash Tables
Advanced DS: Bloom Filters + Review
Recommended Readings
(GTM) Chapters 4.1-4.2 + (Weiss) Chapter 6
(GTM) Chapters 3.1-3.4 + (Weiss) Chapters 16
Above + (GTM) Chapters 5.1 + (Weiss) Chapter 17, 16
(GTM) Chapters 5.1-5.3 + (Weiss) Chapter 16
(GTM) Chapters 7.1, 7.2 + (Weiss) Chapter 18.1
Above + (GTM) Chapters 7.3 + (Weiss) Chapter 18.4
(GTM) Chapters 7.3 + (Weiss) Chapter 18.2, 18.3
(GTM) Chapters 10.1 + (Weiss) Chapter 19.1-19.3
(GTM) Chapters 10.2 + (Weiss) Chapter 19.4
(GTM) Chapters 10.5 + (Weiss) Chapter 19.4, 19.5
(GTM) Chapters 9.2 + (Weiss) Chapter 20.1, 20.2
(GTM) Chapters 9.2 + (Weiss) Chapter 20.3
(GTM)
(GTM)
(GTM)
(GTM)
(GTM)
(GTM)
(GTM)
(GTM)
(GTM)
(GTM)
(GTM)
Notes
Notes
Notes
Chapters
Chapters
Chapters
Chapters
Chapters
Chapters
Chapters
Chapters
Chapters
Chapters
Chapters
8.1-8.3 + (Weiss) Chapter 21.1
8.3 + (Weiss) Chapter 21.1, 21.2
11.1 + (Weiss) Chapter 9.1-9.5
11.2, 11.3 + (Weiss) Chapter 9.6-9.8
12.4 + (Weiss) Chapter 13.1 + Notes
12.5
13.1, 13.2 + (Weiss) Chapter 15.1
13.3 + (Weiss) Chapter 15.2
13.6 + (Weiss) Chapter 15.5
13.4, 13.5 + (Weiss) Chapter 15.5
13.5 + (Weiss) Chapter 15.3
