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

, 11.1, 11.2, 11.3
datesyllabusplandocuments and reading assignments
03/03 class introduction, DSA introduction
03/10 C++ introduction (Chapter 1) and array (Section 3.1) homework 1 announced
03/17 array (Section 3.1) and linked list (Section 3.2)
03/24 linked list (Sections 3.2, 3.3, 3.4), recursion (Section 3.5), analysis tools (Chapter 4) homework 1 due; homework 2 announced
03/31 analysis tools (Chapter 4), stack (Section 5.1)
04/07 stack (Sections 5.1) and queue (Sections 5.2 and 5.3)
04/14 container/iterator (Chapter 6) homework 2 due; homework 3 announced
  • container (notes from past, notes from class, youtube)
  • reading assignments: Chapter 6
04/21 tree (Chapter 7) final project announced
04/28 heap (Chapter 8) homework 4 announced
05/05 binomial heap / hash table (Sections 9.1, 9.2, 9.3) homework 3 due
05/12 hash table (Section 9.2) homework 5 announced
  • hash table (notes from past, notes from class, youtube)
  • reading assignments: Sections 9.1, 9.2, 9.3
05/19 skip list / binary search tree / AVL tree (Sections 9.4, 10.1, 10.2) homework 4 due; homework 6 announced
  • skip list (notes from past, notes from class, youtube)
  • binary search tree / AVL tree (notes from past, notes from class, youtube)
  • reading assignments: Sections 9.4, 10.1
05/26 AVL tree / 2-3-4 tree / red-black tree (Sections 10.2, 10.4, 10.5)
  • AVL tree (notes from past, notes from class, youtube)
  • (2, 3, 4)-tree / red-black tree (notes from past, notes from class, youtube)
  • reading assignments: Sections 10.2, 10.4, 10.5
06/02 (2, 3, 4)-tree / red-black tree (Sections 10.4, 10.5)
  • (2, 3, 4)-tree / red-black tree (notes from past, notes from class [forgot to save, sorry!], youtube)
  • reading assignments: Sections 10.4, 10.5
06/09sorting (Sections 11.1, 11.2, 11.3) and summary homework 5 due; homework 6 due
06/16 no class and good luck with your other finals
06/23 summar vacation begins (really?) final project due

Last updated at CST 13:08, October 04, 2023
Please feel free to contact me: htlin.email.png
Valid HTML 4.0!