Electrical Engineering
 
Welcome Biography Research Teaching Publications Awards
Lab Professional Activities Research Projects Links
 
 

資料結構與程式設計

Data Structures and Programming

Spring 2017

 

Instructor: 顏嗣鈞
E-mail:  hcyen(_at_)ntu.edu.tw

Time:  9:10-12:00 AM, Tuesday

Place: Room BL-113

Office phone: (02) 3366 3581

Office hours: by appointment

TA:  (1)顏玓德 博理館606室 bottlebottle13@gmail.com 

                      (02) 33663700 ext 6606

          (2)謝友恆 博理館603室 scrashedward@gmail.com

                      (02) 33663700 ext 6603


Announcements

  • 期中期末考作業1-4(updated 6/27)及程式1-2(updated 6/27)成績登錄
     同學如果要看期末考卷,請於星期三(6/28)下午4:00 - 5:30 到
    計算機及資訊網路中心220室。
    作業評分有問題請和顏玓德助教連絡; 程式評分有問題,請聯絡謝友恆助教。上述作業及程式詢問由即日起至 6/27(二) 5:00 PM 截止,有問題請務必在6/27前聯絡助教

  • Final Exam Solutions

  • Final Exam will be held on June 20 (Tuesday) 9:10 - 12:00.

  • Sample final exam:  (Spring 2016)  (Spring 2015) (Spring 2014), (Spring 2010), (Spring 2007)  (Fall 2004; Solutions) (Fall 2003 ) (Spring 2003)  (Fall 2000)

  • 期末考範圍: 講義(4c~4g;  5;  6a~6d;  7;  8 )    課本(Chapter 4: pp. 149-157; Chapter 5: pp. 185-203; Chapter 6: pp. 213-225, 229-250; Chapter 7: pp. 261-289, 297-299; Chapter 8: pp. 315-326, 332-334; Chapter 11: pp. 509-513)

  • Instructor's office hours for final exam: 

                      6/16(五)  10:00 ~ 12:00AM,計算機及資訊網路中心220室

     TA's office hours:

        謝友恆: 6/15(四)  2:00 ~ 4:00PM, 博理館 603

        顏玓德: 6/19(一)  3:00 ~ 5:00PM, 博理館 606

     

  • Homework #4: (Solutions)   due June 13.

  • Homework #3: (Solutions)  due May 23.

  • Programming Assignment #2: due 23:59 PM, May 25,  2017.

      Input files: op.txt   tree.txt

  • Midterm Exam (solutions) will be held on April 25 (Tuesday) 9:10 - 12:00.

      期中考範圍: 講義(1.pdf、2.pdf、3.pdf、4a.pdf、4b.pdf,不包括note)

                 課本(Chapter 2: pp. 43-69; Chapter 3: pp. 71-74; 94-111;

                      Chapter 4: pp. 113-149) 

       Instructor's office hours: 

                  4/21(五)  9:30 ~ 11:00AM,計算機及資訊網路中心220室

                  4/24(一)  1:30 ~   3:00 PM,計算機及資訊網路中心220室

       TA's office hours:

        顏玓德: 4/19  3:30 ~ 5:30PM,博理館 606

        謝友恆: 4/20  3:00 ~ 5:00PM, 博理館 603

     Input file: request.txt

     繳交說明

 


Class Notes:

 

Topics

    PRELIMINARIES Introduction.  Asymptotic Notations. Algorithm Analysis 1.ppt

2.pdf

 
  LISTS, STACKS, and QUEUES

Abstract data types. Stacks. Queues. Lists. List operations. List representations. List traversals. Doubly linked lists.

3.pdf (Note)

 

  TREES:

Tree operations. Tree representations. Tree traversals. Threaded trees. Binary trees. AVL trees. 2-3-4 trees. B-trees. Red-black trees. Binomial trees. Splay trees, and more.

4a.pdf

4b.pdf

4c.pdf

4e.pdf

4f.pdf

4g.pdf

vis1, vis2

  HASHING

Chaining. Open addressing. Collision handling.

5.pdf 

  PRIORITY QUEUES

Binary heaps. Binomial heaps. Fibonacci heaps. Min-max heaps. Leftist heaps. Skew heaps.

6a.pdf

6b.pdf

6c.pdf

6d.pdf

6e.pdf

  AMORTIZED ANALYSIS   4d.pdf
  SORTING

Insertion sort. Selection sort. Quicksort. Heapsort. Mergesort. Shellsort. Lower bound of sorting.

7.ppt
DISJOINT SETS

Set operations. Set representations. Union-find. Path compression.

8.pdf
  GRAPHS

Graph operations. Graph representations. Basic graph algorithms. Algorithm design techniques 

9.ppt

ADVANCED DATA STRUCTURES Tries.   Skip lists.   Treaps. Top-down splay trees, and more Skip lists

 

 

 

Textbook:

  • Mark Allen Weiss, Data Structures and Algorithm Analysis in C++. (3rd or 4th Ed.)

    Addison-Wesley, 2006/2013


Grading:  

  • Homework/Prog. Assignments: 25-30%

  • Midterm exam: 35-40%

  • Final exam:  35-40% 

 

CHEATING: With the exception of group assignments, the work (including homework, programming assignments, tests) must be the result of your individual effort. This implies that one student should never have in his/her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. Academic dishonesty has no place in a university, in particular, in NTUEE. It wastes our time and yours, and it is unfair to the majority of students. Any form of cheating will automatically result in a failing grade in the course and will be reported to the Dean's office.

.