First-Year Seminar, Winter 2013

Great Ideas in Computer Science

Instructor:
Zhaojun Bai
3005 Kemper Hall
530-752-4874
bai at cs.ucdavis.edu

Meeting time:
4:10pm - 5:00pm, Wed..
1007 Giedt

Office Hours :

Catalog Description
This seminar begins with first and most important of the great ideas of computer science: the algorithm - a procedure or recipe that can be given to a person or machine for doing a job. We will then discuss other great ideas revolve around this central one, and experiment few processes of computer simulation to try our ideas. The class will condense a great of deal of complex material into a manageable, accessible form to all students who have a curiosity to learn about computing. The object is to let students gain basic understanding and appreciation some intellectual ideas in computer science.

Textbook
The instructor will provide lecture notes and reading materials taken from a variety of sources.

Homework assignment and grading:
The seminar meets one hour each week. The meetings will be consisted of classroom lecture and discussion. Students will be given a letter grade based on two short assignments (30%), participation in classroom discussions (30%), and a report on a pre-approved, relevant topic of their choosing (40%).

On-line Info:
Lecture schedule, handouts and assignments
  1. 1/9 and 1/16
    • The idea of recursion: a simple idea to solve large problems
    • Reading: Chap. 1 and 3 of ``Thinking Recursively'' by Eric Roberts (handout)
    • Video: traditional song ``There's a hole in the bucket"
    • Additional reading assignment: the tower of Hanoi (handout)
  2. 1/23 and 1/30
    • Induction and complexity
    • Reading: Chap. 2 of ``Thinking Recursively'' by Eric Roberts (handout)
  3. 2/6
    • Abstraction
    • Reading: Prof. Harvey's introduction to abstraction (handout)
    • Reading: J. Karmer: Is abstraction the key to computing?'' (handout)
  4. 2/13
  5. 2/20
    • Algorithmic methods: dvide-and-conquer, greedy algorithms
  6. 2/28
    • Guest lecture by Prof. P. Rogaway on what computers cannot do
    • Halting problem, Post Correspondnce Problem and the Diophantine Equation Problem (Hilbert's 10th problem)
  7. 3/6
    • Concurrency and parallelism
    • Reading: The free lunch is over: a fundamental turn toward concurrency in software

  8. 3/13
    • Student presentations

  9. 3/20 5:00pm, final project writeup due
Student project papers
  1. Michael Rea: The usefulness of recursion

  2. Stefan Paterson: When are computers going to kill us?

  3. Destiny Durham: Viewpoint computing as social science
    references: Computing as Social Science and Social science meets computer science at Yahoo

  4. Cynthia Quan: Computers in psychology
    References: Computer uses in clinical psychology

  5. Charlton Lin: Tower of Hanoi and Recursion
    References: (1) Tower of Hanoi explanation (2) Tower of Hanoi game (3) Reve's Puzzle game and explanation

  6. Cameron Bridges: Moore's law and you: why computer speed will continue to grow

  7. Jagdeep Singh: Future of the CPU (presentation)

  8. Lynn Huynh: Spirit of computing: abstraction

  9. Xinru Xiao: General facts about computer science

  10. Clark Fisher:Abstractness in computer science

  11. Kim Nguyen: Abstraction

  12. David Ogle: Greedy algorithm

  13. Dante Williams: Algorithmics vs. computer science

  14. Tue Doan: Recursion

  15. Candice Tandiono: Recursion and the tower of Hanoi

Additional reading
Questions sent to bai at cs.ucdavis.edu.