CSCI Exam 1
Terms
undefined, object
copy deck
- Selection
- Conditional operations. allows choosing between alternative courses of action
- Iteration
- Looping. allows us to repeat a set of actions
- IF it doesn't rain, THEN walk the dog rake the leaves, ELSE go to the grocery store go to movie matinee
- Selection
- walk the dog rake leaves go to grocery store go to movie matinee
- Sequence
- Walk the dog While there are more leaves and the ;eaf bag supply lasts rake leaves stuff a bag Go to store Go to movie
- Looping
- Formal definition of Computer Science
- The study of algorithms, including 1) their formal and mathematical properties (studying algorithm efficiency) 2) Their hardware realizations (building computer systems to execute algorithms) 3) Their linguisitc realizations (algorithms translated into high level languages :software) 4) Their applications (algorithms used to solve important common problems)
- Why are formal algorithms so important to Science
- Answer: In we can specify an algorithm to solve a problem, then we can automate its solution. Computer revolution has freed us from the drusgery of repetitive mental tasks to allow us to focus more attention on planning creative & efficient solutions to problems
- Not all problems lend themselves to algorithmic descriptions or computer solutions
- 1) Sometimes a computer solution is simply inappropriate for the problem at hand 2) Sometimes solutions do not exist 3) SOmetimes a solution is too inefficient to be of use
- What is a computer?
- general purpose data-processing machine
- Data processing
- the transformation of raw data into information
- Raw data
- unorganized facts and figures
- Information
- organized and meaningful knowledge that results from processing data
- program
- processing and transformation of raw data into information
- What is Computer Science
- the study of algorithms, both their hardware and software realizations
- Algorithm
- A step by steb method for accomplishing a task (i.e., a to do list, a recpe, a set of instructions)
- Algorithms use control structures
- Sequence, Selection, and Iteration
- Sequence
- a linear ordered set of instructions. carries out a single well-defined task.
- Algorithm (formal definition)
- a well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.
- "effectively computable⬝ (doable)
- (there must exist a computational process that allows the operation to be completed successfully)
- Algorithm requirements
- Algorithm requirements: 1) well-ordered 2) unambiguous 3)Computable 4) halts
- Problems with natural language
- same words can be interpreted differently
- problem with formal language
- algorithm deal with problem solving in an abstract way. formal program language deals with syntax, grammer, punctuation
- Best language for ALgorithm. Why?
- Pseudocode. It uses subset of english and math symbols. it is flexible
- Attributes of Algorithms
- Correctness Ease of understanding Elegance Efficiency
- Efficiency
- Time (Time is especially important for real-time programming, that is ongoing activities like landing the space shuttle or online banking.) Space (There is an upper limit on the amount of memory that the computer has available.)
- time efficiency
- indication of the amount of work required by the program independent of machine
- Algorithms for Common Tasks
- Searching - Sequential search and binary search Sorting - selection sort
- Sequential Search
- Search for NAME (item to be found) among a list of n names (items) Start at the beginning and compare NAME to each entry in the list until a match is found Central task: The comparison of the NAME being searched for against an indexed name in the list. Peripheral tasks (generally contribute a negligible amount of work) Setting the initial value of index i Incrementing i ( moving the index forward in the list) Adjusting the value of Found Outputting results
- Cases for Sequential search
- Best Case: Minimum amount of work is done if NAME is the first element in the list, N1 Worst Case: This is the maximum amount of work. This will require n comparisons If NAME is found at the end of the list, Nn If NAME is not in the list Average Case: If NAME is found somewhere in the middle of the list. It requires somewhere between 1 and n comparisons (roughly n/2 comparisons)
- Selection Sort
- Takes a sequence of n values and rearranges them into order Uses the ‘Find Largest’ algorithm to assist in the process
- Order of magnitude
- Sequential Search - n Selection sort - n2 (squared) Binary search lg2 n
- Binary search
- Precondition: List must be already sorted !! First looks for NAME in the middle of the list. If a match occurs the search is over. If name comes alphabetically before the middle then we look in the first half of the list else we look in the last half of the list Repeat this process on the iteratively smaller sub-lists until NAME is found or the final sub-list becomes empty.
- Binary search cases
- best case - we find NAME on the first try Worst case - name is not on the list
- sequential search vs binary search
- Binary is faster but original data has to be sorted first Sequential search is slower but can be done on unsorted list