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: computatational 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/assignments
2011.02.21/ 2011.02.22 Introduction to Algorithms and Data Organization
  • course policy announced on 02/21/2011
  • homework 1 announced on 02/23/2011
  • taught in class:
    • Section 1.1
    • Section 1.3 except Subsection 1.3.2
  • reading assignments:
    • Section 1.2
    • Subsection 1.3.2
2011.02.28/ 2011.03.01 no class because of Peace Memorial Day,
instructor office hour from 2011.03.01 14:20 to 17:20
2011.03.07/ 2011.03.08 Basics/Arrays
  • taught in class:
    • Sections 1.4, 1.5, 2.1
  • reading assignments:
    • Examples 1.20, 1.21
    • Subsection 2.2.1
  • suggested reading:
    • Section 1.6
2011.03.14/ 2011.03.15 Arrays and Stacks
  • homework 1 due on 03/15/2011
  • homework 2 announced on 03/16/2011
  • taught in class:
    • Sections 2.2, 2.4 (Sparse Polynomial Adding), 2.5
    • class 01: Subsection 2.7.3 (to be explained again next time)
    • class 02: Section 3.1
  • reading assignments:
    • Sections 2.3, 2.4 (Other Parts), 2.6
    • Subsections 2.7.1, 2.7.2
2011.03.21/ 2011.03.22 Arrays (String) and Stacks
  • taught in class:
    • Subsection 2.7.3 (StringMatchDemo.jar), Section 3.2, beginning of Section 3.6
    • class 01: Section 3.1
  • reading assignments:
    • Stack with Fixed C Array (Part of Section 3.1)
2011.03.28/ 2011.03.29 Stacks/Queues and Linked Lists
  • homework 2 due on 03/29/2011
  • homework 3 announced on 03/31/2011
  • taught in class:
    • Sections 3.3, 3.5, 3.6, 4.1
  • reading assignments:
    • Circular Queue with Fixed C Array (Part of Section 3.3), Sections 3.4, 3.7, 4.2
2011.04.04/ 2011.04.05 no class because of Children Day and Tomb-Sweeping Festival
2011.04.11/ 2011.04.12 Lists
  • homework 3 due on 04/12/2011
  • homework 4 announced on 04/13/2011
  • taught in class:
    • Sections 4.3, 4.4 (selected parts), 4.6, 4.8
    • Subsection 4.7.1
  • reading assignments:
    • Sections 4.4 (other parts), 4.5
    • Subsection 4.7.2, 4.7.3, 4.7.4
2011.04.18/ 2011.04.19 Trees
  • taught in class:
    • Sections 5.1, 5.3 (beginning)
    • Subsection 5.2.2, 5.3.1, 5.3.2, 5.3.3
  • reading assignments:
    • Subsection 5.2.1
2011.04.25/ 2011.04.26 Trees Continued
  • taught in class:
    • midterm exam done on 2011.04.24 Sunday from 3pm to 5:45pm and discussed in class
    • Section 5.5, 5.6 (very beginning)
    • Subsection 5.3.4, 5.3.5, 5.3.6
  • reading assignments:
    • Section 5.4
    • Subsection 5.5.3
2011.05.02/ 2011.05.03 Trees Continued Again
  • homework 4 due on 05/03/2011
  • homework 5 announced on 05/04/2011
  • taught in class:
    • Sections 5.6, 5.7 (except Subsection 5.7.5), 5.8
    • trees and Balance Puzzle
  • reading assignments:
    • Sections 5.9
    • Subsection 5.7.5
2011.05.09/ 2011.05.10 Sorting
  • class 01 notes: sort
  • class 02 notes: sort
  • midterm solution announced on 05/09/2011
  • taught in class:
    • Section 7.2, 7.5 (parts), 7.6 and Selection Sort (recall from Chapter 1), the deprecated Bubble Sort, Tournament Sort with Winner Tree, beginning of Section 7.3 (class 02)
  • reading assignments:
    • Section 7.1
2011.05.16/ 2011.05.17 More on Sorting
  • class 01 slides: sort
  • class 02 slides: sort
  • taught in class:
    • Section 7.3, 7.4, 7.5; a slight exposure to Section 7.10; Counting Sort (class 01)
  • reading assignments:
    • Subsection 7.10.1
2011.05.23/ 2011.05.24 Sorting/Hashing
  • notes (including some from last week): sort/hash
  • homework 5 due on 05/24/2011
  • homework 6 announced on 05/27/2011
  • taught in class:
    • Section 7.6, 7.7, 7.9, 8.1
    • Subsection 8.2.1, 8.2.3
  • reading assignments:
    • Subsection 8.2.2
2011.05.30/ 2011.05.31 Hashing/AVL Trees
  • taught in class:
    • Section 10.2
    • Subsection 8.3.1, 8.3.2
  • reading assignments:
    • Subsection 8.3.3
2011.06.06/ 2011.06.07 no class because of Dragon Boat Festival,
instructor office hour from 2011.06.07 14:20 to 17:20
2011.06.13/ 2011.06.14 Priority Queue/Final Words
  • homework 6 due on 06/17/2011
  • taught in class:
    • Section 9.3
    • review and beyond
  • reading assignments:
    • Subsection 9.3.6
2011.06.20/ 2011.06.21 no classes on 2011.06.20/2011.06.21

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