Introduction to Computer Science


Fall 2011, Room 4263, 9:10~12:00 Thursday
Instructor: Kun-chan Lan
(this course is offered in English) 


    * Know what is "Computer science"?
    * Familiarize yourself with the basic
          o Terminologies
          o Principles
          o Theories
    * Also, a strong hands-on focus
          o Homework
          o Project


    * Data storage
    * Computer architecture
    * Operating system
    * Networking
    * Algorithm
    * Programming language
    * Artificial intelligence

Text Book

    * J. Glenn Brookshear, Computer Science -- An Overview, 11th edition, Addison-Wesley
          o ISBN-10: 0132569035 | ISBN-13: 978-0132569033

Please download and check the team list and the roll call list. If it has any problem, please contact TA.
For 甲班 students, Please come to TA's office to borrow the GPS receiver before 10/1.
The course of this week (10/27) class will be canceled.
Please check your area for term project in team list. If you have any question, please contact TA.  
Please send your presentation slides to TA before 11-17 for midterm project presentation. 
o A 3-5 minute presentation for your navigation algorithm (10%) 
o And one-page, 11-pt-font, double-spaced report that describes/explain/justify your algorithm.
Please in the following teams submit your midterm report to TA (Jensen): 20, 23, 30, 31, 44
Please in the following teams return your GPS devices to TA Henry,
27, 35, 14, 26, 39, 24, 27, 19, 28, 29, 38, 43
Please submit your Irobot code (homework II) to TA (Jensen).
2011-12-29 Time, starting location, destination will be post on the course webpage at 9:00 AM. You have one hour to estimate the travel time based on the given info and then submit your results to TA over email before 10:00 AM (no late submission). No class today.
The question is: 

Estimate the travel time from our department (大學路) to Costco (和緯路三段) by
taking the following route 大學路 -> 勝利路-> 東豐路 -> 公園北路 -> 西門路 -> 和緯路
Please consider speeds with car density (e.g., if car density is low, the speed is maximal road speed) and depart time is 11:00 AM.  

Please submit your algorithm with results to TA (Jensen),
One page report by MS word. 
Final exam is closed book, closed note exam. You can bring one-page A4 size note to the exam. But any electronic device is prohibited (e.g., calculator, iphone, ipad, etc.)
2012-01-16 Student (F24007028, Mr. 梁), please contacts TA ASAP.   
2012-01-17 Student (F24007028, Mr. 梁), since your grade have some problem, please contact TA before Friday. Otherwise, accept the consequences by yourself.  
2012-01-20 Here is final grade [download]  
2012-01-20 TA puts exam paper outside of Prof. office (East Block, Yun-Ping building 309). You can take if you want.   



Prof. Kun-chan Lan
  Office: Room 309 (East Block, Yun-Ping building, Kuang-Fu Campus)
  Office hours: 11-12pm on Monday and Tuesday or by appointment via e-mail
  Email: This email address is being protected from spambots. You need JavaScript enabled to view it.
  TEL: +886 6 2757575 ext 62550




    * Creative project (25%)
    * Home Work Exercise (30%)
    * Exam (45%)
    * Extra credit
          o Class participation and in-class quiz
          o Up to 10%


  • week 1 (9/15) Administration issues 
  • week 2 (9/22) tutorial on GPS and robots (Henry and Jensen)
  • Fundamental
  • week 3 (9/29) Data storage System
  • week 4 (10/6) Hardware
  • week 5 (10/13) Operating System(I)
  • week 6 (10/20) Operating System(II)
  • week 7 (10/27) Networking (I)
  • week 8 (11/3) Networking (II)
  • week 9 (11/10)  Midterm exam
  • week 10 (11/17) Homework I due, midterm project presentation
  • week 11 (11/24) Algorithms (I)
  • Advanced topic
  • week 12 (12/1) Algorithms (II)
  • week 13 (12/8) Programming language
  • week 14 (12/15) Demo for homework II
  • week 15 (12/22) Artificial Intelligence
  • week 16 (12/29) Final project demo
  • week 17  (1/5) Final Exam

Lecture Slides

week 1 (9/15) Administration issues [video]
week 2 (9/22) Tutorial for iRobot Create Tutorial for GPS [video1] [video2]
week 3 (9/29) History, Data Storage [video1] [video2]
week 4 (10/06) Hardware [video1] [video2] [video3]
week 5 (10/13) Operating System [video1] [video2] [video3]
week 6 (10/20) Networking and the Internet [video1] [video2] [video3]
week 8 (11/3)  [video1] [video2] [video3]
week 11 (11/24) Algorithm Project comment [video1] [video2] [video3]
week 12 (12/1) Scenario of homework II [video1] [video2] [video3]
week 13 (12/8) Artificial Intelligence Programming Languages



