This is the summary of all the materials of module CS-155 in Swansea University. The file contains six chapters: Algorithms, Operating Systems, File Systems, Networks, The Web and Limits of Computing.
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
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Milton. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £2.99. You're not tied to anything after your purchase.
