USST01: Computer Science and the Information Technology Revolution

(Spring 2002 Semester)


Instructor: A/P Leong Hon Wai, (email: leonghw@comp.nus.edu.sg)
Office: Blk S16, Rm 05-05; Tel: 874-4358;


Lectures, Tutorials, Consultations

Lectures: Tue 10am-12nn USP-SR4 for all
Tutorials: Fri 10am-12nn
Fri 2-4pm
USP-SR4
USP-SR3
Group 1
Group 2
Consultation: Tue/Wed 4pm Office (else email me)
Exam: 23-April AM MPSH2


Reading List:

The following three textbooks provide a fairly complete picture of the whole area, each from a somewhat different perspective:

  • A: [Brookshear] "Computer Science, an Overview," J. Brookshear, Addison Wesley, 2000, ISBN: 0-8053-4632-5.
    (Note: This book gives the CS perspective.)

  • B: "Management Information Systems," Haag, Cummings & Dawkins, McGraw-Hill, 2000, ISBN: 0-07-231535-0. (Note: The library copy dated 1999 but appears same.)
    (Note: This book gives the business perspective.)

  • C: "Computers in Your Future," Meyer, Baber & Pfaffenberger, Que (Macmillan/Prentice-Hall), 1999, ISBN: 1-58076-085-6. (Note: The new edition 2002 is not yet here.)
    (Note: This book gives the layman's perspective.)
  • The following two books appeal to the future researchers

  • "Great Ideas in Computer Science," Alan W Biermann, MIT Press, ISBN: 0-262-02302-4.

  • "Turing Omnibus: 61 Excursions in Computer Science," A. K. Dewdney, Computer Science Press, ISBN: 0-7167-8154-9.

  • Assessment Allocation (Spring 2002)

    Final Exam:          30% 
    Term Paper:          30%
    Practical Exercises: 20% (5-6 sets)
    Tutorial Exercises : 20% (5-6 sets)
    
                  Total: 100%
    


    Detailed Syllabus

    1. Introduction, Motivation and Top level Demystification (4 lectures)

    Goal: To illustrate pervasiveness of computers and how it has changed our lives in a significant way. Introduce the type of CS components (as black boxes) that go into some technologies.

    Topics: Some examples such as Email, Walk through a house, electronic bank transaction, CD/MP3, module registration, Linc, expert system, sum of 1 to 10, etc would be considered to illustrate the pervasiveness of computers and to introduce the various CS components (as black boxes) that are needed to make the above work. Search Engines. Databases.

    Readings: A - Ch 0; B - Ch 1-4; C - Ch 1

    Lecture Notes: | Introduction (ppt) | Trends (pdf) | Database (ppt) |

    Additional Notes: | The Capable Computer (txt) | History of PC (txt) |

    Actual Lectures: (4) Wk1 + Wk2: 8-Jan, 8-Jan, 15-Jan, 15-Jan


    2. Algorithms (3 lectures)

    Goal: To introduce the notion of algorithms as a means for telling a physical device, how to solve a problem in a step by step fashion. To introduce the idea of systems analysis, capturing data to represent state of objects in real life and events that change object states .

    Topics: Notion of an algorithm. Some simple algorithms and basic idea about complexity of an algorithm.

    Readings: A - Ch 4-5; C - Ch 4.

    Lecture Notes: | Algorithms (New) (ppt) | Algorithms (Old) (ppt) |

    Actual Lectures: (4) Wk3 + Wk4f: 22-Jan, 22-Jan, 29-Jan, 29-Jan


    3. Hardware (3 lectures)

    Goal: Physical realization of a computer. To give some simple steps to illustrate how a physical computer may be constructed. To understand that the computers are essentially devices computing logical functions. To illustrate approach of building complex systems by incrementally realizing and putting together well defined simpler parts.

    Topics: binary numbers, boolean logic, logic gates, transistors, combinatorial/sequential circuits, memory, CPU, ALU, Von Neumann Architecture, peripherals. The above topics will be explained using simple examples with the aim to give an idea to the students about how the physical computer can be built and their scientific basis. In general in this and all topics below the idea would be to give only a brief overview so as to "demystify" the technology and address the advantages and impact of the technology.

    Readings: A - Ch 1-2; C - Ch 2.

    Lecture Notes: | Hardware (New) (ppt)! | | Hardware (old) (ppt) |

    Additional Notes: | Karnaugh Maps (txt) |

    Actual Lectures: (4) Wk5 + Wk6: 5-Feb, 5-Feb, 15-Feb, 15-Feb [Makeup for CNY]


    4. Virtual Machine (2 lectures)

    Goal: To appreciate the idea of creating and presenting more versatile interfaces for computing machines, and to understand how these vastly different interfaces can be implemented merely through appropriate software programmes (OS/System Software/High-level Languages). Motivation includes human user friendliness and physical resource sharing in a mode transparent to its multiple users.

    Topics: Notion of language translators as programmes, to present an apparently new and more human-friendly machine that understands higher-level commands. Notion of using programmes on a single physical machine to emulate multiple machines existing simultaneously and independently.

    Readings: A - Ch 3; C - Ch 5.

    Lecture Notes: | Virtual Machines (pdf) |

    Additional Notes: | single machine/multiple machines (txt) |

    Actual Lectures: (2) Wk7: 19-Feb, 19-Feb


    5. Networks/Internet/WWW (2 lectures)

    Goal: To present and highlight the idea and advantages of linking together multiple machines that are physically separated to form ``communities'' of machines with unique identites. Advantages inclide extended capabilities in terms of resource sharing, communication, web etc.

    Topics: network, communication links, internet, addressing, protocols, routing algorithms, WWW, network services, resource sharing, client-server, ftp, telnet, email, newsgroups, bbs, ecommerce, web-mail.

    Readings: A - Ch 3; B - Ch 6; C - Ch 6-8.

    Lecture Notes: | Network (pdf) | | Network(more) (ppt) |

    Additional Notes: | The Sociable Machine (txt) | electronic publishing (txt) | Akamai (txt) | Gifts from the Web (txt) |

    Actual Lectures: (2) Wk9: 05-Mar, 05-Mar [Just after break]


    6. Modeling, Simulation and Software Applications (1 lecture)

    Goal: To present the idea of using computers as a platform for representing and simulating physical entities or abstract concepts in virtual environments. To appreciate the convenience and power that simulation and other software applications can bring about.

    Topics: Simulation and applications as computer programmes. Principles behind modeling and simulation using computers.

    Readings: B - Ch 7; C - Ch 11.

    Lecture Notes: | Simulation (Old) (pdf) |

    Additional Notes: | simulation (txt) | | security |

    Actual Lectures: (1) Wk10: 12-Mar


    7. Abstraction, Specification and Problem Decomposition (1 lecture)

    Goal: To appreciate difficulties involved with developing and understanding large scale complex systems. To present principled methods and modes of thought that computer scientists and engineers have adopted for making large problems more tractable.

    Topics: Notions of abstraction, decomposition, interfaces, reuse. Abstraction, specification and decomposition as powerful modes of thought and problem solving approaches for dealing with large complex systems. Examples of the above in developing and understanding algorithms. Code libraries as collections of well specified abstract routines to support re-use.

    Readings: A - Ch 6; B - Ch 8-9; C - Ch 9.

    Lecture Notes: | Abstraction (pdf) |

    Additional Notes: | abstraction (txt) | | project management (txt) |

    Actual Lectures: (1.5) Wk10: 12-Mar, 19-Mar


    8. Artificial Intelligence (2 lectures)

    Goal: To address the question (and broader issues) of whether computers are basically dumb machines following instructions (programs), or whether programs can exhibit ``autonomous'' behaviour, and hence ``intelligence''. The quest to qualify the notion of machine intelligence and ways of achieving or at least emulating it.

    Topics: Philosophical issue. Can machines think? or do they just follow programs? Can we think or are we just following DNA? Historical Perspective on how machine trying to do human like activities were built. Perception, recognition, reasoning, knowledge representation, learning, expert system, game playing.

    Readings: A - Ch 10; B - Ch 5; C - Ch 10D.

    Lecture Notes: | Artificial Intelligence (Old) (pdf) |

    Additional Notes: | Deep Blue Beats Gary Kasparov (txt) | robots (txt) |

    Actual Lectures: (2.5) Wk11, Wk12: 19-Mar, 19-Mar, 26-Mar


    9. Theory (2 lectures)

    Goal: To provide a mathematical model to reason about the capabilities of computers, what computers can or cannot do, and how efficiently they can do? To highlight and appreciate the intellectual beauty that one can reason about the capabilities of computers and arrive at powerful conclusions without experimentation.

    Topics: Turing Machine, Automata, Unsolvability Efficiency/Complexity of solving problems.

    Readings: A - Ch 11.

    Lecture Notes: | Theory (ppt) |

    Additional Notes: | theory (txt) |

    Actual Lectures: (3.5) Wk12 and Wk 13: 26-Mar, 02-Apr, 02-Apr


    10. Cryptography, Security and E-commerce (1 lecture)

    Goal: The notion and need for communication security and how to achieve it. Powerful theoretical ways to reason about and quantify degree of security, without need for actual experimentation and simulations.

    Topics: What does security mean. Some basic cryptography algorithms. Interactive Proofs, Zero-Knowledge proofs, Applications in Ecommerce.

    Readings: A - Ch 11.

    Lecture Notes: | Cryptography (ppt) |

    Additional Notes: | information theory (txt) |

    Actual Lectures: (1) W14: 09-Apr


    11. Past and Future Trends (1 lecture)

    Goal: To understand on how various scientific advances have influenced the cost, performance, size and availbility of computers, and the extent to which the current trend might continue. To understand how computers have been and might be employed as a result of its increasing pervasiveness. To examine some predictions, and to evaluate their technical soundness and/or feasibility based on current knowledge.

    Topics: Quantum devices --- transistors and lasers, as the foundation of silicon-based computers. Physical, and hence technical limits of such devices. Principles behind Biocomputing and Quantum computing as fundamentally different computing paradigms, and their feasibility. Predictions on future computer usage, capabilties, and their technical bases.

    Lecture Notes: | Future (Old) (pdf) |

    Additional Notes: | CS History (txt) | Quantum computing (txt)

    Actual Lectures: (0.5) Wk14: 09-Apr


    12. Computers and Society (2 lectures)

    Goal: To emphasize the wide impact of computers on society and how it has changed our lives in a significant way. To be aware that potential social/legal/ethical issues exist and may arise due to information technology.

    Topics: Examples to illustrate how computers have impacted on society and changed our lives in a significant way. Range of issues that can exist as a result of technology, which may or may not have right solution. Example issues.

    Readings: B - Ch 11; C - Ch 11.

    Lecture Notes: | Social (Old) (ppt) |

    Additional Notes: | Information Economy (txt) | research & trendiness (txt) | More Info Economy (txt) |

    Actual Lectures: (1) Wk14: 9-Apr


    13. Revision (2 lectures)

    Lectures: Wk14: 12-Apr, 12-Apr | Summary (ppt) |

    Past Year Exam: | here (pdf) | (Discussed on 5-April-2002)

    End of Course: Exam: Tues 23-Apr-2002; 8:30AM; @MPSH2


    [TOP] Install Acrobat on your system to read PDF files.