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

Announcements

Course Plan

datesyllabusteaching plandocuments and reading assignments
02/21
  • class introduction (supplementary material)
  • C++ basics (selected parts of Chapter 1)
homework 1 announced on 2/23
  • slides: class introduction
  • reading assignment: Chapter 1 (except references, class friends, nested classes and standard template library, we will attend to those in the next class, you are expected to read and learn all the other stuff)
02/28no class because of Peace Memorial Day
03/06
  • C++ basics (selected parts of Chapter 1)
  • DSA (supplementary material)
homework 1 due on 3/7
  • slides: more C++
  • slides: DSA
  • reading assignments: all Chapter 1
  • recommended (but not required) reading: Chapter 2
03/13
  • DSA (supplementary material)
  • Array (selected parts of Section 3.1 and supplementary material)
homework 2 announced on 3/14
  • slides: DSA
  • slides: array
  • reading assignments: all Section 3.1
03/20
  • list (selected parts of Sections 3.2, 3.3, 3.4)
  • recursion (selected parts of Section 3.5)
  • analysis tools (selected parts of Subsection 4.2.1, 4.2.2, 4.2.3
  • notes: list
  • notes: recursion
  • slides: analysis
  • reading assignments: all Sections 3.2, 3.3, 3.4, 3.5; Section 4.1, Subsections 4.2.1, 4.2.2, 4.2.3
03/27
  • analysis tools (selected parts of Subsection 4.2.4, 4.2.5)
  • stack/queue/deque (selected parts of Chapter 5 and supplementary material)
homework 2 due on 3/28; homework 3 announced
04/03no class because of Spring Break
04/10
  • list/iterator (selected parts of Chapter 6)
homework 3 due on 4/13; homework 4 announced
  • notes: container
  • reading assignments: all Chapter 6
04/17
  • tree (selected parts of Sections 7.1, 7.3 [7.3 until 7.3.3 and 7.3.8])
homework 4 due on 4/20
  • notes: tree
  • reading assignments: Section 7.1, Section 7.3 (until 7.3.3)
04/24midterm exam (Chapters 1 to 6, including all supplmentary materials taught in class, excluding Chapter 2)
05/01tree/heap homework 5 announced
  • notes: tree/heap
  • reading assignments: Chapter 7 (except the assignments last time), Section 8.3
05/08priority queue/hash table
  • notes: hash table
  • reading assignments: all Chapter 8 (except the assignments last time), Sections 9.1 and 9.2
05/15hash table/skip listhomework 5 due
05/22avl tree/2-3-4 treehomework 6 announced
05/292-3-4 tree/red-black tree
06/05sortinghomework 6 due
  • slides: sorting
  • reading assignments: Sections 10.3, 11.1, 11.2
06/12no class because of heavy rain
06/19sorting/string/final wordsfinal project competition end (6/19); final project due (6/29)
Last updated at CST 13:07, October 04, 2023
Please feel free to contact me: htlin.email.png 		Valid HTML 4.0!