In this exercise, we want to answer this question:
    Is it easier to meet your friends on-line or to meet them in real world?
    * Every time when you are on-line
          o Go to this website
          o Enter your student ID and click on the ?Start? button on the
          o Before you go offline,click on the "End" button on the page
    * TA will announce an address let you download data.
    * Compare your online times with your teammates?
    * Draw the ?overlay? time when you and your teammate are both
      on-line with Microsoft Excel
    * Record your location with GPS
    * A GPS logger will be loaned to you, and you should carry it all
      the time
    * If you are indoor, find out your GPS location via Google Map and
      record it manually
    * Download your GPS log everyday
    * Remember to recharge the battery!!
    * Draw the ?overlay? time when you and your teammate are ?close? to
      each other with Microsoft Excel
          o ?close? is defined as your GPS location is less
            than 10m from your teammates?
    * Compare your mobility data with your teammates 
Important Date
    * Trace collection period (we only have around 100 GPS loggers)
          o 甲班(and 外系/轉系): 10/1-10/31
          o 乙班: 11/1-11/30
    * Results due
          o 甲班(and 外系/轉系): 11/12 midnight
          o 乙班: 12/10 midnight
          o Submit your results (submission instruction will be
            announced later)
          o NO late submission
    * The more detailed raw data you collected, the higher grade
          o GPS logger collect location every second
                + So you should have a maximum of 86400 data entries
                  every day
                + GPS can only work outdoor. Estimate your GPS location
                  using Google Earth if you are indoor
    * Your analysis of results should be sensible
    * An example is at

Homework II – Auto-parking

    * Learn simple programming via iRobot
    * Use the programmable robot (iRobot) to simulate auto-parking
    * TA will give you a tutorial on how to use and program iRobot (and
      how to use GPS for your homework) on 9/22
What to do?
    * You will be given two locations A, and B (somewhere around our
    * You need to write a program to move iRobot from A to B
How would I evaluate the performance of your program?
    * How much time it will take for your program to move iRobot from A
      to B (the shorter, the better!)?
    * Could your program park the iRobot exactly at location B? (in this
      homework, we use location B to simulate the 停車格)
Loaning Equipment
    * We only have 17 iRobot ($15K each) but we have more than 100 students
    * The equipment needs to be SHARED
    * The loaning time of any equipment from TA (including iRobot,
      sensor, GPS, etc) is up to 3 days
    * First come, first serve!
    * Make a reservation when all the iRobot have been checked out
iRobot Related Document

Term project

    * Design a car navigation system
    * Car navigation
          o Provide a route from A to B for the driver
          o A good navigation system
                + should provide a route that has the shortest travel
                  time from A to B
                + relies on accurate road information
Road information
    * Traffic light cycle (how long you need to wait for the red light)
    * Road length
    * Number of lanes
    * Traffic density, i.e. how many cars moving on the same road (e.g.

      rush-hours vs. off-peak time)

How to design your navigation system?

     1. collect the road info from the real-world
    2. Design an algorithm that use those road traffic parameters we previously discuss
        (I only listed 4 parameters, you are strongly welcome to add more if you wish) to
        predict the driving time from A to B

Collect Road information

    * We will assign different teams to collect traffic info for different areas (抽籤)
          o 中西區
          o 東區
          o 北區

Example of Traces

路 口 紅 燈 綠 燈
長榮路/大學路 30 seconds 45 seconds
長榮路/裕農路 20 seconds 30 seconds

路 名 路 段 Number of lanes Road length
長榮路三段 小東路-大學路 2 720m

路 名 路 段 Time Car density
長榮路三段 小東路-大學路 7am-8am 1239
長榮路三段 小東路-大學路 8am-9am 1102
長榮路三段 大學路-小東路 7am-8am 1011
長榮路三段 大學路-小東路 8am-9am 1259
    * Car density: In a given duration, the number of cars entering that
      particular road
    * Duration for collection of car density
          o 7-9am
          o 11-1pm
          o 5-7pm
Example of the algorithm
    * Should look like an equation or a function
    * For example
          o Travel time =  red light duration + car speed/road distance
            * number of lanes
          o I did not use ?car density? in the example above?but you
            should try to make use of EVERY possible parameter in your
    * Demo your algorithm
          o You will need to present your algorithm in mid-semester (3-5
            minutes) and explain how you design your algorithm
Demo your project demo
    * In the end of semester, you will demo your project as the following
    * I will ask you, for example, how long it takes to drive at a speed
      of 30km/hrfrom 光復校區 to 赤崁樓 at 1pm
    * You should use the collected road information traces and your
      algorithm to predict the travel time
Score for the final project demo
    * Your score = 25 x ( 1 ? D / real travel time)
          o D = | your predicted travel time ? real travel time |
Project Evaluation
    * Mid-term
          o A 3-5 minute presentation for your navigation algorithm (10%)
          o And one-page, 11-pt-font, double-spaced report that
            describes/explain/justify your algorithm
    * Final
          o Project demo (15%)
data collection: 7.5%
results: 7.5%


    * In class
    * Problems related to the topics of the week


    * In Q&A form
    * Questions mostly are from the textbook exercise
    * 2 Exams
          o Midterm (20%)
          o Final (25%)