Concepts of Computer Science
Table of Content
Chapter 7 Algorithms
7.1 Definition
7.2 Searching Algorithms
7.3 Sorting Algorithms
Chapter 10 Operating Systems
10.1 Definition
10.2 Resource Management
10.3 Memory Management
Single Contiguous Memory Management
Partition Memory Management
Paged Memory Management
10.4 Process Management
10.5 CPU Scheduling
Chapter 11 File Systems
11.1 Definition
11.2 File System Technique
11.3 Disk Scheduling
15 Networks
15.1 Local Area Network
15.2 Packet Switching
15.3 Network Address
Chapter 16 The Web
16.1 Highlights
Chapter 18 Limits of Computing
18.1 Limits of Arithmetic
18.2 Limits of Communication
18.3 Problem solvability
1
,Concepts of Computer Science
Chapter 7 Algorithms
7.1 Definition
1. Divide and conquer: break up a large problem into smaller units and solve each smaller
problem
● Applies the concept of abstraction
● The divideandconquer approach can be applied over recursively
2. Algorithm: a set of explicit instructions for a problem or a subproblem
● Abstract step: an algorithm containing unspecified details
● Concrete step: an algorithm in which all details are specified
● Top down design: focus on tasks and break up a large problem into subproblems
● Object oriented design: focus on data to be involved in the solution
3. Composite data type
● Records: a collection in which an item is accessed by name
● Arrays: a collection in which an item is accessed by position within the collection
7.2 Searching Algorithms
1. Sequential Search: start at the beginning until the item is found or the entire list has been
searched
2. Binary Search
● Before applying binary search, the array must be sorted
● Binary search applies the concept divide and conquer
● Start at the middle and finds the item or eliminates half of the unexamined items
1) first ← 0 2) last ← length1 3) found←FALSE
WHILE (first <= last AND not found)
middle ← (first + last) / 2
IF (item equals data[middle]))
found ← TRUE
ELSE IF (item < data[middle])
last ← middle – 1
ELSE
first ← middle + 1
RETURN found
7.3 Sorting Algorithms
1. Selection Sort
● Select the extreme value (either smallest or largest)
● Swap the first unsorted item with the extreme value
2. Bubble Sort
● Repeatedly compare adjacent elements
● Swap when necessary
3. Insertion Sort
● Traverse an array linearly and check each element
2
, Concepts of Computer Science
● Shift the smaller element to the correct position
4. Quick Sort
● Applying divide and conquer, the stack is repeatedly divided at a spit value
● Two variables f and l indicate the first and last data in that part of stack
5. Merge Sort
● Split a list into two and sort each half
● Merge two sorted halves
● For a list of length n, we can halve it log2n times
Selection sort Bubble sort Insertion sort Quick sort Merge sort
Best N2 N2 N2 N log2N N log2N
complexity
Worst N2 N log2N
complexity
Best Complexity when the when the array when the Complexity
performance remains O(N2) array is is sorted split value is remains
all the time sorted the middle N log2N all
of array the time
Outer loop (N1) times (N1) times
Inner loop 1+2+...+(N1) 1+2+...+(N1)
Data Few A lot Few A lot
movement
Space Few Few Few Few A lot
requirement
3
Table of Content
Chapter 7 Algorithms
7.1 Definition
7.2 Searching Algorithms
7.3 Sorting Algorithms
Chapter 10 Operating Systems
10.1 Definition
10.2 Resource Management
10.3 Memory Management
Single Contiguous Memory Management
Partition Memory Management
Paged Memory Management
10.4 Process Management
10.5 CPU Scheduling
Chapter 11 File Systems
11.1 Definition
11.2 File System Technique
11.3 Disk Scheduling
15 Networks
15.1 Local Area Network
15.2 Packet Switching
15.3 Network Address
Chapter 16 The Web
16.1 Highlights
Chapter 18 Limits of Computing
18.1 Limits of Arithmetic
18.2 Limits of Communication
18.3 Problem solvability
1
,Concepts of Computer Science
Chapter 7 Algorithms
7.1 Definition
1. Divide and conquer: break up a large problem into smaller units and solve each smaller
problem
● Applies the concept of abstraction
● The divideandconquer approach can be applied over recursively
2. Algorithm: a set of explicit instructions for a problem or a subproblem
● Abstract step: an algorithm containing unspecified details
● Concrete step: an algorithm in which all details are specified
● Top down design: focus on tasks and break up a large problem into subproblems
● Object oriented design: focus on data to be involved in the solution
3. Composite data type
● Records: a collection in which an item is accessed by name
● Arrays: a collection in which an item is accessed by position within the collection
7.2 Searching Algorithms
1. Sequential Search: start at the beginning until the item is found or the entire list has been
searched
2. Binary Search
● Before applying binary search, the array must be sorted
● Binary search applies the concept divide and conquer
● Start at the middle and finds the item or eliminates half of the unexamined items
1) first ← 0 2) last ← length1 3) found←FALSE
WHILE (first <= last AND not found)
middle ← (first + last) / 2
IF (item equals data[middle]))
found ← TRUE
ELSE IF (item < data[middle])
last ← middle – 1
ELSE
first ← middle + 1
RETURN found
7.3 Sorting Algorithms
1. Selection Sort
● Select the extreme value (either smallest or largest)
● Swap the first unsorted item with the extreme value
2. Bubble Sort
● Repeatedly compare adjacent elements
● Swap when necessary
3. Insertion Sort
● Traverse an array linearly and check each element
2
, Concepts of Computer Science
● Shift the smaller element to the correct position
4. Quick Sort
● Applying divide and conquer, the stack is repeatedly divided at a spit value
● Two variables f and l indicate the first and last data in that part of stack
5. Merge Sort
● Split a list into two and sort each half
● Merge two sorted halves
● For a list of length n, we can halve it log2n times
Selection sort Bubble sort Insertion sort Quick sort Merge sort
Best N2 N2 N2 N log2N N log2N
complexity
Worst N2 N log2N
complexity
Best Complexity when the when the array when the Complexity
performance remains O(N2) array is is sorted split value is remains
all the time sorted the middle N log2N all
of array the time
Outer loop (N1) times (N1) times
Inner loop 1+2+...+(N1) 1+2+...+(N1)
Data Few A lot Few A lot
movement
Space Few Few Few Few A lot
requirement
3
