### CSIE1212: Data Structures and Algorithms 資料結構與演算法

```CSIE1212:
Data Structures and Algorithms

Hsuan-Tien Lin (林軒田)
Jyh-Shing Roger Jang (張智星)
CSIE Dept, National Taiwan University
Warnings Before (Signing for) the Course (1/3)

Goal of NTU DSA class

As good as the best ones in the world
Tentatively, 6 homework sets, midterm exam, final
project

Including writing assignments and time-consuming
programming assignments
 HW1 is to be announced next week

Warning: High expectations  Be prepared to work hard!
2
Warnings Before (Signing for) the Course (2/3)
Will you give me a second chance if I copy homework
from other people? No.
 Could you let me pass because I will be kicked out by the
½ rule? No.
 Will you change my score from F to C? No.

Warning: Strict instructor  Be prepared to follow the rules!
3
Warnings Before (Signing for) the Course (3/3)

We are veterans
HT: Fifth-time teach the course
 Roger: Fourth-time teach the course

But we are ambitious and willing to experiment with
different ways for effective learning.
 How many people will not pass?



Not known yet.
Will your investment get good return (knowledge)?

No guarantees, but we’ll try our best.
Warning: Uncertain outcome  Be prepared to take some risks!
4
Wise Words

5
Some Historical Notes

Around 1997
「計程」有兩學期，上學期教 C，下學期教 C++
 大二上學期教「資料結構」
 大二下學期教「演算法」


Starting 2001




「計程」變成一學期，大一下學期教「物件導向程式設計」

Starting 2010




6
Reasons

 把「資料結構」及「演算法」合成一門課：兩者互相

 把「資料結構與演算法上/下」區分成「資料結構與演


7
Course Descriptions

Goal

Use software to synergize two resources effectively
Computation: CPU, GPU
 Storage: memory, disk, network


A program is…

Algorithms + Data Structures = Programs
8

Instructors

Hsuan-Tien Lin 林軒田
Email: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
 Office: 314


J.-S. Roger Jang 張智星
Email: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
 Skype: roger_jang
 Mobile: 0953-154-045
 Office: 509


Office hours: After class or by appointments
9




CEIBA (for mailing list, etc)
HT: http://ceiba.ntu.edu.tw/1032dsa
 Roger: http://ceiba.ntu.edu.tw/1032dsaByRoger


Course websites:
HT: http://www.csie.ntu.edu.tw/~htlin/course/dsa15spring
 Roger: http://mirlab.org/jang/courses/dsa

10
Textbook and Prerequisites

Textbook: Data Structures and Algorithms in C++, 2nd
Edition by Goodrich, Tamassia and Mount.
assignments
 Learning to read a text book is part of the course
 NTU Library: reserved copy in the shared course material area


Prerequisites
C: required
 C++: preferred

11
To Keep Two Classes Sync’ed
To keep these two DSA classes equivalent (and make it
fair), we will try to keep (almost) everything the same,
including textbook, homework, midterm exam, final
project, grading formula, TAs, schedule, etc.
 So what’s the difference?

HT’s class is in English
 Roger’s class is in Mandarin


So…
You don’t need to switch between these two classes.
 You are welcome to attend any class at any time.

12

Both instructors are strict but friendly, and willing to help...
Will you repeat the previous code/slide? Yes!
 Will you discuss with me after class if I don’t understand? Yes!
 Will you pardon my silly questions? There is no silly questions at
all!

Feel free to ask the instructors and give feedbacks!
13
Both instructors welcome extra enrollment, up to the limit
of the classroom. (Type-3)
 Auditing is also welcome.

Think before you choose to enroll.
If you have chosen to do so, welcome aboard!
14

List of TAs (tentatively):



Email for TAs: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
All the TAs and instructors will receive emails sent to this account.
 It is usually faster than sending to individual.


Office hours for TAs: to be announced.
Very friendly TAs. Be sure to ask them questions!
15
Policy of fairness

How important is fairness?


For monkeys
Our ultimate policy of fairness
Taking any unfair advantages over other class members is not
allowed
 It is everyone’s responsibility to maximize the level of fairness.
 This applies to instructors, TAs, and students.

No cheating!
No lying!
No plagiarism!
16

10% for participation


2% each for in-class or on-forum (FB) questions/asnwering
90%
Homework: 45% or so
 Midterm exam: 20% or so
 Final project: 25% or so

The final grades are based on both scores and rankings
 The instructors reserve the rights to



Determine the way to combine scores and rankings
17
Homework discussions are encouraged, but students should
have their own write-ups alone and understand them fully.
 References (books, notes, Internet) can be consulted, but
not copied from.
 Lending/borrowing homework is strictly prohibited!

Deal? If your classmate wants to borrow homework from you,
what do you say?
18
No individual extension allowed unless for legitimate
 Overdue penalty for homework

90% discount for overdue of 0-12 hours
 80% discount for overdue of 12-24 hours
 …

Four penalty-free late half-days (金牌) per person.
19

Sections related to what we teach
 Sections that are worth reading by yourself


3/6: 3-hour teaching, 6-hour reading/writing after class


Some of the reading material may show up in exams
We cannot teach the whole book, but with reading you can
learning it all.
20
How to Pass the Class?

Golden rules to pass the class
Catch up from day 1
 Have fun (and spend hours) writing programs
 Understand theorems and proofs

21
Can and Cannot

Rules in the classroom
Eating? Fine, but no smells and no noise
 Sleeping? Fine, but no snoring
 Cellphone? Fine, but use silent mode and speak outside

22
Todo List