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

datesyllabusplandocuments and reading assignments
02/17,02/18 class/DSA introduction
02/24,02/25 C++ introduction homework 1 announced
03/03,03/04 array
  • notes on array
  • reading assignment: Section 3.1
  • recommended previewing: Section 2.3, Chapter 4
03/10,03/11 analysis tools homework 1 due; homework 2 announced
  • notes on extendable array
  • notes on analysis tools
  • reading assignment: Section 2.3, Section 4.2.1, 4.2.2, 4.2.3, 4.3
  • recommended previewing: Chapter 4, Section 3.2, Section 3.3, Seciton 3.4
03/17,03/18 sparse array
  • notes on analysis tools: check the pages last week
  • notes on sparse array
  • reading assignment: Chapter 4
  • recommended previewing: Chapter 3, Chapter 6
03/24,03/25 linked list/stack
  • slides on linked list/stack
  • reading assignment: Chapter 3, Section 5.1
  • recommended previewing: Chapter 5, Chapter 6
03/31,04/01 queue/dequeue homework 2 due; homework 3 announced
  • slides on queue/dequeue
  • reading assignment: Chapter 5
  • recommended previewing: Chapter 6, Section 7.1
04/07,04/08 container/tree
  • notes on container (reusing notes in earlier years; extendable array actually covered much earlier this year)
  • notes on tree (reusing notes from earlier years)
  • reading assignment: Chapter 6, Section 7.1
04/14,04/15 midterm exam from 2pm to 4pm of 04/13; no classes and good luck with your other finals final project announced
  • midterm range: all notes/handouts/class discussions; Chapter 1, Section 2.3, Chapter 3, Chapter 4, Chapter 5, Chapter 6, Section 7.1
04/21,04/22 tree homework 3 due; homework 4 announced
  • notes on tree (reusing notes from earlier years)
  • reading assignment: Chapter 7
  • recommended previewing: Chapter 8
04/28,04/29 heap
  • notes on heap (reusing notes from earlier years)
  • reading assignment: Chapter 8
  • recommended previewing: Chapter 9
05/05,05/06 hash homework 4 due; homework 5 announced
  • notes on hash (reusing notes from earlier years)
  • notes on binomial and leftist heaps (reusing notes from earlier years)
  • reading assignment: Sections 9.1, 9.2 (until 9.2.4)
  • recommended previewing: Chapter 9
05/12,05/13 hash/skip list
  • notes on hash and skip list (reusing notes from earlier years)
  • reading assignment: Chapter 9
  • recommended previewing: Chapter 10
05/19,05/20 AVL tree/2-3-4 tree homework 5 due; homework 6 announced
  • notes on AVL and 2-3-4 tree (reusing notes from earlier years)
  • reading assignment: Sections 10.1, 10.2, 10.3
  • recommended previewing: rest of Chapter 10
05/26,05/27 2-3-4-tree/red-black tree
06/02,06/03 no class on 06/02 because of dragon boat festival; sorting homework 6 due
  • notes on sorting (see next week)
  • reading assignment: (see next week)
06/09,06/10 sorting
  • slides on sorting (reusing notes from earlier years)
  • notes on non-comparison sort (reusing notes from earlier years)
  • reading assignment: Chapter 11
06/16,06/17 summary on 06/16 10:30am to 11:30am (two classes together); no class on 06/17 and good luck with your other finals final project due
Last updated at CST 13:07, October 04, 2023
Please feel free to contact me: htlin.email.png 		Valid HTML 4.0!