Hsuan-Tien Lin > Courses > Data Structures and Algorithms, Spring 2013

Hsuan-Tien Lin

Home | MOOCs | AIsk | Courses | Research Group | Awards | Publications | Presentations | Programs/Data

Data Structures and Algorithms

Course Description

Good program comes from appropriately using the "resources" on the computer. There are two types of key resources: computational units (CPU, FPU, etc.) and storage units (memory, disk, etc., along with channels and networks). Data Structures and Algorithms discuss how to use those two types of resources suitably and effectively. Traditionally, data structures aim at the use of storage units, while algorithms aim at the use of computational units. But the two aims are actually inseparable: succinct data structures require coupling with corresponding algorithms; efficient algorithms require coupling with corresponding data structures. The course, designed as a required course for NTU CSIE students in the freshman year, introduces basic data structures and their corresponding algorithms. We will move from the concrete side of implementing basic data structures to the abstract side of analyzing the complexity of storage and computation.

Course Information

Instructor: Hsuan-Tien Lin (htlin AT csie DOT ntu DOT edu DOT tw)
office hour: after classes, R104; or by appointment, R314
TAs: Tse-Ju Lin, Han-Jay Yang, Ya-Hsuan Chang, Wei-Yuan Shen, Kuan-Hao Huang (dsata AT csie DOT ntu DOT edu DOT tw)
TA office hours: in the CSIE basement
- Tse-Ju: Tuesday 13:20--14:10 (Before the class!) (Start 3/5)
- Han-Jay: Wednesday 19:00--20:00 (Start 3/6)
Time: (Class 01) Tuesday 14:20--15:10; Thursdays 10:20--12:10
Room: R104
CEIBA: https://ceiba.ntu.edu.tw/1012dsa
Textbook: Data Structures and Algorithms in C++, 2nd Edition by Goodrich, Tamassia and Mount

Announcements

homework 6 announced on 05/24, due on 06/06
final project announced on 05/15, due on 06/27
homework 5 announced on 05/03, due on 05/16
homework 4 announced on 04/09, due on 05/02
homework 3 announced on 03/22, due on 04/09
homework 2 announced on 03/07, due on 03/21
homework 1 announced on 02/22, due on 03/07
draft slides/notes will often be available before the class
course policy announced on 02/20 and explained in class on 02/19

Course Plan

date	syllabus	plan	documents and reading assignments
02/19,02/21	class introduction/DSA/C++ basics (Ch01)	homework 1 announced	notes on course policy slides about course introduction slides about data structure and algorithm slides about C++ reading assignments: Sections 1.1 to 1.5 of the textbook
02/26,02/28	C++ basics (Ch01); no class on 02/28 because of Peace Memorial Day		slides about C++ reading assignments: none, for you to catch up with the assignments last week
03/05,03/07	array/linked list (Ch03)	homework 1 due; homework 2 announced	slides about C++ slides about Array, and more notes on Linked List reading assignments: All Chapter 1 (if you haven't done so), All Chapter 3
03/12,03/14	analysis tools (Ch04), stack		slides about Analysis Tools, more slides about Stack reading assignments: All Chapter 4, Sections 5.1 and 5.2
03/19,03/21	stack/queue/dequeue (Ch05), container (Ch06)	homework 2 due; homework 3 announced	slides about Stack/Queue slides about Deque notes about Containers (reusing notes from 2012 class) reading assignments: All Chapter 5, Section 6.1
03/26,03/28	list/iterator (Ch06), tree (Ch07)		notes about Containers (reusing notes from 2012 class) notes about Trees (reusing notes from 2012 class) reading assignments: All Chapter 6, Section 7.1 and 7.3
04/02,04/04	tree (Ch07); no class on 04/04 because of Spring Break	homework 3 due; homework 4 announced	notes about Trees (reusing notes from 2012 class) reading assignments: All Chapter 7
04/09,04/11	heap (Ch08)		check midterm of 2011 and midterm of 2012 to help you prepare for your midterm. notes about Heaps (reusing notes from 2012 class) reading assignments: All Chapter 8
04/16,04/18	midterm exam on 04/18: range: Chapters 1-8, except Chapter 2, and all class slides/notes; no class on 04/16 because of Midterm-studying		midterm exam
04/23,04/25	hash table/map (Ch09)		notes about Hash Table (reusing notes from 2012 class) reading assignments: Sections 9.1, 9.2, 9.5
04/30,05/02	hash table/map (Ch09)	homework 4 due; homework 5 announced	notes about Hash Table and more (reusing notes from 2012 class) reading assignments: Sections 9.1, 9.2, 9.5
05/07,05/09	skip list/dictionary (Ch09)	final project announced	notes about Hash Table and Skip List (reusing notes from 2012 class) notes about Binary Search Tree (reusing notes from 2012 class) reading assignments: Sections 9.3, 9.4, 10.1
05/14,05/16	avl tree (Ch10)	homework 5 due	notes about AVL Tree (reusing notes from 2012 class) reading assignments: Sections 10.2
05/21,05/23	avl tree/2-3-4 tree (Ch10)	homework 6 announced	notes about More on AVL Tree (reusing notes from 2012 class) notes about 2-3-4 tree (see next week) reading assignments: Sections 10.2, 10.4
05/28,05/30	2-3-4 tree/red-black tree (Ch10)		notes about 2-3-4 tree and red-black tree (reusing notes from 2012 class) reading assignments: Sections 10.4, 10.5
06/04,06/06	sorting (Ch11)	homework 6 due	slides about sorting notes about non-comparison sorting reading assignments: Sections 11.1, 11.2, 11.3
06/11,06/13	graph (Ch13)		notes about graph reading assignments: Sections 13.1, 13.2, 13.3, 13.4, 13.5 (highly encouraged to read all Chapter 13)
06/18,06/20	no class on 06/18; graph/summary on 06/20	final project report due on 06/27	slides about summary and competition reading assignments: see the ones last week

Last updated at CST 13:07, October 04, 2023
Please feel free to contact me: htlin.email.png