Concepts, Techniques and Models of Computing

 

Introduction	Notes c_const_test.c
Declarative Model	Outline
Exceptions	Exceptions
Unification	Unification
Declarative Programming Techniques- Tail Recursion, Follow. the grammar	declarative- programming
Declarative Concurrency - Introduction, Semantics	declarative-concurrency Thread.oz
Declarative Concurrency-Threads
Erlang - Sequential Programming, Concurrent Programming	erlang
Erlang - Concurrent Programming (contd.)
Object-Oriented Programming	oop Java 1.4 Polymorphism
Type Inference	tinf

Some fact about Complexity, Algorithms, Cryptography

• Computational Complexity

Most of the open problems in computational complexity can be stated in terms of lower bounds. There are few general techniques available in proving lower bounds, and consequently, there has been little progress in this field. My approach to solving such problems is bottom up, working with simple open problems such as:

• Do we need an exponential number of states to simulate a two-way nondeterministic finite automaton by a deterministic one?
• What is the minimum parallel time required to solve some specific problems using a given number of processors? 

• Algorithms

  I am working on designing new sequential and parallel algorithms, and improving existing ones, to solve various computational problems such as: graph isomorphism, membership in permutation groups (generalized Rubik's Cube), network flow, matching in graphs, Boolean matrix multiplication, and connectivity of graphs.
  Recently, I have been concentrating on the following problems.
  Dynamic graph algorithms. These are algorithms which solve problems in which the input graph keeps changing; e.g. edges are inserted and deleted or weights are increased or decreased. The goal is to maintain the solution in such a way that the changes in it can be found faster than resolving the problem from scratch.
  String processing algorithms with applications to molecular biology. There exist computational problems associated with the human genome project where algorithmic improvements are possible. An area were considerable progress has already been achieved is the speed up of various dynamic programming techniques.
   

• Cryptography

  Various number theoretic problems, such as factoring of integers, primality testing, discrete logarithms and quadratic residuocity, are used as a basis for public key cryptosystems. The security of such crpytosystems therefore depends on the complexity of these problems. A deeper understanding of the complexity of these problems can help in reasoning about the security of the cryptosystems.
  Currently, proving the correctness and security of cryptoprotocols is hard. I am working on general techniques that can be applied to constructing protocols for which it is possible to prove things about.
   

Automaton Simulator

Finite State Automation Applet is an automaton simulator, similar to JFLAP. Requires Java.

Analysis of Algorithm

	Introduction,   RAM model,     Worst-case complexity I Asymptotics		Note 1
	Asymptotics, Induction, Divide and conquer, Merge sort Recurrence, Recursion tree		Note 2
	Binary search, Powering, Matrix multiplication, Strassen's algorithm, Master theorem		Note 3
	Randomized algorithms, Quicksort and its analysis		Note 4
	Randomized Quicksort		Note 5
	Selection in linear time, and Lower bound on comparison sorts		Note 6
	Counting sort and Radix sort Hash tables and hash functions		Note 7.1 Note 7.2
	Universal hashing		Note 8
	Perfect hashing and Binary search trees		Note 9.1 Note 9.2
	Red-Black trees		Note 10
	Augmenting data structures Order statistics, Interval trees		Note 11
	Greedy algorithms Activity selection		Note 12
	Greedy: Huffman trees, Dynamic programming: Rod cutting		Note 13
	Dynamic programming: Longest common subsequence
	Midterm in class
	Dynamic programming: Optimal binary search tree; midterm problems		Note 14
	Amortized analysis		Note 15
	Graphs and Breadth-first search		Note 16
	Breadth-first search and its correctness		See Note 16
	Depth-first search and Topological sort		Note 17
	Strongly connected componentsMinimum spanning tree: the generic method		Note 18
	Minimum spanning trees: Kruskal and Prim		Note 19
	Single-source shortest path: Bellman-Ford and Dijkstra		Note 20
	All-pairs shortest paths		Note 21
	Maximum Flow: Ford-Fulkerson		Note 22
	Edmonds-Karp, and Maximum bipartite matching		Note 23
	NP-completeness		Note 24
	NP-completeness		Note 25