Principle and Practice of Computer Algorithms (Summer 2012)

Jump to: navigation, search



  • July 5 -- Update lecture schedule (just tentative).
  • July 4 -- This course will last from July 9 to August 3.
  • July 3 -- Hello world!


Welcome to CS484, Principle and Practice of Computer Algorithms! In this course, you are required to follow the lectures, and to finish one of the complementary tasks.

This year, the course will last from July 9 to August 3, and will focus on the fundamental aspects of both programming and programming languages.

Lecture Schedule

Lecturer: Xiao Jia

Location: SEIEE Building, Room 3-414

Time: 8:30am--11:30am (Monday to Friday)

A Structural Approach to Operational Semantics [1981]

  • July 9 -- Course Introduction, Transition Systems
    • Finite Automata
    • Three Counter Machines
    • Context-Free Grammars
    • Petri Nets
  • July 10 -- Selected Topics of Randomized Algorithms (by Jingcheng Liu)
    • Non-determinism vs. Randomness, PTM
    • Polynomial Identity Testing
    • Randomizing against adversary: Universal Hashing
    • Pseudo Random-number Generator: Derandomizing BPP
  • July 11 -- Interpreting Automata
    • The Language L
    • SMC Machine
    • \mathbf{let}\dots\mathbf{in}\dots\mathbf{end}
  • July 12 -- Simple Expressions and Commands
    • \langle e,\sigma\rangle
  • July 13 -- Functions and Classes
    • \lambda x.x+1
    • An object is a mapping from names to functions

The Evolution of Programming Languages [1999, revised 2002]

Language Presentations

Date Languages
July 23 AWK 郑辉煌 Groovy 朱旻申 Perl 沈思亮 PHP 罗璇 Python 蒋舜宁 Ruby 解东
July 24 Forth 董博男 Io 李霄旭 JavaScript 高岩松 Lua 吴航 PostScript 何瑞阳 Tcl 金天行
July 25 C# 张方魁 Ceylon 李一同 Go 王星凯 Opa 刘轩 Scala 谢佳明 Verilog 陈爽
July 26 Clojure 张惠楚 Datalog 李青林 Erlang 王浩然 F# 李冠儒 Haskell 杨宽 ML 汪旻
July 27 feature proposal & implementation 孙锴 陈楠昕 陈志鹏

» 点击此处下载评分表 «

Complementary Tasks

Location: Computing Center (包图旁边), Room 106 (July 9 to 22) and Room 201 (otherwise)

Time: 2:00pm--10:00pm (Monday to Friday)

USACO Training Program

Director: Yuke Liao, Tianxing He

Computational Number Theory

Director: Ziqing Xiang

#Students: up to 6

Real-World Projects

Director: Huan Yang

Students: Guanru Li, Dong Xie, Qinglin Li, Zhipeng Chen, Nanxin Chen

Grading Policy

  • 35% -- Language Presentation
  • 30% -- Complementary Tasks
  • 35% -- Algorithm Tests
    • Every Friday 2:00pm--5:00pm (3 hours, close-book)
    • Each test contains exactly 4 problems

Useful Links


Read this if you cannot access Google Groups

Try GoAgent:

Personal tools