Hsuan-Tien Lin

Home | MOOCs | 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

Announcements

Course Plan

datesyllabusplandocuments and reading assignments
02/19,02/21 class introduction/DSA/C++ basics (Ch01) homework 1 announced
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
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)
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
04/23,04/25hash table/map (Ch09)
  • notes about Hash Table (reusing notes from 2012 class)
  • reading assignments: Sections 9.1, 9.2, 9.5
04/30,05/02hash 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/09skip list/dictionary (Ch09) final project announced
05/14,05/16avl tree (Ch10) homework 5 due
  • notes about AVL Tree (reusing notes from 2012 class)
  • reading assignments: Sections 10.2
05/21,05/23avl 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/302-3-4 tree/red-black tree (Ch10)
06/04,06/06sorting (Ch11) homework 6 due
06/11,06/13graph (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/20no class on 06/18; graph/summary on 06/20 final project report due on 06/27

Last updated at CST 01:19, February 17, 2015
Please feel free to contact me: htlin.email.png
Valid HTML 4.0!