Lahore University of Management Sciences CS 202 / EE 202 Data Structures Fall 2016-17 Instructor Room No. Office Hours Email Telephone Secretary/TA TA Office Hours Course URL (if any)
Shafay Shamail 9-113A, CS Department, SBASSE Building OSPR, Academic Block 11:00 AM – 12:00 PM Tue Thu
[email protected] 8187 Muhammad Faisal / TBA TBA lms.lums.edu.pk
COURSE BASICS Credit Hours Class Room Class Timings Lecture(s) Recitation/Lab (per week) Tutorial (per week)
3 TBA 9:30 AM – 10:45 AM Tue Thu Nbr of Lec(s) Per Week 2 Nbr of Lec(s) Per Week None Nbr of Lec(s) Per Week As per Need
COURSE DISTRIBUTION Core Elective Open for Student Category Close for Student Category
CS Majors, EE Majors, CS Minors All All None
Duration Duration Duration
75 Minutes
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(S) CS 200 Introduction to Programming
Lahore University of Management Sciences UNDERGRADUATE PROGRAM LEARNING GOALS & OBJECTIVES (PLO)
COURSE LEARNING OBJECTIVES (CLO) 1. To understand the design of fundamental data structures as well as algorithms that operate on them CLO 1 2. To introduce tools for analyzing the time and space complexity of data structures
CLO 2 3. To provide rigorous ‘hands-on’ experience with implementing different data structures in a programming CLO 3 language LEARNING OUTCOMES (LO) 1. Students will become aware of several commonly used data structures in real-world applications LO 1 2. Students will understand the fundamental design choices made in data structures and their reasoning LO 2 3. Students will be able to compare the time and space efficiency of different data structures
LO 3 4. Students will be able to write programs to efficiently manipulate, store, and retrieve data LO 4 PROGRAM LEARNING GOALS AND OBJECTIVES
COURSE LEARNING OBJECTIVES
GRADING BREAKUP AND POLICY Assignment(s) + Home Work: Quiz(s) + Class Participation: Midterm Examination: Final Examination:
30% 20% 20% 30%
EXAMINATION DETAIL Yes/No: Midterm Duration: Exam Preferred Date: Exam Specifications: Yes/No: Duration: Final Exam Exam Specifications:
Yes 75 Minutes (In class) Week 7 Course covered till mid term Yes 3 hours Complete Course
COURSE ASSESSMENT ITEM
Textbook(s)/Supplementary Readings Recommended 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) • (YMT) Data Structures Using C AND C++, Langsam Yedidyah , Augenstein J Moshe ,Tenenbaum M Aaron, (2nd Edition)
Lahore University of Management Sciences 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, Applications) Analysis Tools, Asymptotic Notation Arrays, Lists (Singly, Doubly, Circular Linked Lists) Lists (continued), Stacks Stacks, Queues Introduction to Trees, Tree Traversals Tree Traversals (continued), Binary Trees Binary Trees (continued) Binary Search Trees (BST), BST Analysis Huffman Coding AVL Trees B Trees, Multi-way Trees Hashing/Hash Tables Midterm Exam Priority Queues, Binary Heaps Binary Heaps, HeapSort Sorting (Insertion Sort, Mergesort) Sorting (Quicksort, Radix-Sort [optional], Bucket-Sort [optional]) Data Compression (Huffman Coding) Tries (Standard, Compressed, Suffix) Graphs, Data Structures for Graphs Graph Traversals (Depth First Search, Breadth First Search) Directed Graphs, Topological Sort Shortest-Path Algorithms (including Dijkstra's Algorithm) Shortest-Path Algorithms, Minimum Spanning Trees Network Flow Problems Advanced DS: Distributed Hash Tables & Bloom Filters Review
Recommended Readings (YMT) Chapter 1.1 (GTM) Chapters 4.1-4.2 + (Weiss) Chapters 1.1, 1.2,2 (GTM) Chapters 3.1-3.4 + (Weiss) Chapters 3.2, 3.5 Above + (GTM) Chapters 5.1 + (Weiss) Chapter 3.6 (GTM) Chapters 5.1-5.3 + (Weiss) Chapter 3.7 (GTM) Chapters 7.1, 7.2 + (Weiss) Chapter 4.1, 4.6 Above + (GTM) Chapters 7.3 + (Weiss) Chapter 4.2 (GTM) Chapters 7.3 + (Weiss) Chapter 4.2 (GTM) Chapters 10.1 + (Weiss) Chapter 4.3 (GTM) Chapters 10.2 + (Weiss) Chapter 4.4 Above + (GTM) Chapters 10.5 + (Weiss) Chapter 12.2 (GTM) Chapters 9.2 + (Weiss) Chapter 5.1-5.3 (GTM) Chapters 9.2 + (Weiss) Chapter 5.4-5.6 (GTM) Chapters 8.1-8.3 + (Weiss) Chapter 6.1, 6.2 (GTM) Chapters 8.3 + (Weiss) Chapter 6.3, 7.5 (GTM) Chapters 11.1 + (Weiss) Chapter 7.2, 7.6 (GTM) Chapters 11.2, 11.3 + (Weiss) Chapter 7.7 (GTM) Chapters 12.4 + (Weiss) Chapter 10.1.2+Notes (GTM) Chapters 12.5 + (Weiss) Chapter 10.1.2 (GTM) Chapters 13.1, 13.2 + (Weiss) Chapter 9.1 (GTM) Chapters 13.3 + (Weiss) Chapter 9.3.1, 9.6 (GTM) Chapters 13.4 + (Weiss) Chapter 9.2 (GTM) Chapters 13.5 + (Weiss) Chapter 9.3 (GTM) Chapters 13.6 + (Weiss) Chapter 9.4, 9.5 Notes Notes Notes
