Wikplayer

Tips for taking Class Notes

We will be using mathematical notation too rich for HTML. So format your notes in LaTeX, compile it and submit the working TeX and/or PostScript file.

Take notes in your own style after understanding the lecture. Your notes shouldn't be just a dictation exercise.

Your notes will be read by students who didn't follow the lecture in class or were absent. So don't use cryptic SMS-style language in the final version that you submit. In particular, avoid grammatically incorrect and incomplete sentences. You can see the brief writeup on Well ordering and generalized induction to get an idea of how your notes should look like.

Since verbal explanations accompany text written on the board in class, simply copying what's written on the board may give an incomplete picture. Fill in gaps, if any, in board-writing by what is said in class.

If you didn't follow something, check with friends, ask the TA or the instructor and get it clarified before submitting your notes. Taking notes without understanding can lead to incorrect statements, which is worse than no notes at all.

Machine Learning and Optimization

Machine Learning algorithms and optimization techniques have become central to most applications of computing ranging from search, ads, data-mining, data-analytics in large databases, information retrieval and extraction, natural language processing including machine translation, speech, vision, gaming, user adaptation of computing systems, as well as security, privacy, and the broad topic of crowd-sourcing. Our goal is to conduct research in theoretical and practical aspects of Machine Learning and Optimization including:

• Novel machine learning algorithms and paradigms
• Foundational aspects of optimization techniques, including new algorithms and applications to machine learning
• Theoretical analysis of machine learning and optimization algorithms
• Performance analysis and enhancement of machine learning and optimization algorithms
• Applications in search and IR, vision, NLP and other areas
• Data mining and data analytics for very large data sets

TURING LECTURES A.M. TURING AWARD WINNERS BY...

(2011) Pearl, Judea The Mechanization of Causal Inference: A “mini” Turing Test and Beyond

(2010) Valiant, Leslie Gabriel The Extent and Limitations of Mechanistic Explanations of Nature

(2009) Thacker, Charles P. (Chuck) Improving the future by examining the past: ACM Turing Award Lecture

(2008) Liskov, Barbara The Power of Abstraction

(2007) Clarke, Edmund Melson Model checking: my 27-year quest to overcome the state explosion problem

Emerson, E. Allen Model checking: A Personal Perspective

Sifakis, Joseph The Quest for Correctness Beyond Verification

(2006) Allen, Frances ("Fran") Elizabeth Compiling for Performance: A Personal Tour

(2005) Naur, Peter Computing vs. Human Thinking

(2004) Cerf, Vinton (“Vint”) Gray Assessing the Internet: Lessons Learned, Strategies for Evolution, and Future Possibilities

Kahn, Robert (“Bob”) Elliot Assessing the Internet: Lessons Learned, Strategies for Evolution, and Future Possibilities

(2003) Kay, Alan Turing Award Lecture

(2002) Adleman, Leonard (Len) Max Pre-RSA Days: History and Lessons

Rivest, Ronald (Ron) Linn The Eary Days of RSA: History and Lessons

Shamir, Adi Cryptography: State of the science

(1996) Pnueli, Amir Verification engineering: a future profession

(1994) Feigenbaum, Edward A ("Ed") How the “what” becomes the “how”

Reddy, Dabbala Rajagopal ("Raj") To dream the possible dream

(1993) Hartmanis, Juris Turing award lecture: on computational complexity and the nature of computer science

Stearns, Richard ("Dick") Edwin Turing award lecture: it's time to reconsider time

(1992) Lampson, Butler W Principles for Computer System Design

(1991) Milner, Arthur John Robin Gorell ("Robin") Elements of interaction

(1990) Corbato, Fernando J ("Corby") On building systems that will fail

(1987) Cocke, John The search for performance in scientific processors

(1986) Hopcroft, John E Computer science: the emergence of a discipline

Tarjan, Robert (Bob) Endre Algorithm design

(1985) Karp, Richard ("Dick") Manning Combinatorics, complexity, and randomness

(1984) Wirth, Niklaus E From programming language design to computer construction

(1983) Ritchie, Dennis M. Reflections on software research

Thompson, Kenneth Lane Reflections on trusting trust

(1982) Cook, Stephen Arthur An overview of computational complexity

(1981) Codd, Edgar F. ("Ted") Relational database: a practical foundation for productivity

(1980) Hoare, C. Antony ("Tony") R. The emperor's old clothes

(1979) Iverson, Kenneth E. ("Ken") Notation as a tool of thought

(1978) Floyd, Robert (Bob) W The paradigms of programming

(1977) Backus, John Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs

(1976) Rabin, Michael O. Complexity of computations

Scott, Dana Stewart Logic and programming languages

(1975) Newell, Allen Computer science as empirical inquiry: symbols and search

Simon, Herbert ("Herb") Alexander Computer science as empirical inquiry: symbols and search

(1974) Knuth, Donald ("Don") Ervin Computer programming as an art

(1973) Bachman, Charles William The programmer as navigator

(1972) Dijkstra, Edsger Wybe The humble programmer

(1971) McCarthy, John Generality in artificial intelligence

(1970) Wilkinson, James Hardy ("Jim") Some comments from a numerical analyst

(1969) Minsky, Marvin Form and content in computer science

(1968) Hamming, Richard W One man's view of computer science

(1967) Wilkes, Maurice V. Computers then and now

(1966) Perlis, Alan Jay The synthesis of algorithmic systems

About Java Shell

This file gives instruction on how to install and run the Java Shell

Installation

