|Each presentation is worth 20 points, graded based on the following points breakdown: contents (8), style/time management (6); 3 contributed Q/As (3); and summary of Q/As at presentation (3). (updated 10/17/2002)|
|Session #||Last Name||First/Middle Initials||Chapter||Presentation Date||Topic||Work (complete or missing)||Question Credits in Sessions|
|1||Llama||A||3||Sept. 3||Systems of logic, boolean bases||complete||3, 7, 9, 11, 13, 28|
|2||Lewandowski||S||5||Sept. 3||Godel's Incompleteness Theorem||complete||5, 6, 11, 12, 19, 25, 26|
|3||Levy||A||8||Sept. 3||Random numbers||complete||1, 4, 4, 14, 16|
|4||Drahl||JM||10||Sept. 5||Program Correctness||complete||1, 7, 9, 16, 17, 17|
|5||Beroual||N||16||Sept. 5||Genetic Algorithms||complete||10, 10, 11, 12, 16, 18|
|6||Coffman||MJ||19||Sept. 5||Computer Vision - Polyhedral Scenes||complete||2, 10, 11, 12, 18, 19|
|7||Enright||B||25||Sept. 10||Fast multiplication||complete||3, 10, 17, 18|
|8||Lovegren||MN||26||Sept. 10||Non-determinism||rescheduled for September 19|
|9||Higgins||W||29||Sept. 10||CAT scanning||complete||11, 13, 16, 28|
|10||Reigada||D||30||Sept. 12||The partition problem||complete||11, 16|
|11||DeBoer||SM||33||Sept. 12||Analog computation||complete||2, 10, 18, 21, 21, 26|
|12||Wilson||J||36||Sept. 12||Neueral networks that learn||complete||4, 22, 22|
|13||Rooks||JD||38||Sept. 17||Sequential circuits||complete||4, 7, 10, 16, 19|
|14||Khoo||HK||42||Sept. 17||Number systems for computing||complete||2, 21|
|15||Tanner||J||43||Sept. 17||Storage by hashing||complete||7, 8, 11, 17, 21|
|8||Lovegren||MN||26||Sept. 19||Non-determinism||complete||5, 5, 22|
|16||Pham||NH||44||Sept. 24||Cellular automata||rescheduled for October 8|
|17||Segall||BA||45||Sept. 24||Cook's theorem||complete||9, 16, 21|
|18||Tran||D||46||Sept. 24||Self-replicating computers||complete||13, 16, 19, 26|
|19||Marshall||N||47||Sept. 26||Storing images||complete||1, 9, 18, 23|
|20||Landsberger||D||49||Sept. 26||Shannon's theory||rescheduled for October 8|
|21||Dahl||TC||50||Sept. 26||Detecting primes||complete||9, 22|
|22||Doherty||FM||56||Oct. 1||VLSI computers||complete||2, 6, 9, 20|
|23||Lother||D||57||Oct. 1||Linear programming||complete||19|
|24||Jacob||RE||58||Oct. 1||Predicate calculus||complete||2, 9, 11, 17, 28|
|25||Ostrowski||GK||59||Oct. 3||The Halting problem||rescheduled for October 10|
|26||Koshak||M||60||Oct. 3||Computer viruses||rescheduled for October 10|
|27||Harris||K||62||Oct. 3||Parallel computing||rescheduled for October 10|
|16||Pham||NH||44||Oct. 8||Cellular automata||complete||24, 26|
|28||Robinson||JJ||63||Oct. 8||The word problem||complete||3, 11, 11, 12, 18, 20, 25|
|20||Landsberger||D||49||Oct. 8||Shannon's theory||complete||2, 13, 22|
|25||Ostrowski||GK||59||Oct. 10||The Halting problem||complete||6, 6, 7, 11, 27|
|26||Koshak||M||60||Oct. 10||Computer viruses||complete||6, 18|
|27||Harris||K||62||Oct. 10||Parallel computing||complete||2, 3, 8, 8, 19, 21, 23|
Systems of logic, boolean bases:
Just about every electronic device uses boolean functions somewhere in its circuitry. A complete base for any function of n variables is defined as the set of operators that can express the function for all values of its variables, which can be derived from its truth table. Complete bases are important because in plenty of computer components, the logic must involve a complete base. Since these components are constructed using gates, finding the smallest number of gates is obviously beneficial. We’ll discuss specific examples with AND and NOT as a complete base, as well as NAND as a complete base.
Godel's Incompleteness theorem:
My Godel presentation will give a description of what it means to formulize mathematics and give a brief history of some landmark attempts to do so. Then, the presentation will then give an overview of Godel's incompleteness theorem followed by a description of the major components of the theorem. The presentation will conclude with an explanation of the implications of his theorem to mathematics and computer science.
An introduction to random numbers will be given which answers two questions. How are random numbers defined, and why is it that we need random numbers. The theorem of Gregory Chaitin and Andrey Kolmogorov will be introduced, along with some consequences of that theorem. Some useful applications of random numbers such as collision resolution, modeling nuclear-physical phenomena, and encryption will be discussed. Finally, methods for generating and/or finding random numbers will be covered along with their merits and drawbacks. Both algorithmic methods, and physical methods for generating random numbers will be covered.
My first presentation is on Program correctness. My lecture will explain what it is, and why is it important to us as Computer Science Students. Examples will be to help explain this to students. I will then cover the fundamentals of Hoare’s ‘Axiomatic Semantics,’ a process for proving program correctness. I will give examples as I go thru the basic parts of this process, and go over the more advanced parts briefly. This topic is covered in our Major, so I will try to relate it as much as possible to how it can be used in our future.
From a natural perspective, the population chosen in a genetic algorithm can be simply viewed as a collection of interacting creatures. The weaker ones tend to die without producing children, while the stronger mate, combining attributes of both parents to produce new and perhaps unique children to continue the cycle. After variation-inducing operators such as mutation and recombination (crossover), we have a better population that illustrates an optimum solution. The size of the population shouldn't be too large, because the genetic algorithms scale rather poorly in these conditions. Genetic algorithms are helpful in many domains like optimization, automatic programming, and immune system modelsetc.
Computer Vision-Polyhedral Scenes:
This presentation describes the recognition of polyhedral scenes. The algorithm developed by David Waltz is the major focus. The lecture provides an in-depth discussion on what the algorithm requires, how it works, and what it produces. Other topics of interest will be applications of the technology and problems associated with this method.
This presentation covers elementary multiplication and matrix multiplication from the perspective of improving the efficiency. The focus will be on the divide and conquer algorithm developed by V. Strassen which computes the multiplication of two nxn matrices with the time complexity of O(n2.81). In addition to the analysis of this improved algorithm, some practical uses for this field of research will be discussed.
CAT Scan or as it is medically known as CT Scan is a procedure that utilizes x-rays and computers to produce 2-dimensional or, if necessary, 3-dimensional images of human anatomy or just about any solid object that can be accommodated inside the gantry of the machine. The discussions high point will be in discussing the Backprojection algorithm for reconstructing a 2-dimensional image from the data produced from the 1-dimensional x-rays.
The partition problem:
Partitioning a set of positive integers into two equal subsets is known in the field of computer science as The Partition Problem. This problem falls into the category of NP-hard algorithms, and as such it is not easy to solve efficiently. This presentation will explain the Partition Problem using visual representations, followed by an explanation of an algorithm that can solve the problem in pseudopolynomial time. The run-time of the algorithm will then be discussed, and the presentation will conclude with examples of practical applications of the Partition Problem.
While digital computing is an important part of the modern computing world, analog computing is a powerful tool that can be used to solve many problems. In this talk, a brief history of analog computing will be examined, exploring examples of how analog computations were beneficial in the past. Then two demonstrations will be done, showing how physical models of analog computations can be done. These two examples will model problems that are difficult to solve with a digital computer, but can be solved relatively easily with an analog machine. Analog processors in specific will be discussed next. Analog and digital processors will be compared, and benefits of analog processors will be shown. Finally, a new application of a new analog chip will be given to show the possible direction analog processors will be taking in the future.
Neural networks are a relatively new concept in computer science. While there existence was acknowledge before the 1980's, it was only then that they g ained more popularity after scientists realized their ability to simulate the le arning of a task. By modeling neurons and synapses, we are able to build s imple "brains" tuned to solving a particular task after a sufficient amount of t raining. The example presented here uses roughly 30 neurons to solve the p roblem of converting coordinates from their Polar form to a Cartesian representa ion. While neural networks are better suited for problems that may not hav e complete or exact information, this example can be a good place to begin learn ing about the structure of neural networks. There are several ways to set up the neural network to handle this task. I will present the simplest for m and briefly touch on a slightly more complex implementaion.
This presentation will cover the basics of sequential logic. First we will examine the differences between sequential and combinational logic. Then we will use these ideas to build up the concept for a flip-flop. These ideas will then be extended to provide an understanding of the implementation of a complete memory cell. Finally we will take the ideas for a memory cell and build the concept of a simple computer memory.
Number systems for computing:
Assuming the audiences have had good experience with the decimal, binary, octal, and hexadecimal base of number systems, this presentation will just give a quick review on the overall base representation including computation and conversion, and move on to the balanced ternary system and its addition operation. The main emphasis is on the Chinese Remainder Theorem as it plays an important role in cryptography. The presenter will go thru the history, goal, derivation of general solution, as well as the applications of the theorem. Two sample problems similar to the submitted homework problems will be solved.
Storage by hashing:
Hashing is a simple technique at the surface, yet efficient hashing requires som e thought. My presentation suggests ways to get good performance from the two ma jor phases -- the hashing function and the collision resolution method. Good has hing functions are an underappreciated component of efficient hashing. While som e methods tend to clump hash keys together, presented hashing functions yield ra ndomly-distributed values for the keys, minimizing collisions. Collisions will s till occur; nevertheless the demonstrated collision resolution methods allow the programmer to predict and control the work needed to handle the conflicting key s. The presentation provides useful information, yet twenty minutes is not enoug h to explore this powerful yet deceptively subtle concept.
This presentation deals with aspects of nondeterminism. Among the topics discussed will be the definition of nondeterminism and ways of implementing nondeterministic algorithms. Also included will be definitions for different types of automata. These will be nondeterministic finite automata, pushdown automata, linear bounded automata, and Turing machines. For each type of automata, the power of the nondeterministic variety will be compared with the deterministic variety, as well as the family of languages which they accept. Also, the method for converting a nondeterministic finite automaton into an equivalent deterministic finite automaton will be presented.
Cooks theorem establishes that the satisfiability problem is NP-Complete by displaying a generic transformation that, in polynomial time, maps each and every problem in NP into the satisfiability problem. This is important because once one problem is shown to be NP-Complete other problems can be reduced to it in polynomial time and shown to be in NP. This presentation will give a short review of the satisfiability problem, and show the generation of a set of clauses using cooks transformation with both predicate and propositional calculus as encoding langauges
From the fact that biological organisms self replicating itself to form more co mplex organisms, mathematician and scientist began studying artificial self rep licating computer in the late 1940s when it became a desire to gain deeper under standing of how a complex machine can be built that could not only compute any c omputable function but also to reproduce itself. The concept of Universal Compu ter Constructor along with the Cellular Automata will be introduced. Also, we'l l do an analysis of various studied models and compare their complexity.
Image storage is a very important subject with the proliferation of web pages and with graphical user interfaces being the defacto standard in operating systems. One method of storing images that provides lossless storage and compression is a quad-tree. By breaking the image up into four quadrants and assigning each quadrant to a node on the tree a quad-tree is formed. Leaf nodes are obtained when the quadrant is of a uniform color. This method is very effective for large images with very little detail, but the overhead makes it prohibitive for very detailed images. For 3-d images a very similar process is used, the only real difference is the image is broken up into eight different regions.
Prime numbers play an important role in mathematics - especially in the area of public key encryption. Today, we will be discussing the different types of prime numbers (twin primes, primorial primes, factorial primes, sophie germain primes and mersenne primes), some popular methods for detecting primes (Sieve of Eratosthenes, Lucas-Lehmer Test, and the Rabin-Miller Probabilistic Test) and also highlight some important finds regarding prime numbers.
Computer hardware has undergone a veritable revolution in the last 20 years. Basic computer functions implemented in printed-circuit boards studded with transistors, capacitors and resistors have now migrated to a new technology of ultra small wires and components etched on the surface of silicon chips. This technology is called very large scale integration (VLSI). This presentation will discuss the VLSI circuit fabrication process, which includes an overview of the VLSI circuit layers, configuration of transistors, implementation of logical circuits and the major fabrication steps used to create a VLSI circuit.
This presentation will briefly cover what Linear programming is and talk about some basic application. Since the book spends most of the time talking about the simplex method, the presentation will cover the simplex method in detail. Finally there will be an example showing how to solve a linear program problem using the simplex method.
Predicate Calculus or First Order Logic is a powerful tool that is used in mathematics, philosophy, artificial intelligence, and other areas. It is by far the most studied and best understood scheme yet devised for knowledge representation and reasoning. I will explain the syntax and semantics of predicate calculus and show how it can be used to represent knowledge.
Cellular Automata is a concept of computer science that has been used for fifty years and has captured the imagination of scientists ever since John von Neumann developed the concept to argue about self-reproduction. The cellular automata provides a way of viewing whole populations of interacting "cells", each of whic h is itself a computer (automaton). By building appropriate rules into a cellula r automaton, we can simulate many kinds of complex behavior. This presentation will look at what CAs are, what they do and also will introduce the Game of Lif e (Conways Life), which is the most well known cellular automaton.
The word problem:
The idea of looking up words in a dictionary is an easy enough task for humans, but for computers it can prove quite difficult. In fact, it turns out to be an unsolvable NP-Complete problem, known as the Word Problem. In this presentation, an introduction to the Word Problem will be given, including Thue's formal def inition, some simple examples, and a reduction to the unsolvable Halting Problem
My presentation is about a theorem developed by Claude Shannon of Bell Laboratories. When a word message is transmitted over any kind of communication channel, there exists a possibility that the bits of the message will be changed during the transmission. Shannon's theorem tells us that for any small positive number E, there is a word length N and a code C having that word length such that the probability of a decoding failure is less than E.
The Halting problem:
This presentation introduces the audience to the concept of the Uncomputable; problems which cannot be solved by a computational model under observation, in this case, the Turing machine. I introduce the inherent flaws in any computational model and prove the existance of the Uncomputable by studying the Halting Problem by means of the Universal Program Analyzer concept. Finally, the consequences and implications of this discovery are presented.
We all know that it is a big problem to get a virus in our computer. So I'm going to present an easy to understand explanation of viruses. I will explain what computer viruses are, how you get them, how they work, types of viruses and how to protect against them. I will give example of each type so that the student can know the difference between each type of them. Viruses can seem mysterious but computer viruses are actually quite easy to understand. I'll give the information you need to know to make sure that your PC is safe from viruses
Parallel computing can be used to increase the speed of classical algorithms, such as sorting. Sometimes, this increase in speed can be very large. I will cover the basics of this architecture, give benefits and detriments of using this architecture, as well as cover two examples (gravitational bodies and a sorting algorithm) that take full advantage of the power parallel processing possesses. I will also cover some ethical/moral issues that this architecture can lead to.