CIS Study Guide Midterm

10 Pages
Unlock Document

Computing and Information Science
CIS 1500
Michael Wirth

CIS*1500 Midterm Studying Definitions Software: a program designed for the user in order to derive information from data. Software limitations: Software is only limited by human ambition and expectation. We'll always find new algorithms, new applications, and new users. CBIR: Content based image retrieval Semantic gap: disparity between humans and computers. Humans examine images using high-level semantic content and can multitask well, computers use low- level information and perform tasks precisely and identically every time. Good at repetition. Programming: more than just writing code. It is a problem solving activity that has a life cycle. The process of analyzing a problem and creating a solution in the form of a program. Program: a series of characters which when put in the right place will produce the result you want. Set of instructions that is executed to perform some task. Coding: The actual process of writing code. Algorithm: Programs consist of algorithms. An algorithm is just a well-outlined method for completing a task. This high-level abstraction is not actual code. However, it does express the ideas of a program, and is called pseudo- code. It is a verbal description. Analyzing the problem involves identifying the problem inputs and outputs (I/O), and any additional requirements or constraints upon the solution. An algorithm is a computable set of steps to achieve a desired result. Ex. Recipe History of Algorithms: The Rhind Papyrus (Egypt, 1650BC), 300BC describes rule, for calculating the area of a circle given its diameter. Euclid, Greek Mathematician, 300BC The prototype of an algorithm. An algorithm for computing the Greatest Common Divisor of two numbers. Archimedes (Syracuse 287-212BC) used the algorithm in his work, The Measurement of a Circle. Earliest known attempt to formalize the algorithmic process. Generation of prime numbers First algorithm is the Sieve of Eratosthenes The term algorithm is derived from the name of Abu Abd Allah Muhammed ben Musa al- Khwarizmi (c.783-847), a Persian mathematician. Founder of algebra. It was translated as Algorismus in Latin. Algorthmi de numero Indorum (Latin) Algorithms for computing Hindu numerals, base 10 with 0. Derived the decimal system of numeration, using the so-called Arabic numerals. Problem Statement: Specifying the problem statement forces you to state the problem clearly and unambiguously in order to gain a clear understanding of what is required for its solution. Programming Languages: Lack ambiguity and vagueness. Executable: After compiling code, the final form of a program. Unstructured Style: Spaghetti Code. Code is contained in a single continuous block. Complex and tangled control structure. Structured Style: Tasks are split up into smaller componenets. Can be three kinds: Procedural (C, Pascal) Imperative: most procedural languages are also imperative, as they make explicit reference to the state of the execution in the environment Object-Oriented: Passes around objects rather than dealing with procedures, inputs and outputs (C++, Java) Syntax: The set of allowable lexical elements. Software life cycle: Compiler: takes a program in plaintext and converts it to a form a computer can understand, an executable. Many different compilers. We will use GCC! Why C?: C was designed as a language to be used, is a powerful language & can be used on many different systems. History of C: In the beginning there was B. Appeared circa 1969. Designed for PDP-7, PDP-11. PDP-11 had 24K memory. I/O via teletype machine. CIS*1500 Midterm Studying Then New B evolved Added more types. C emerged in 1973 Created by Dennis and Ritchie. Rewrote the entire Unix kernel. ANSI standard C - 1989 9 9 C , 5 9 C Languages in Industries: Defense (1994, 450 languages used in DoD): Weapons systems: Ada-83, C-89, Fortran, CMS-2, Jovial-73, C++ Automated information systems (collecting, processing, transmitting, and displaying information) Cobol, Ada, Basic, C++, C, Fortran Embedded systems: C Air Traffic Control Systems: Ada Aerospace: Ada, Fortran, Jovial, C, C++ Automotive: Assembler, C, C++, Modula-2 Railway: Ada Game programming: C, C++ Coding on the Fly: Rushing into writing code before you have a clear understanding of the requirements. Top-down Design: continuously refining an algorithm until it is at a sufficient depth to translate into code. Creating an overview, then sub problems with no detail, then sub-problems in greater detail, then sub-system levels, etc. Continue until the problem is reduced until simple problems. Each represents a sub-algorithm in the system. Problem solving strategies: Trial and error, brute force, divide and conquer. Trial and error: Guess and check. Select a possible answer, apply it to the problem. If it isn't successful, selects another possibility that is subsequently tried, until a solution is found. Usually a last resort as it is tedious, monotonous and time consuming. Ex. Biological evolution. Wheres Waldo: Randomly test different regions of the picture to see if the pattern exists. Brute Force: Exhaustive search. Systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problems statement. Simple to implement, will always find a solution if one exists. However its cost tends to grow as the size of the problem increases. Often used in crypotgraphic attacks, testing all possible keys in order to recover the plaintext used to produce a particular ciphertext. Wheres Waldo: Test ever possible location for the pattern. Divide and conquer: Break down a problem into sub-problems, and continue to break them down until they become simple enough to solve. Used to solve difficult problems. For tougher problems, we can decompose, where we divide problem into parts, then solve, where we conquer the smaller subproblems, then we combine or put all the subproblems back together to solve the larger original problem. Wheres Waldo: Find a way of finding only the regions with similar attributes and test them. Control Structures: Used to design an algorithm. Can be sequences, decisions, or iterations. Sequences: Contain steps performed one after another Decisions: Contains a condition that can be evaluated as either true or false Iteration: Allows steps to be repeated as long as a condition is true Psuedocode: A detailed yet readable description of what an algorithm must do. It must use natural language, not syntax, and be easily understood. Bridge between abstract algorithm and code itself. Flowchart: Pictorial representation of an algorithmCIS*1500 Midterm Studying Skeleton: The most basic program, does nothing. main() or int main() {} { return 0; } Hello: The rosetta stone of programming. #include int main() { printf(hello world); return 0; } Pre-Processing: Isnt technically compiling, but is the first thing a compiler does. Preprocessor statements begin with a pound sign (#). Using the preprocessor makes programs easier to develop, read, and modify. It makes C code more transportable between different machine architectures. #include: a way of including libraries in your program. Allows us to use functions from these libraries. C libraries: Consist of commonly used program modules, functions. Libraries can be created by users. Each library has a standard header file whose name ends with the symbol .h #define: Allows us to define symbolic constants. Basically used for substitution. Ex: #define PI 3.14159 Comments: A way to embed information in a program about the program. Documenting the code. Aims to express the notion of why rather than how: good comments don't repeat the code, or explain it, they clarify its intent. Two types of comments: Block Comments: Delimited by /* and */ Line Comments: Start with a line delimiter // and continue until the end of the line. Statement: Causes some definite action to be carried out. A simple statement in C is an expression followed by a ; (semicolon). Compound Statement: Consists of several individual statements enclosed within a pair of curly braces {}. The braces are used to group declarations and statements together into a block, so they are equivalent to a single statement. Return Statement: used to tell the OS the status of a program when it
More Less

Related notes for CIS 1500

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.