•     Java Shell comes in a zipped format - jshell.tar.gz
•     Unzip the file in the directory where the Java Shell has to be installed
•     The zipped file will expand to the following directory structure

                  jshell---
                                       
                                        |---- source ---( contains source code of java shell)
                                       
                                        |---- man1--- ( contains man pages for the commands)
                                      
                                        |---- classes---
                                                  |--- ( contains class files of the source code)
                                                  |--- help---( contains help files for the commands)
 
   

Run the Shell

• The shell is written in java  and it makes use of java swing api. To run the shell JVM has to be installed on the machine .

• Set the PATH and CLASSPATH environment variables appropriately . Make sure that the CLASSPATH includes swing classes.

• To run the Shell go to the classes subdirectory of jshell . i.e. cd  jshell/classes

• In the classes directory type at the comand prompt :  java  JShell to run the shell

• The java shell is up and running

To get help on a command

•   To see what all commands are  supported by Java Shell type  help from      the java shell
•   To get help on a particular command type  help  commandname  

Man pages

•    To see a manual entry on a command  go to the jshell directory .
•     Type  man -M  .  commandname

 

Click to see the report on java shell

Click to download java shell source code

Principles of compiler design By Aho & Ullman

The Dragon Book

Theory of Computation Books

Advanced Complexity Theory
by Daniel Spielman, 2001, PDF

Algorithmic Randomness and Complexity
by R. G. Downey, D. R. Hirschfeldt, 2010, 629 pages, 4MB, PDF

Bayesian Computational Methods
by Christian P. Robert, 2010, 59 pp, 3.7MB, PDF

Cellular Automata
edited by S. Bandini, B. Chopard, M. Tomassini, 2002, 379 pp, 8.3MB, PDF

Cellular Automata
Wikibooks, 2010

Cellular Automata And Complexity: Collected Papers
by Stephen Wolfram, 1994

Cellular Automata: Simplicity Behind Complexity
edited by Alejandro Salcido, 2011, 566 pages, 31MB, PDF

Combinatorial Optimization: Exact and Approximate Algorithms
by Luca Trevisan, 2011, 139 pages, 830KB, PDF

Communication Complexity
by Domotor Palvolgyi, 2005, 39 pages, 380KB, PDF

Complexity
by Rajesh R. Parwani, 2002

Complexity Theory by Johan Hastad, 2008, 130 pages, 0.7MB, PDF

Computability and Complexity
Wikibooks, 2010

Computability and Complexity from a Programming Perspective
by Neil D. Jones, 1997, 485 pages, 1.7MB, PDF

Computability and Randomness
by Andre Nies, 2008, 447 pages, 2.6MB, PDF

Computability Theory
by Wilfried Sieg, 2006, 125 pp, 1.9MB, PDF

Computational Complexity: A Modern Approach
by Sanjeev Arora, Boaz Barak, 2008, 489 pages, 4.4MB, PDF

Computational Modeling and Complexity Science
by Allen Downey, 2008, 97 pages, 1.4MB, PDF

Finite-state Automata in Java
by Bradley Kjell

From Complexity to Creativity
by Ben Goertzel, 1996

From Philosophy to Program Size
by G. J. Chaitin, 2003, 54 pages, PS/PDF

Handbook of Quantum Information
Quantiki, 2013, online html

Introduction to Complexity Theory
by Oded Goldreich, 1999, 375 pages, 2.3MB, PDF

Introduction to Computational Complexity
by Martin Tompa, 1991, 85 pages, 1MB, PDF

Introduction to Quantum Algorithms for Physics and Chemistry
by Man-Hong Yung, et al. 2012, 44 pp, 2MB, PDF

Introduction to Quantum Cellular Automata
by B. Aoun, M. Tarifi, 2004, 46 pages, 330KB, PDF

An Introduction to Quantum Computing using Cavity QED concepts
by Zachary Burell, 2012, 53 pp, 260KB, PDF

An Introduction to the Theory of Computation
by Eitan Gurari, 1989, 314 pages, 3.2MB, ZIP/HTML

Lecture Notes on Algorithm Analysis and Computational Complexity
by Ian Parberry, 119 pages, 1.9MB, PDF

Lecture Notes on Computational Complexity
by Luca Trevisan, 2004, 171 pages, 0.9MB, PDF

Logic for Computer Scientists
by Uli Furbach, 2010

Mathematical Foundations of Automata Theory
by Jean-Eric Pin, 2012, 310 pp, 1.9MB, PDF

Notes on Automata, Logics, Games and Algebra
by K Narayan Kumar, 2007, PDF

P, NP, and NP-Completeness: The Basics of Complexity Theory
by Oded Goldreich, 2010, 190pp, 1.9MB, PS

Physics, Topology, Logic and Computation: A Rosetta Stone
by John C. Baez, Mike Stay, 2009, 73 pages, 780KB, PDF

Quantum Computation
by John Watrous, 2006, 139 pages, 660KB, PDF

Quantum Walks: A Comprehensive Review
by Salvador E. Venegas-Andraca, 2012, 88 pp, 1.5MB, PDF

Recursion Theory
by Frank Stephan, 2009, 125 pp, 610KB, PDF

Rule-based Computation and Deduction
by Helene Kirchner, Pierre-Etienne Moreau, 2001, 100 pp, 870KB, PDF

Think Complexity: Complexity Science and Computational Modeling
by Allen B. Downey, 2012, 146 pp, 1.2MB, PDF

Tree Automata Techniques and Applications
by H. Comon, M. Dauchet, R. Gilleron, 2008, 262 pages, 2MB, PDF