CS-4 (LESSON 1) Flashcards
Problem Solving: Main Steps
Problem definition
Algorithm design / Algorithm specification
Algorithm analysis
Implementation
Testing
[Maintenance]
What is the task to be accomplished?
What are the time / space / speed / performance requirements ?
Problem Definition
Describe: in natural language / pseudo-code / diagrams / etc.
Algorithm Design / Specifications
Finite set of instructions that, if followed, accomplishes a particular task.
Algorithm
Space complexity
Time complexity
Often, we deal with estimates!
Algorithm Analysis
How much space is required
Space complexity
How much time does it take to run the algorithm
Time complexity
is a procedure (a finite set of well-defined instructions) for accomplishing some tasks which,
given an initial state
terminate in a defined end-state
algorithm
The computational complexity and efficient implementation of the algorithm are important in computing, and this depends on suitable data structures.
Computer Algorithms
Decide on the programming language to use
C, C++, Lisp, Java, Perl, Prolog, assembly, etc. , etc.
Write clean, well documented code
Implementation
Integrate feedback from users, fix bugs, ensure compatibility across different versions
Maintenance
Criteria to follow:
Input
Output
Definiteness
Finiteness
Effectiveness
Zero or more quantities (externally produced)
Input
One or more quantities
Output
Clarity, precision of each instruction
Definiteness
The algorithm has to stop after a finite (may be very large) number of steps
Finiteness
Each instruction has to be basic enough and feasible
Effectiveness
