UIT2201: Computer Science and the Information Technology Revolution

UIT2201: Computer Science and the Information Technology Revolution
(Fall 2016 Semester)

Detailed Syllabus

This page list the detailed syllabus for the module and links to the lecture notes. This year, I am making changes to bring more FUN to this course, and infuse "Computational Thinking" and "CS Unplugged" activities to the course. Hence, the notes and topics coverage will evolve a bit over the duration of the course.

For a start, I will link to lecture notes that were used for the course last year (2014 version). The new material will be continuously updated. (You can download the 2014 versions to get an idea of the course and to study ahead, but don't print yet [save some trees and help protect the environment].)

So watch this space for the Fall 2016 versions (and "Current Status" below).

Current Status: (Updated: 11-11-2016)
Added in notes on OPTIONAL FUN topics (Section 8). Not covered in Exam. For your FUN learning!

1. Course Overview, CS Problem Modelling and Solving (2)

Goal: To give overview of UIT2201. To kick start the course with an interesting illustration of how to model and solve problems in computer science. This is done by way of the interesting Tourist Problem.

Lecture Notes: (Updated 2016 versions)
About the Course --- | Course Overvew (pdf) |

Lectures (2 hrs): Week 1

2. The Pervasive Computer, ITEM (IT Enabled Mindset) (1 hour)

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 ITEM -- "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.)

Compulsory Reading: | [SG] - Ch 1; |

Lectures (2 hr): Week 2

3. Algorithms (7 hours)

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; |
Supplementary Reading: | [Brookshear] - Ch 4-5; |

Efficiency of Algorithms --- | [Part E] (pdf) NEW! |

More Simple Algorithms (for beginners) --- | Alg-supp (html) | | Alg-supp (pdf) |

Fun Optional Stuffs (to be covered later in course):
Bin Packing Algorithm --- | Bin Packing (ppt) [2014 version] |

Optional Stuffs (not covered in course):
Recursive Algorithms (optional, for info only) --- | [Part D] (ppt) [2014 version] |

Lectures (8 hrs): Week 3,4,5,6

4. Database (2 hours)

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; |
Supplementary Reading: | [Brookshear] - Ch 9; |

Optional Stuffs (not covered in course):
Relational Databases as Relational Algebra (optional, for info only) --- | Notes (pdf) |
(Note used when I taught "Discrete Math" at UIUC, Fall 1996;
adapted from: Discrete Mathematics and its Applications, by Kenneth H. Rosen, McGraw-Hill.)

Lectures (4 hrs): Weeks 7,8.5

5, 6. Hardware (5 hours)

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; |
Supplementary Reading: | [Brookshear] - Ch 1-2; |

Lecture Notes: (All updated)
Binary Computer, Logic and Basic Building Blocks --- | (pdf) [updatd] |

Computer Organization and Architecture --- | Here (pdf) [updatd] |

Optional Stuffs (not covered in course):
Karnaugh Maps (optional, for info only) --- | notes (txt) |

Additional Notes:

Lectures (6 hrs): Week 8,9, 11 (Wk 10 holiday)

6. Networks/Internet/WWW (2 hours) [Skipped in Fall 2016]

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; |
Supplementary Reading: | [B] - Ch 3; |

Lecture Notes: (Spring 2013 version)
Network, Internet, WWW --- | Network (ppt) |
Animating Comm Protocols --- | Protocols animated (ppt) |

Optional Stuffs (not covered in course):
Optional notes on internet and web-pages (html) (for info only) --- | here (ppt) |

~~Lectures (2 hrs): Week 9~~

7. Artificial Intelligence (4 hours)

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; |
Supplementary Reading: | [B] - Ch 10; |

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

Lectures (4 hrs): Week 12 & 13

9. E-commerce, Security and Cryptography (2 hours) [not covered!]

8. Theory (2 hours) [not covered!]

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, Complexity of solving problems, Approximation Algorithms

Compulsory Reading: | [SG] - Ch 11; Ch 3.6 |
Supplementary Reading: | [B] - Ch 11; |

Lecture Notes: (All 2016 versions )
Computability and Complexity --- | Theory (pptx) (updated) |
Approximation Algorithms (Bin Packing) --- | Here (ppt) (updated) |

Additional Notes: (for info only) | theory (txt) |

Lectures (2 hrs): Week 13

9. E-commerce, Security and Cryptography (2 hours) [not covered!]

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; |
Supplementary Reading: | [B] - Ch 11; |

Lecture Notes: (Spring 2013 version) | SG-Chap13 (ppt) | | Cryptography (ppt) |

Additional Notes: | information theory (txt) | | privacy-security (html) |

Planned Lectures (2 hrs): Week 12

10. Computers and Society (1 hour) [not covered]

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; |
Supplementary Readings: | [B] - Ch 11; |

Lecture Notes: (Old -- 2010 version) | Social (ppt) |

Lectures (1 hr):

11. Past and Future Trends (1 hour) [not covered]

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 -- 2010 version) | Future (pdf) |

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

Lectures (1 hr):

12. Revision (Optional) [T13]

UIT2201 Syllabus (Fall 2013)