(Spring 2009 Semester)
Update Status:
Lecture notes for Topic 5 (Networks) have been updated.
You can download and print if you want to.
Will be updating Topic 6 (AI) next...
(LeongHW, 27-Mar-2009 (Fri)...)
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. Discuss what is needed to have an IT-enabled mindset.
Topics: Some examples such as Email, Walk through a house, electronic
bank transaction, CD/MP3, module registration, Linc, expert system,
sum of 1 to 100, 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. e-greeting cards.
Examples of advantages of having an IT-enabled mindset.
(Also give an overview of CS and perspectives from the textbook.)
Lecture Notes: (2009 version [updated])
About the Course ---
| Course Overview (ppt) [updated] |
The Computer Revolution ---
| Introduction (ppt) [no-change] |
| Algo-Animation (ppt) [no-change] |
Overview of CS (from [SG3]) ---
| SG-Chap1 (ppt) [Self-Study] |
Lectures (2 hrs): Week 1
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.
Compulsory Reading: | [SG] - Ch 2-3; |
Lecture Notes: (2009 version [updated])
Algorithms, Pseudo-Code, and Primitives Operations ---
| [Part A] (ppt) [updated] |
Algorithmic Problem Solving ---
| [Part B] (ppt) [updated] |
| Alg-Animation (ppt) [updated] |
More Simple Algorithms (for beginners) ---
| Alg-supp (html) [no change] |
| Alg-supp (ppt) [no change] |
Efficiency of Algorithms ---
| [Part C] (ppt) [updated] |
Fun Stuffs (to be covered later in course):
Tourist Problem and Graph Colouring ---
| Tourist Problem (pdf) |
Bin Packing Algorithm ---
| Bin Packing (ppt) |
Optional Stuffs (not covered in course):
Recursive Algorithms (optional, for info only) ---
| [Part D] (ppt) |
Lectures (6 hrs):
Goal: To appreciate the idea of organizing, managing and using data. We examine issues related to databases and database applications.
Topics: Notion of data and tables. Combination of tables. Database terminologies and operations. Issues related to database organization, query processing, and concurrency control.
Compulsory Reading: | [SG] - Ch 13.3; |Lecture Notes: (2009 versions [updated]
Databases ---
| Database (ppt) [updated] |
Animating SQL Queries ---
| SQL-Animated (ppt) [no change] |
Primitive Database Operations ---
| Notes [txt] |
(MUST READ)
Databases ---
| Concurrency (ppt) [new] |
| Record-Locoking (Wikipedia) [pdf] |
Notes from [SG3] ---
| SG-Chap13-3 (ppt) | (Self Study)
Optional Stuffs (not covered in course):
Relational Databases as Relational Algebra (optional, for info only) ---
| Notes (pdf) |
(adapted from: Discrete Mathematics and its Applications,
by Kenneth H. Rosen, McGraw-Hill.
Lectures (2 hr):
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.
Compulsory Reading: | [SG] - Ch 4-5; |Lecture Notes: (2009 versions [no change from 2008])
Basics of Hardware, Building Blocks ---
| (Part 1) (ppt) [no change] |
Computer Hardware System ---
| (Part 2) (ppt) [no change] |
Optional Stuffs (not covered in course):
Karnaugh Maps (optional, for info only) ---
| notes (txt) |
Additional Notes:
Lectures (6 hrs):
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.
Compulsory Reading: | [SG] - Ch 7; |Lecture Notes: (2009 versions -- [updated])
Network, Internet, WWW ---
| Network (ppt) [updated] |
Animating Comm Protocols ---
| Protocols animated (ppt) [renamed] |
Optional Stuffs (not covered in course):
Optional notes on internet and web-pages (html) (for info only) ---
| here (ppt) |
Additional Notes: | The Sociable Machine (txt) | electronic publishing (txt) | Akamai (txt) | Gifts from the Web (txt) |
Lectures (2 hrs):
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.
Compulsory Reading: | [SG] - Ch 14; |Lecture Notes: (2008 versions)
Artificial Intelligence ---
| AI (ppt) |
Prolog ---
| PROLOG (ppt) |
Additional Notes: | Deep Blue Beats Gary Kasparov (txt) | robots (txt) |
Lectures (3 hrs):
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.
Compulsory Reading: | [SG] - Ch 11; Ch 3.6 |Lecture Notes: (2008 versions)
Artificial Intelligence ---
| Theory (ppt) |
Bin Packing Approx Algorithms ---
| Approx-Alg (ppt) |
Additional Notes: (for info only) | theory (txt) |
Lectures (1 hr): (Did NOT cover computational complexity [Last 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.
Compulsory Reading: | [SG] - Ch 13; |Lecture Notes: (Old -- 2007 version) | SG-Chap13 (ppt) | | Cryptography (ppt) |
Additional Notes:
| information theory (txt) |
| privacy-security (html) |
Planned Lectures (2 hrs):
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.
Compulsory Reading: | [SG] Ch 15; |Lecture Notes: (Old -- 2007 version) | Social (ppt) |
Additional Notes: | Info Economy (txt) | More Info Economy (txt) | Research & Trendiness (txt) | privacy-security (html) |
Lectures (1 hr):
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.
Compulsory Reading: | [SG] Ch ??; |Lecture Notes: (Old -- 2007 version) | Future (pdf) |
Additional Notes: | CS History (txt) | Quantum computing (txt)
Lectures (1 hr):