ACS 211/MIS 222
DATASTRUCTURES AND
ALGORITHMS
REVISION MATERIAL
NAME YOUR DESIRED SCORE IN THE COURSE
STUDY GROUP MEMBER(S) WHEN DO YOU STUDY THIS COURSE
WHEN DOES THE STUDY GROUP MEET
, RECOMMENDED STUDY METHOD FOR SCIENCE COURSES
Browse/scheme
thro the
Notes/Lesson
Before class
Have a study
Attend class to
partner/Study
be taugh
Group.
-clarify any
"We retain Always isolate and concepts during
knowledge by perefct on every class
sharing it"
practical aspect of a
course eg.
Programs, database
queries ,networking
skills etc
Reflect on the
Lesson with no After class,
refference Summarise key
material then points in what
check what you was covered in
could not class
remember
Anthony Wambua | REVISION MATERIAL FOR ASC 211 AND MIS 222 DATASTRUCTURES AND ALGORITHMS
, 1. Define algorithm.
An algorithm is a step-by-step recipe for solving an instance of a problem. It is a precise
procedure for solving a problem in finite number of steps.
2. List the properties of an algorithm.
1. Input: - An algorithm takes zero or more inputs.
2. Output:-An algorithm results in one or more outputs.
3. Finiteness: - All operations can be carried out in a finite time.
4. Effectiveness:-Each step in the algorithm must be easily understood for
someone reading it.
5. Definiteness:-Each step in An algorithm should be concise and clear
3. Differentiate Recursive from iterative algorithms
Iterative(Repetitive) Algorithms -They use loops(while,for,do) and conditional
statements.
Recursive algorithms
They use divide and conquer strategy ; they divide a problem into small pieces and use
the algorithm to solve these small pieces. The solutions are then joined. Divided into
Direct and Indirect recursion
4. Define run time. What is its impact in calculating time complexity?
The time to execute the compiled program. The run time of an algorithm depends upon
the number of instructions present in the algorithm. The run time is in the control of the
programmer, as the compiler is going to compile only the same number of statements,
irrespective of the type of compiler used.
5. Define time complexity of an algorithm.
It is the amount of time (or the number of steps) needed by a program to complete its
task.
6. Define worst case of an algorithm.
It is the longest time that an algorithm will use over all instances of size n for a given
problem to produce a desired result.
7. Define space complexity of an algorithm.
It is the amount of memory used at once by the algorithm until it completes its execution.
8. State the different memory spaces occupied by an algorithm.
Instruction space, data space and environment space.
9. Define divide and conquer algorithm.
It is based on dividing the problem into several, smaller sub instances, solving them
independently and then combining the sub instance solutions so as to yield a solution for
the original instance.
10. Mention some of the problems that implements divide and conquer algorithm.
Divide and conquer algorithm are quick sort, binary search, merge sort
11. Define data structures.
Data structure defines a way of organizing all data items that consider not only the
elements stored but also stores the relationship between the elements.
12. Define static data structures.
Anthony Wambua | REVISION MATERIAL FOR ASC 211 AND MIS 222 DATASTRUCTURES AND ALGORITHMS
DATASTRUCTURES AND
ALGORITHMS
REVISION MATERIAL
NAME YOUR DESIRED SCORE IN THE COURSE
STUDY GROUP MEMBER(S) WHEN DO YOU STUDY THIS COURSE
WHEN DOES THE STUDY GROUP MEET
, RECOMMENDED STUDY METHOD FOR SCIENCE COURSES
Browse/scheme
thro the
Notes/Lesson
Before class
Have a study
Attend class to
partner/Study
be taugh
Group.
-clarify any
"We retain Always isolate and concepts during
knowledge by perefct on every class
sharing it"
practical aspect of a
course eg.
Programs, database
queries ,networking
skills etc
Reflect on the
Lesson with no After class,
refference Summarise key
material then points in what
check what you was covered in
could not class
remember
Anthony Wambua | REVISION MATERIAL FOR ASC 211 AND MIS 222 DATASTRUCTURES AND ALGORITHMS
, 1. Define algorithm.
An algorithm is a step-by-step recipe for solving an instance of a problem. It is a precise
procedure for solving a problem in finite number of steps.
2. List the properties of an algorithm.
1. Input: - An algorithm takes zero or more inputs.
2. Output:-An algorithm results in one or more outputs.
3. Finiteness: - All operations can be carried out in a finite time.
4. Effectiveness:-Each step in the algorithm must be easily understood for
someone reading it.
5. Definiteness:-Each step in An algorithm should be concise and clear
3. Differentiate Recursive from iterative algorithms
Iterative(Repetitive) Algorithms -They use loops(while,for,do) and conditional
statements.
Recursive algorithms
They use divide and conquer strategy ; they divide a problem into small pieces and use
the algorithm to solve these small pieces. The solutions are then joined. Divided into
Direct and Indirect recursion
4. Define run time. What is its impact in calculating time complexity?
The time to execute the compiled program. The run time of an algorithm depends upon
the number of instructions present in the algorithm. The run time is in the control of the
programmer, as the compiler is going to compile only the same number of statements,
irrespective of the type of compiler used.
5. Define time complexity of an algorithm.
It is the amount of time (or the number of steps) needed by a program to complete its
task.
6. Define worst case of an algorithm.
It is the longest time that an algorithm will use over all instances of size n for a given
problem to produce a desired result.
7. Define space complexity of an algorithm.
It is the amount of memory used at once by the algorithm until it completes its execution.
8. State the different memory spaces occupied by an algorithm.
Instruction space, data space and environment space.
9. Define divide and conquer algorithm.
It is based on dividing the problem into several, smaller sub instances, solving them
independently and then combining the sub instance solutions so as to yield a solution for
the original instance.
10. Mention some of the problems that implements divide and conquer algorithm.
Divide and conquer algorithm are quick sort, binary search, merge sort
11. Define data structures.
Data structure defines a way of organizing all data items that consider not only the
elements stored but also stores the relationship between the elements.
12. Define static data structures.
Anthony Wambua | REVISION MATERIAL FOR ASC 211 AND MIS 222 DATASTRUCTURES AND ALGORITHMS
